General approximation algorithms for some arithmetical combinatorial problems

DOI10.1016/0304-3975(81)90047-5MaRDI QIDQ1158970zbMATH OpenOpenAlexFDO

Authors 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

NP-completeoptimization problemssubset 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)

Cites work

• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3551892 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3593565 (Why is no real title available?)
• Algorithms for Scheduling Independent Tasks
• Bounds on Multiprocessing Timing Anomalies
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• On the computational power of pushdown automata
• `` Strong NP-Completeness Results

Cited in

(4)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1158970)