An alternative approach for proving the NP-hardness of optimization problems
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 5799870
- A generic approach to proving NP-hardness of partition type problems
- scientific article; zbMATH DE number 847149
- The inapproximability of non-NP-hard optimization problems.
- An unconstrained optimization problem is NP-hard given an oracle representation of its objective function: a technical note
Cites work
- scientific article; zbMATH DE number 1731178 (Why is no real title available?)
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- A concise survey of scheduling with time-dependent processing times
- A framework for the complexity of high-multiplicity scheduling problems
- A generic approach to proving NP-hardness of partition type problems
- A note on scheduling on a single processor with speed dependent on a number of executed jobs
- A state-of-the-art review on scheduling with learning effects
- An introduction to multi-parameter complexity analysis of discrete problems
- An unconstrained optimization problem is NP-hard given an oracle representation of its objective function: a technical note
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Batch scheduling with deadlines on parallel machines
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Equivalent time-dependent scheduling problems
- Exact and approximate algorithms for high-multiplicity parallel machine scheduling
- Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine
- Flowshop scheduling with a general exponential learning effect
- High Multiplicity in Earliness-Tardiness Scheduling
- Minimizing the number of tardy job units under release time constraints
- Multiagent scheduling. Models and algorithms
- Multiplicity and complexity issues in contemporary production scheduling
- Parallel machine scheduling with high multiplicity
- Parametric problem in scheduling theory
- Scheduling with time dependent processing times: Review and extensions
- Single machine scheduling with learning effect considerations
- Single-machine scheduling and due date assignment with rejection and position-dependent processing times
- Single-machine scheduling problems with actual time-dependent and job-dependent learning effect
- Single-machine scheduling with learning considerations
- Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
- Time-dependent scheduling
- Unrelated parallel-machine scheduling with position-dependent deteriorating jobs and resource-dependent processing time
- ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
Cited in
(6)- Easy NP-hardness Proofs of Some Subset Choice Problems
- On the complexity of constructing a minmax regret solution for the two-machine flow shop problem under the interval uncertainty
- Scheduling lower bounds via AND subset sum
- A generic approach to proving NP-hardness of partition type problems
- A review of four decades of time-dependent scheduling: main results, new topics, and open problems
- Reoptimization of NP-Hard Problems
This page was built for publication: An alternative approach for proving the NP-hardness of optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q320621)
