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

cardinality constraintscut polytopematroidal relaxationvalid inequalities

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

• 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
• 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?)
• 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
• polymake: a framework for analyzing convex polytopes
• The Factorization of Linear Graphs

Cited in

(21)

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

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)