On the Lifted Multicut Polytope for Trees
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
We study the lifted multicut problem restricted to trees, which is np-hard in general and solvable in polynomial time for paths. In particular, we characterize facets of the lifted multicut polytope for trees defined by the inequalities of a canonical relaxation. Moreover, we present an additional class of inequalities associated with paths that are facet-defining. Taken together, our facets yield a complete totally dual integral description of the lifted multicut polytope for paths. This description establishes a connection to the combinatorial properties of alternative formulations such as sequential set partitioning.
Details
Originalsprache | Englisch |
---|---|
Titel | Pattern Recognition |
Redakteure/-innen | Zeynep Akata, Andreas Geiger, Torsten Sattler |
Herausgeber (Verlag) | Springer, Berlin [u. a.] |
Seiten | 360–372 |
ISBN (elektronisch) | 978-3-030-71278-5 |
ISBN (Print) | 978-3-030-71277-8 |
Publikationsstatus | Veröffentlicht - 2020 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | Lecture Notes in Computer Science, Volume 12544 |
---|---|
ISSN | 0302-9743 |
Externe IDs
Scopus | 85104882919 |
---|---|
ORCID | /0000-0001-5036-9162/work/161888478 |