NDLI: Generating facets for the cut polytope of a graph by triangular elimination

Content Provider	Springer Nature Link
Author	Ito, Tsuyoshi Avis, David Imai, Hiroshi
Copyright Year	2006
Abstract	The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.
Ending Page	325
Page Count	23
Starting Page	303
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	2
Volume Number	112
Language	English
Publisher	Springer-Verlag
Publisher Date	2006-08-02
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Cut polytope Mathematical and Computational Physics Lifting Mathematical Methods in Physics Graph Mathematics of Computing Calculus of Variations and Optimal Control; Optimization Numerical Analysis Special polytopes (linear programming, centrally symmetric, etc.) Combinatorics Fourier–Motzkin elimination Polyhedral combinatorics, branch-and-bound, branch-and-cut Facet
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Generating facets for the cut polytope of a graph by triangular elimination

Some characteristics of the simple Boolean quadric polytope extension

Generating Facets for the Independence System Polytope

Basic Polyhedral Theory

Facets of the Weak Order Polytope Derived from the Induced Partition Projection

Packing and partitioning orbitopes

Orbitopal Fixing

Constructing Extended Formulations from Reflection Relations

Deriving tight Bell inequalities for 2 parties with many 2-valued observables from facets of cut polytopes. arXiv:quant-ph/0404014 (2004)

Generating facets for the cut polytope of a graph by triangular elimination

Similar Documents

Generating facets for the cut polytope of a graph by triangular elimination

Some characteristics of the simple Boolean quadric polytope extension

Generating Facets for the Independence System Polytope

Basic Polyhedral Theory

Facets of the Weak Order Polytope Derived from the Induced Partition Projection

Packing and partitioning orbitopes

Orbitopal Fixing

Constructing Extended Formulations from Reflection Relations

Deriving tight Bell inequalities for 2 parties with many 2-valued observables from facets of cut polytopes. arXiv:quant-ph/0404014 (2004)

Generating facets for the cut polytope of a graph by triangular elimination