The counting complexity of a simple scheduling problem

DOI10.1016/J.ORL.2009.05.004zbMath1173.90399OpenAlexW2032776320MaRDI QIDQ1038110

Gerardo Berbeglia

Publication date: 17 November 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2009.05.004

zbMATH Keywords

computational complexityschedulingcountingpolynomial interpolation\#P-complete

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (1)

Routing by ranking: a link analysis method for the constrained dial-a-ride problem

Cites Work

• The complexity of computing the permanent
• Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete
• The Complexity of Enumeration and Reliability Problems
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Counting and enumeration complexity with application to multicriteria scheduling

This page was built for publication: The counting complexity of a simple scheduling problem