Attributes | Values |
---|
rdf:type
| |
rdfs:seeAlso
| |
Description
| - We extend previous studies on NP-hard problems dealing with the decomposition of nonnegative integer vectors into sums of few homogeneous segments. These problems are motivated by radiation therapy and database applications. If the segments may have only positive integer entries, then the problem is called Vector Explanation+. If arbitrary integer entries are allowed in the decomposition, then the problem is called Vector Explanation. Considering several natural parameterizations (including maximum vector entry, maximum difference between consecutive vector entries, maximum segment length), we obtain a refined picture of the computational (in-)tractability of these problems. In particular, we show that in relevant cases Vector Explanation+ is algorithmically harder than Vector Explanation.
- We extend previous studies on NP-hard problems dealing with the decomposition of nonnegative integer vectors into sums of few homogeneous segments. These problems are motivated by radiation therapy and database applications. If the segments may have only positive integer entries, then the problem is called Vector Explanation+. If arbitrary integer entries are allowed in the decomposition, then the problem is called Vector Explanation. Considering several natural parameterizations (including maximum vector entry, maximum difference between consecutive vector entries, maximum segment length), we obtain a refined picture of the computational (in-)tractability of these problems. In particular, we show that in relevant cases Vector Explanation+ is algorithmically harder than Vector Explanation. (en)
|
Title
| - On Explaining Integer Vectors by Few Homogenous Segments
- On Explaining Integer Vectors by Few Homogenous Segments (en)
|
skos:prefLabel
| - On Explaining Integer Vectors by Few Homogenous Segments
- On Explaining Integer Vectors by Few Homogenous Segments (en)
|
skos:notation
| - RIV/68407700:21240/13:00209345!RIV14-MSM-21240___
|
http://linked.open...avai/predkladatel
| |
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/68407700:21240/13:00209345
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - parameterized complexity; matrix and vector decomposition; multivariate algorithmics; NP-hardness and exact algorithms (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...v/mistoKonaniAkce
| |
http://linked.open...i/riv/mistoVydani
| |
http://linked.open...i/riv/nazevZdroje
| - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...iv/tvurceVysledku
| - Suchý, Ondřej
- Chen, J.
- Hartung, S.
- Niedermeier, R.
- Komusiewicz, C.
- Bredereck, R.
|
http://linked.open...vavai/riv/typAkce
| |
http://linked.open.../riv/zahajeniAkce
| |
issn
| |
number of pages
| |
http://bibframe.org/vocab/doi
| - 10.1007/978-3-642-40104-6_18
|
http://purl.org/ne...btex#hasPublisher
| - Springer Science+Business Media
|
https://schema.org/isbn
| |
http://localhost/t...ganizacniJednotka
| |