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 |