scientific article; zbMATH DE number 3876926

MaRDI QIDQ3342215zbMATH OpenFDO

Authors Christos Papadimitriou

Publication date 1984

zbMATH Keywords

computational complexity of combinatorial optimization problemsellipsoid algorithmNP-completenesspolytopes, facetssupporting hyperplanessurvey

Mathematics Subject Classification ID

Polytopes and polyhedra (52Bxx) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Recommendations

• Polyhedral combinatorics and combinatorial optimization
• Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes
• scientific article; zbMATH DE number 919758
• scientific article; zbMATH DE number 1961535
• scientific article; zbMATH DE number 19091

Cited in

(21)

• The complexity of facets (and some facets of complexity)
• Correlation polytopes: Their geometry and complexity
• Geometric comparison of combinatorial polytopes
• Matchings in colored bipartite networks
• An analog of the Cook theorem for polytopes
• A bound on the k-gonality of facets of the hypermetric cone and related complexity problems
• Complexity yardsticks for \(f\)-vectors of polytopes and spheres
• The simplest families of polytopes associated with NP-hard problems
• Random bichromatic matchings
• scientific article; zbMATH DE number 1687058 (Why is no real title available?)
• scientific article; zbMATH DE number 3860890 (Why is no real title available?)
• Polyhedral combinatorics and combinatorial optimization
• Reducibility among combinatorial problems
• scientific article; zbMATH DE number 3906238 (Why is no real title available?)
• scientific article; zbMATH DE number 4020474 (Why is no real title available?)
• scientific article; zbMATH DE number 702972 (Why is no real title available?)
• scientific article; zbMATH DE number 702975 (Why is no real title available?)
• scientific article; zbMATH DE number 1961535 (Why is no real title available?)
• scientific article; zbMATH DE number 919758 (Why is no real title available?)
• Nonlinear bipartite matching
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3342215)