A generic approach to proving NP-hardness of partition type problems
DOI10.1016/J.DAM.2010.08.001zbMATH Open1206.90147OpenAlexW1984508242MaRDI QIDQ608273FDOQ608273
Authors: Erwin Pesch, M. Y. Kovalyov 
Publication date: 25 November 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.08.001
Recommendations
- scientific article; zbMATH DE number 5799870
- An alternative approach for proving the NP-hardness of optimization problems
- scientific article; zbMATH DE number 1538871
- On the complexity of some partition problems
- An unconstrained optimization problem is NP-hard given an oracle representation of its objective function: a technical note
Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Minimization of half-products
- Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
- Algorithms for minclique scheduling problems
- Maximization problems in single machine scheduling
- ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
- Title not available (Why is that?)
- A scheduling problem with job values given as a power function of their completion times
- Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering
- Job sequencing with exponential functions of processing times
Cited In (9)
- The complexity of contracts
- Scheduling lower bounds via AND subset sum
- Efficient reductions and algorithms for subset product
- Almost periodic functions: their limit sets and various applications
- An alternative approach for proving the NP-hardness of optimization problems
- No existence of a linear algorithm for the one-dimensional Fourier phase retrieval
- On domain-partitioning induction criteria: worst-case bounds for the worst-case based
- The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
- Easy NP-hardness Proofs of Some Subset Choice Problems
This page was built for publication: A generic approach to proving NP-hardness of partition type problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q608273)
