Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets

DOI10.1137/050636589MaRDI QIDQ3544249zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Moshe Dror, James B. Orlin

Publication date 5 December 2008

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/1dd6704bf3e43eb6fb0fe6e3e5efe4d82ae7aa53

zbMATH Keywords

approximation algorithmsgeneralized bin packinggeneralized scheduling problemsinapproximabilitysubset travelling salesman

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• Combinatorial Optimization Problems for Systems of Subsets
• scientific article; zbMATH DE number 3912107
• Combinatorial optimization problems related to the committee polyhedral separability of finite sets
• Exact algorithms for combinatorial optimization problems with submodular objective functions
• Subclasses of solvable problems from classes of combinatorial optimization problems
• scientific article; zbMATH DE number 2168886
• Deterministic and iterative solutions to subset selection problems
• scientific article; zbMATH DE number 2185596
• Exact Algorithms for Generalized Combinatorial Optimization Problems

Cited in

(12)

• Approximation schemes for the generalized traveling salesman problem
• Minimum color spanning circle of imprecise points
• Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
• Minimum color spanning circle in imprecise setup
• Constant-factor approximation for TSP with disks
• Fixed set search applied to the clique partitioning problem
• Observation routes and external watchman routes
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• Observation routes and external watchman routes
• Geometric TSP on sets
• Geometric TSP on sets
• Fixed set search matheuristic applied to the knapsack problem with forfeits

This page was built for publication: Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets

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