Approximating Single Machine Scheduling with Scenarios
From MaRDI portal
Publication:3541793
DOI10.1007/978-3-540-85363-3_13zbMath1159.68671MaRDI QIDQ3541793
Monaldo Mastrolilli, Ola Svensson, Nikolaus Mutsanas
Publication date: 27 November 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_13
90B35: Deterministic scheduling theory in operations research
90C27: Combinatorial optimization
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Approximating a two-machine flow shop scheduling under discrete scenario uncertainty, On the approximability of robust spanning tree problems
Cites Work
- Robust discrete optimization and its applications
- Robust discrete optimization and network flows
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
- On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
- On the power of unique 2-prover 1-round games
- A new multilayered PCP and the hardness of hypergraph vertex cover
- Approximating Min-Max (Regret) Versions of Some Polynomial Problems
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- An algorithm for the single machine sequencing problem with precedence constraints
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Introduction to Stochastic Programming
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
- Single-Machine Scheduling with Precedence Constraints
- Robust Combinatorial Optimization with Exponential Scenarios
