Cardinality constrained combinatorial optimization: complexity and polyhedra

DOI10.1016/J.DISOPT.2010.03.002MaRDI QIDQ429646zbMATH OpenOpenAlexFDO

Authors Rüdiger Stephan

Publication date 20 June 2012

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2010.03.002

zbMATH Keywords

valid inequalitiescardinality constraintscut polytopematroidal relaxation

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Polyhedral aspects of cardinality constrained combinatorial optimization problems
• On the cardinality constrained matroid polytope
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• Cardinality constraints and systems of restricted representatives
• A polyhedral study of the cardinality constrained knapsack problem

Cites work

• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• scientific article; zbMATH DE number 3818558 (Why is no real title available?)
• scientific article; zbMATH DE number 3562010 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2196280 (Why is no real title available?)
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Disjunctive programming: Properties of the convex hull of feasible points
• Facets of the Bipartite Subgraph Polytope
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Matroids and the greedy algorithm
• Maximum matching and a polyhedron with 0,1-vertices
• On cardinality constrained cycle and path polytopes
• On defining sets of vertices of the hypercube by linear inequalities
• On the cut polytope
• The Factorization of Linear Graphs
• polymake: a framework for analyzing convex polytopes

Cited in

(19)

• On cardinality constrained polymatroids
• The location-dispatching problem: polyhedral results and content delivery network design
• Dual consistent systems of linear inequalities and cardinality constrained polytopes
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• Lot-sizing polyhedra with a cardinality constraint
• Cardinality minimization, constraints, and regularization: a survey
• Multi-clustering via evolutionary multi-objective optimization
• On the cardinality constrained matroid polytope
• On cardinality constrained polymatroids
• On the Complexity of Clustering with Relaxed Size Constraints
• On the complexity of clustering with relaxed size constraints in fixed dimension
• Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes
• Combinatorial flexibility problems and their computational complexity
• Forbidden vertices
• Cardinality constrained and multicriteria (multi)cut problems
• Polyhedral aspects of cardinality constrained combinatorial optimization problems
• Cardinality constraints and systems of restricted representatives
• Polyhedra with high-density graphs and polynomial-time solvability of combinatorial optimization problems
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

Describes a project that uses

Uses Software

• polymake

This page was built for publication: Cardinality constrained combinatorial optimization: complexity and polyhedra

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