A generic approach to proving NP-hardness of partition type problems

DOI10.1016/J.DAM.2010.08.001MaRDI QIDQ608273zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexitydiscrete optimizationscheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Integer programming (90C10) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

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

Cites work

• ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
• A scheduling problem with job values given as a power function of their completion times
• Algorithms for minclique scheduling problems
• Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering
• Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1264428 (Why is no real title available?)
• Job sequencing with exponential functions of processing times
• Maximization problems in single machine scheduling
• Minimization of half-products

Cited in

(11)

• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• On domain-partitioning induction criteria: worst-case bounds for the worst-case based
• Scheduling lower bounds via AND subset sum
• An alternative approach for proving the NP-hardness of optimization problems
• Easy NP-hardness Proofs of Some Subset Choice Problems
• The complexity of contracts
• Efficient reductions and algorithms for subset product
• No existence of a linear algorithm for the one-dimensional Fourier phase retrieval
• Almost periodic functions: their limit sets and various applications
• Scheduling lower bounds via and subset sum
• Algorithmic contract theory: a survey

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)