An alternative approach for proving the NP-hardness of optimization problems
From MaRDI portal
Publication:320621
DOI10.1016/j.ejor.2015.06.076zbMath1346.90833OpenAlexW1478931920MaRDI QIDQ320621
Publication date: 7 October 2016
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2015.06.076
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
Scheduling lower bounds via AND subset sum ⋮ On the complexity of constructing a minmax regret solution for the two-machine flow shop problem under the interval uncertainty ⋮ A review of four decades of time-dependent scheduling: main results, new topics, and open problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Flowshop scheduling with a general exponential learning effect
- A generic approach to proving NP-hardness of partition type problems
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
- Minimizing the number of tardy job units under release time constraints
- Time-dependent scheduling
- ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
- Exact and approximate algorithms for high-multiplicity parallel machine scheduling
- Equivalent time-dependent scheduling problems
- Single-machine scheduling with learning considerations
- Batch scheduling with deadlines on parallel machines
- A note on scheduling on a single processor with speed dependent on a number of executed jobs
- A concise survey of scheduling with time-dependent processing times
- An introduction to multi-parameter complexity analysis of discrete problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- An unconstrained optimization problem is NP-hard given an oracle representation of its objective function: a technical note
- Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine
- Single-machine scheduling problems with actual time-dependent and job-dependent learning effect
- Single-machine scheduling and due date assignment with rejection and position-dependent processing times
- Unrelated parallel-machine scheduling with position-dependent deteriorating jobs and resource-dependent processing time
- A state-of-the-art review on scheduling with learning effects
- A framework for the complexity of high-multiplicity scheduling problems
- Scheduling with time dependent processing times: Review and extensions
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Parametric problem in scheduling theory
- Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
- High Multiplicity in Earliness-Tardiness Scheduling
- Multiagent Scheduling
- Multiplicity and complexity issues in contemporary production scheduling
- Parallel machine scheduling with high multiplicity
- Single machine scheduling with learning effect considerations
This page was built for publication: An alternative approach for proving the NP-hardness of optimization problems
