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

DOI10.1137/050636589zbMath1158.68011OpenAlexW1997900197WikidataQ59592409 ScholiaQ59592409MaRDI QIDQ3544249

James B. Orlin, Moshe Dror

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)

Related Items (8)

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

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