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

DOI10.1137/050636589zbMATH Open1158.68011DBLPjournals/siamdm/DrorO08OpenAlexW1997900197WikidataQ59592409 ScholiaQ59592409MaRDI QIDQ3544249FDOQ3544249

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

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

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)

Cited In (9)

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

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)