Paper Info
Title
The polytope of tree-structured binary constraint satisfaction problems
Abstract
We correct a result that we recently published in this conference series on the polytope of Binary Constraint Problems (BCPs). We had claimed that the so-called "support formulation" would characterize the convex hull of all feasible solutions to tree-structured BCPs. We show that this claim is not accurate by providing a small counter example. We then show that the respective polytope defines a facet of the stable-set polytope of a perfect graph which allows us to perform LP inference in polynomial time.
Year
Venue
Keywords
2008
CPAIOR
convex hull,lp inference,tree-structured bcps,polynomial time,respective polytope,feasible solution,conference series,binary constraint problems,perfect graph,stable-set polytope,tree-structured binary constraint satisfaction,constraint satisfaction problem,tree structure
Field
DocType
Volume
Birkhoff polytope,Discrete mathematics,Combinatorics,Mathematical optimization,Ehrhart polynomial,Computer science,Convex polytope,Linear programming,Facet (geometry),Cross-polytope,Vertex enumeration problem,Binary constraint
Conference
5015
ISSN
ISBN
Citations 
0302-9743
3-540-68154-X
2
PageRank 
References 
Authors
0.38
6
1
Name
Order
Citations
PageRank
Meinolf Sellmann172848.77