Priority algorithms for the subset-sum problem

DOI10.1007/s10878-007-9126-9zbMath1170.90442OpenAlexW2919974563MaRDI QIDQ1029701

Allan Borodin, Yuli Ye

Publication date: 13 July 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9126-9

zbMATH Keywords

approximation algorithmgreedyrevocable acceptance

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Integer programming (90C10)

Related Items (4)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ On exponential time lower bound of Knapsack under backtracking ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Priority algorithms for graph optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on scheduling equal-length jobs to maximize throughput
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• On-line scheduling revisited
• (Incremental) priority algorithms
• Priority algorithms for makespan minimization in the subset model.
• The power of priority algorithms for facility location and set cover
• Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
• Approximating the Throughput of Multiple Machines in Real-Time Scheduling
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Interval selection: Applications, algorithms, and lower bounds
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Bounds for Certain Multiprocessing Anomalies
• Approximation and Online Algorithms

This page was built for publication: Priority algorithms for the subset-sum problem