On Explaining Integer Vectors by Few Homogenous Segments

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F13%3A00209345" target="_blank" >RIV/68407700:21240/13:00209345 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007%2F978-3-642-40104-6_18" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-642-40104-6_18</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-40104-6_18" target="_blank" >10.1007/978-3-642-40104-6_18</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Explaining Integer Vectors by Few Homogenous Segments

Popis výsledku v původním jazyce

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 onlypositive 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.

Název v anglickém jazyce

On Explaining Integer Vectors by Few Homogenous Segments

Popis výsledku anglicky

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 onlypositive 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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ISBN

978-3-642-40103-9

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

207-218

Název nakladatele

Springer Science+Business Media

Místo vydání

Berlin

Místo konání akce

London, ON

Datum konání akce

12. 8. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—