General approximation algorithms for some arithmetical combinatorial problems

DOI10.1016/0304-3975(81)90047-5zbMath0474.68080OpenAlexW1980563498MaRDI QIDQ1158970

Shlomo Moran

Publication date: 1981

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(81)90047-5

zbMATH Keywords

optimization problemsNP-completesubset sum problemfull approximabilityjob sequencing with deadlinessubset product problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items (4)

Parallel approximation schemes for subset sum and knapsack problems ⋮ Non deterministic polynomial optimization problems and their approximations ⋮ ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation ⋮ The Complexity of Contracts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computational power of pushdown automata
• Algorithms for Scheduling Independent Tasks
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• `` Strong NP-Completeness Results
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: General approximation algorithms for some arithmetical combinatorial problems