On the Lifted Multicut Polytope for Trees

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-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 languageEnglish
Title of host publicationPattern Recognition
EditorsZeynep Akata, Andreas Geiger, Torsten Sattler
PublisherSpringer, Berlin [u. a.]
Pages360–372
ISBN (electronic)978-3-030-71278-5
ISBN (print)978-3-030-71277-8
Publication statusPublished - 2020
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science, Volume 12544
ISSN0302-9743

External IDs

Scopus 85104882919
ORCID /0000-0001-5036-9162/work/161888478

Keywords

Library keywords