The simplest families of polytopes associated with NP-hard problems

DOI10.1134/S1064562415010160zbMath1320.52012MaRDI QIDQ2353062

Aleksandr N. Maksimenko

Publication date: 7 July 2015

Published in: Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-hard problemsaffine mappings of polytopes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (1)

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

Cites Work

• Unnamed Item
• On certain polytopes associated with graphs
• On affine reducibility of combinatorial polytopes
• The common face of some 0/1-polytopes with NP-complete nonadjacency relation
• Exact Algorithms for the Quadratic Linear Ordering Problem
• Linear vs. semidefinite extended formulations
• Geometry of cuts and metrics

This page was built for publication: The simplest families of polytopes associated with NP-hard problems