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 algorithmsinapproximabilitygeneralized bin packinggeneralized scheduling problemssubset travelling salesman

Mathematics Subject Classification ID

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

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

(9)

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

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)