Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes

DOI10.1134/S1990478916030078zbMath1374.90325arXiv1410.7082OpenAlexW3099490925MaRDI QIDQ2959185

Aleksandr N. Maksimenko

Publication date: 9 February 2017

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.7082

zbMATH Keywords

cyclic polytopeextended formulationcombinatorial equivalencegraph of a polytopegraph clique numberNP-complex problemvertex-facet incidence matrix

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Combinatorial optimization (90C27)

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial and geometric properties of the max-cut and min-cut problems
• Extended formulations for polygons
• Expressing combinatorial optimization problems by linear programs
• Combinatorial bounds on nonnegative rank and extended formulations
• Computing the face lattice of a polytope from its vertex-facet incidences
• The common face of some 0/1-polytopes with NP-complete nonadjacency relation
• A short proof that the extension complexity of the correlation polytope grows exponentially
• Small extended formulations for cyclic polytopes
• The simplest families of polytopes associated with NP-hard problems
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Communication Theory of Secrecy Systems*
• The travelling salesman problem and a class of polyhedra of diameter two
• Lectures on Polytopes
• The Matching Polytope has Exponential Extension Complexity
• Solution of a Large-Scale Traveling-Salesman Problem
• Geometry of cuts and metrics
• Extended formulations in combinatorial optimization