Tight approximations for resource constrained scheduling and bin packing

DOI10.1016/S0166-218X(97)00045-0zbMath0892.60013OpenAlexW2054094480MaRDI QIDQ1372745

Peter Stangier, Anand Srivastav

Publication date: 7 January 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

approximation algorithmrandomized algorithmchromatic indexderandomizationresource constrained schedulingmultidimensional bin packing

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Combinatorial probability (60C05)

Related Items

Color-bounded hypergraphs. VI: Structural and functional jumps in complexity ⋮ Approximate strong separation with application in fractional graph coloring and preemptive scheduling. ⋮ Improving simulated annealing with variable neighborhood search to solve the resource-constrained scheduling problem ⋮ Color-bounded hypergraphs, IV: Stable colorings of hypertrees ⋮ Production, maintenance and resource scheduling: a review ⋮ Parallel machine scheduling with additional resources: notation, classification, models and solution methods

Cites Work

• Approximation algorithms for scheduling unrelated parallel machines
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Bin packing can be solved within 1+epsilon in linear time
• Geometric algorithms and combinatorial optimization
• Resource constrained scheduling as generalized bin packing
• The probabilistic method yields deterministic parallel algorithms
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• The NP-Completeness of Edge-Coloring
• Simulating (log ^c n )-wise independence in NC
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Tight approximations for resource constrained scheduling and bin packing