On the Lifted Multicut Polytope for Trees
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
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
Original language | English |
---|---|
Title of host publication | Pattern Recognition |
Editors | Zeynep Akata, Andreas Geiger, Torsten Sattler |
Publisher | Springer, Berlin [u. a.] |
Pages | 360–372 |
ISBN (electronic) | 978-3-030-71278-5 |
ISBN (print) | 978-3-030-71277-8 |
Publication status | Published - 2020 |
Peer-reviewed | Yes |
Publication series
Series | Lecture Notes in Computer Science, Volume 12544 |
---|---|
ISSN | 0302-9743 |
External IDs
Scopus | 85104882919 |
---|---|
ORCID | /0000-0001-5036-9162/work/161888478 |