On the Lifted Multicut Polytope for Trees

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

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

OriginalspracheEnglisch
TitelPattern Recognition
Redakteure/-innenZeynep Akata, Andreas Geiger, Torsten Sattler
Herausgeber (Verlag)Springer, Berlin [u. a.]
Seiten360–372
ISBN (elektronisch)978-3-030-71278-5
ISBN (Print)978-3-030-71277-8
PublikationsstatusVeröffentlicht - 2020
Peer-Review-StatusJa

Publikationsreihe

ReiheLecture Notes in Computer Science, Volume 12544
ISSN0302-9743

Externe IDs

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

Schlagworte

Bibliotheksschlagworte