Tight approximations for resource constrained scheduling and bin packing
DOI10.1016/S0166-218X(97)00045-0zbMATH Open0892.60013OpenAlexW2054094480MaRDI QIDQ1372745FDOQ1372745
Authors: Anand Srivastav, Peter Stangier 
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
Recommendations
- Approximation algorithms for scheduling and packing problems
- scientific article; zbMATH DE number 3997164
- Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems
- Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems
- Approximation algorithms for extensible bin packing
- Approximation algorithms for extensible bin packing
- A tight lower bound for optimal bin packing
- Bounding the running time of algorithms for scheduling and packing problems
- Bounding the running time of algorithms for scheduling and packing problems
randomized algorithmapproximation algorithmderandomizationchromatic indexresource constrained schedulingmultidimensional bin packing
Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Integer programming (90C10) Combinatorial probability (60C05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Geometric algorithms and combinatorial optimization
- Bin packing can be solved within 1+epsilon in linear time
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for scheduling unrelated parallel machines
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Resource constrained scheduling as generalized bin packing
- Title not available (Why is that?)
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Title not available (Why is that?)
- The probabilistic method yields deterministic parallel algorithms
- Simulating (log c n )-wise independence in NC
- Title not available (Why is that?)
Cited In (15)
- Compact integer linear programming formulations for the temporal bin packing problem with fire-ups
- Production, maintenance and resource scheduling: a review
- Title not available (Why is that?)
- Approximability results for the resource-constrained project scheduling problem with a single type of resources
- Scheduling with an orthogonal resource constraint
- Resource constrained scheduling on multiple machines
- Color-bounded hypergraphs. VI: Structural and functional jumps in complexity
- Color-bounded hypergraphs, IV: Stable colorings of hypertrees
- Title not available (Why is that?)
- Approximation schemes for machine scheduling with resource (in-)dependent processing times
- Improving simulated annealing with variable neighborhood search to solve the resource-constrained scheduling problem
- Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
- On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes
- Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups
- Parallel machine scheduling with additional resources: notation, classification, models and solution methods
This page was built for publication: Tight approximations for resource constrained scheduling and bin packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1372745)
