General approximation algorithms for some arithmetical combinatorial problems

DOI10.1016/0304-3975(81)90047-5zbMATH Open0474.68080OpenAlexW1980563498MaRDI QIDQ1158970FDOQ1158970

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms for Scheduling Independent Tasks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• On the computational power of pushdown automata
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Bounds on Multiprocessing Timing Anomalies
• `` Strong NP-Completeness Results
• Title not available (Why is that?)
• Title not available (Why is that?)

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)