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

DOI10.1016/j.dam.2010.08.001zbMath1206.90147OpenAlexW1984508242MaRDI QIDQ608273

Erwin Pesch, Mikhail 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 complexityschedulingdiscrete optimization

Mathematics Subject Classification ID

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

Related Items (4)

Scheduling lower bounds via AND subset sum ⋮ An alternative approach for proving the NP-hardness of optimization problems ⋮ Efficient reductions and algorithms for subset product ⋮ The Complexity of Contracts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximization problems in single machine scheduling
• Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering
• A scheduling problem with job values given as a power function of their completion times
• ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
• 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

This page was built for publication: A generic approach to proving NP-hardness of partition type problems