An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
From MaRDI portal
Publication:2492210
DOI10.1016/j.dam.2005.05.036zbMath1131.90048OpenAlexW2027038333MaRDI QIDQ2492210
Horst W. Hamacher, Francesco Maffioli, Matthias Ehrgott, Maurizio Bruglieri
Publication date: 9 June 2006
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.036
Related Items
A Note on Edge Isoperimetric Numbers and Regular Graphs, On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study, An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints, Cardinality constrained combinatorial optimization: complexity and polyhedra, A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting, Constrained Graph Partitioning via Matrix Differential Equations, Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint, Cardinality constrained minimum cut problems: complexity and algorithms., Counting or producing all fixed cardinality transversals, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Fixed cardinality stable sets, The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs, Parameterized algorithms for the happy set problem, Optimization of product category allocation in multiple warehouses to minimize splitting of online supermarket customer orders, On \(k\)-Max-optimization, The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope, The bottleneck \(k\)-MST, On solving the densestk-subgraph problem on large graphs, An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 2.5-factor approximation algorithm for the \(k\)-MST problem
- The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane
- The facility selection-location problem
- Forest covers and a polyhedral intersection theorem
- Search-hide games on trees
- Lexicographic bottleneck problems
- Lot-sizing polyhedra with a cardinality constraint
- Integer programming approaches to facilities layout models with forbidden areas
- \(K\)-tree/\(K\)-subgraph: A program package for minimal weighted \(K\)-cardinlity trees and subgraphs
- The \(k\)-partitioning problem
- On \(k\)-partitioning of Hamming graphs
- A constant-factor approximation algorithm for the \(k\)-MST problem
- \(k\)-edge subgraph problems
- The \(k\)-cardinality assignment problem
- Faster geometric \(k\)-point MST approximation
- Compact location problems
- On center cycles in grid graphs
- Cardinality constrained minimum cut problems: complexity and algorithms.
- Approximation algorithms for knapsack problems with cardinality constraints
- Upper and lower bounding procedures for minimum rooted \(k\)-subtree problem
- New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem
- The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices
- Local search algorithms for the \(k\)-cardinality tree problem.
- Variable neighborhood decomposition search for the edge weighted \(k\)-cardinality tree problem
- A projection technique for partitioning the nodes of a graph
- Cardinality constrained bin-packing problems
- Approximation algorithms for minimum \(K\)-cut
- Hybrid rounding techniques for knapsack problems
- The maximal dispersion problem and the ``first point outside the neighbourhood heuristic
- Graph minors. IV: Tree-width and well-quasi-ordering
- Approximation Algorithms for Dispersion Problems
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Finding k points with minimum diameter and related problems
- Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
- The NP-Completeness of Some Edge-Partition Problems
- Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
- On Linear Time Minor Tests with Depth-First Search
- An efficient algorithm for minimumk-covers in weighted graphs
- The Optimal Partitioning of Graphs
- Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
- An Efficient Heuristic Procedure for Partitioning Graphs
- New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
- A Constant-Factor Approximation Algorithm for the Geometrick-MST Problem in the Plane
- Decomposing Matrices into Blocks
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Weighted k‐cardinality trees: Complexity and polyhedral structure
- Heuristic and Special Case Algorithms for Dispersion Problems
- Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints
- Finding k Cuts within Twice the Optimal
- Color-coding
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Genetic algorithm and graph partitioning
- Spanning Trees—Short or Small
- Approximation Algorithms for the k-Clique Covering Problem
- On Bounds for the k-Partitioning of Graphs
- Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation
- Greedily Finding a Dense Subgraph
- Minimum Covers of Fixed Cardinality in Weighted Graphs
- Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem
- Lower Bounds for the Partitioning of Graphs
- The dense \(k\)-subgraph problem
- Bounds for the cardinality constrained \(P \|C_{max}\) problem
