pith. sign in

arxiv: 2605.05233 · v1 · submitted 2026-04-30 · 💻 cs.DS

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems

Lin Chen , Tingwei Hu , Yuchen Mao , Yong Chen , Lili Mei , An Zhang , Guangting Chen , Guochuan Zhang This is my paper

Pith reviewed 2026-05-09 20:44 UTC · model grok-4.3

classification 💻 cs.DS
keywords bottleneck knapsackmultiple knapsackapproximation algorithmssubset sumknapsack probleminapproximability
0
0 comments X

The pith

A (2/3 − ε)-approximation algorithm solves the bottleneck multiple knapsack problem for identical-capacity knapsacks, nearly matching the known hardness threshold.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The bottleneck multiple knapsack problem asks for an assignment of items to knapsacks that maximizes the smallest profit collected by any knapsack while respecting capacity limits. The paper constructs approximation algorithms for this balanced-profit objective. For the special case in which every knapsack has the same capacity, it delivers a polynomial-time algorithm achieving a (2/3 − ε) ratio for any fixed ε > 0. This guarantee comes within an arbitrarily small additive gap of the (2/3 + ε) inapproximability bound already known for the related bottleneck multiple subset-sum problem. When capacities may differ arbitrarily, the same work supplies a (1/2 − ε)-approximation together with a matching (1/2 + ε) hardness result.

Core claim

When all knapsacks share an identical capacity the authors give a deterministic polynomial-time algorithm whose minimum knapsack profit is at least (2/3 − ε) times the optimum; for arbitrary capacities they give a (1/2 − ε)-approximation and prove that no better ratio than (1/2 + ε) is possible unless P = NP.

What carries the argument

The algorithms combine item partitioning into large and small groups with dynamic-programming oracles for subset-sum and knapsack subproblems to search for balanced profit thresholds across the knapsacks.

If this is right

  • The identical-capacity variant can be solved to within an arbitrarily small gap from the best possible polynomial-time guarantee.
  • The arbitrary-capacity variant admits a tight constant-factor approximation up to the ε term.
  • The results distinguish the computational difficulty of maximizing minimum profit from the classical total-profit maximization setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same partitioning-plus-dp approach may apply to other bottleneck objectives in scheduling or load balancing.
  • The 2/3 threshold appears fundamental once capacities are forced to be equal.
  • Extensions to randomized algorithms or smoothed analysis could be tested on the same problem family.

Load-bearing premise

The running time may depend exponentially on 1/ε while ε itself remains a fixed positive constant independent of the input size.

What would settle it

A family of identical-capacity instances on which every polynomial-time algorithm returns a minimum profit strictly less than (2/3 − 0.01) times the optimum would disprove the (2/3 − ε) claim.

read the original abstract

In the bottleneck multiple knapsack problem, we are given a set of items and a set of knapsacks, where each item has a profit and a weight, and each knapsack has a capacity. Our goal is to assign items to knapsacks so as to maximize the minimum profit received by any knapsack subject to the capacity constraint. When all knapsacks have identical capacity, we give a $(\frac{2}{3} - \varepsilon)$-approximation algorithm for any constant $\varepsilon > 0$. This result almost matches the $(\frac{2}{3} + \varepsilon)$ inapproximability bound for the bottleneck multiple subset sum problem (Caprara et al., 2000). When the knapsacks can have arbitrary capacities, we propose a $(\frac{1}{2} - \varepsilon)$-approximation algorithm for any constant $\varepsilon > 0$. We also prove a hardness bound of $(\frac{1}{2} + \varepsilon)$ for any constant $\varepsilon > 0$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper studies the bottleneck multiple knapsack problem (BMKP), where the objective is to assign items to knapsacks to maximize the minimum profit across knapsacks subject to capacity constraints. For the identical-capacity case, the authors claim a (2/3 − ε)-approximation algorithm for any constant ε > 0 that nearly matches the (2/3 + ε) inapproximability bound known for the bottleneck multiple subset-sum special case (Caprara et al., 2000). For arbitrary capacities, they claim a (1/2 − ε)-approximation algorithm together with a matching (1/2 + ε) hardness result.

Significance. If the claimed ratios and hardness results hold, the work is a solid contribution to approximation algorithms for multiple-knapsack variants. It closes the gap to known hardness thresholds up to an arbitrary constant ε in both the identical-capacity and general cases, using standard techniques such as threshold guessing, polynomial-time oracles for subset-sum/knapsack subproblems, and ε-parameterized case analysis. The explicit provision of both algorithmic guarantees and matching hardness proofs strengthens the assessment; the results are parameter-free in the sense that the ratios depend only on ε and not on instance-specific fitted constants.

minor comments (1)
  1. [Abstract / Theorem statements] The abstract states that the algorithms run in polynomial time for any fixed ε > 0; the full manuscript should explicitly state the dependence of the running time on 1/ε (e.g., whether it is n^{O(1/ε)} or worse) in the theorem statements.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, accurate summary of our results, and recommendation to accept. The report correctly identifies that our algorithms achieve near-tight ratios (2/3−ε for identical capacities and 1/2−ε for arbitrary capacities) matching the known hardness thresholds up to an arbitrary ε>0.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper presents explicit approximation algorithms for the bottleneck multiple knapsack problem, deriving a (2/3 − ε)-approximation for identical-capacity instances that nearly matches an external hardness result from Caprara et al. (2000) and a (1/2 − ε)-approximation for arbitrary capacities with matching hardness. These guarantees rest on standard algorithmic techniques including threshold guessing, case analysis, and polynomial-time oracles for subset-sum and knapsack subproblems. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the central claims are independent algorithmic results rather than renamings or tautologies. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard axioms of polynomial-time computation and the existence of efficient oracles for subset-sum subproblems; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard model of deterministic polynomial-time algorithms and approximation ratios
    Implicit throughout the field of approximation algorithms.

pith-pipeline@v0.9.0 · 5497 in / 1193 out tokens · 56207 ms · 2026-05-09T20:44:03.096069+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

96 extracted references · 30 canonical work pages

  1. [1]

    Proceedings of the 1st International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX) , pages =

    Approximation schemes for covering and scheduling in related machines , author =. Proceedings of the 1st International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX) , pages =. 1998 , timestamp =. doi:10.1007/BFb0053962 , publisher =

    work page doi:10.1007/bfb0053962 1998

  2. [2]

    Nikhil Bansal and Maxim Sviridenko , booktitle =. The. 2006 , timestamp =. doi:10.1145/1132516.1132522 , publisher =

    work page doi:10.1145/1132516.1132522 2006

  3. [3]

    ACM SIGecom Exchanges , volume =

    Allocating indivisible goods , author =. ACM SIGecom Exchanges , volume =. 2005 , timestamp =. doi:10.1145/1120680.1120683 , _bib2doi_selected =

    work page doi:10.1145/1120680.1120683 2005

  4. [4]

    Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) , pages =

    Fair division under cardinality constraints , author =. Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) , pages =. 2018 , timestamp =. doi:10.24963/ijcai.2018/13 , _bib2doi_selected =

    work page doi:10.24963/ijcai.2018/13 2018

  5. [5]

    SIAM Journal on Optimization , volume =

    The multiple subset sum problem , author =. SIAM Journal on Optimization , volume =. 2000 , timestamp =. doi:10.1137/S1052623498348481 , _bib2doi_selected =

    work page doi:10.1137/s1052623498348481 2000

  6. [6]

    Alberto Caprara and Hans Kellerer and Ulrich Pferschy , journal =. A. 2000 , timestamp =. doi:10.1016/S0020-0190(00)00010-7 , _bib2doi_selected =

    work page doi:10.1016/s0020-0190(00)00010-7 2000

  7. [7]

    Journal of Heuristics , volume =

    A 3/4-approximation algorithm for multiple subset sum , author =. Journal of Heuristics , volume =. 2003 , timestamp =. doi:10.1023/A:1022584312032 , _bib2doi_selected =

    work page doi:10.1023/a:1022584312032 2003

  8. [8]

    Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =

    On allocating goods to maximize fairness , author =. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =. 2009 , timestamp =. doi:10.1109/FOCS.2009.51 , _bib2doi_selected =

    work page doi:10.1109/focs.2009.51 2009

  9. [9]

    SIAM Journal on Computing , volume =

    A polynomial time approximation scheme for the multiple knapsack problem , author =. SIAM Journal on Computing , volume =. 2005 , timestamp =. doi:10.1137/S0097539700382820 , _bib2doi_selected =

    work page doi:10.1137/s0097539700382820 2005

  10. [10]

    Optimization Letters , pages =

    The budgeted maximin share allocation problem , author =. Optimization Letters , pages =. 2025 , timestamp =. doi:10.1007/s11590-024-02145-6 , number =

    work page doi:10.1007/s11590-024-02145-6 2025

  11. [11]

    Algorithmica , volume =

    Approximation schemes for scheduling on uniformly related and identical parallel machines , author =. Algorithmica , volume =. 2004 , timestamp =. doi:10.1007/s00453-003-1077-7 , _bib2doi_selected =

    work page doi:10.1007/s00453-003-1077-7 2004

  12. [12]

    Combinatorica 1(4), 349–355 (1981).https://doi.org/10.1007/BF02579456

    Bin packing can be solved within 1+ in linear time , author =. Combinatorica , volume =. 1981 , timestamp =. doi:10.1007/BF02579456 , _bib2doi_selected =

    work page doi:10.1007/bf02579456 1981

  13. [13]

    Proceedings of the International Conference on Algorithms and Complexity (CIAC) , pages =

    Approximate maximin share allocations in matroids , author =. Proceedings of the International Conference on Algorithms and Complexity (CIAC) , pages =. 2017 , organization =. doi:10.1007/978-3-319-57586-5_26 , volume =

    work page doi:10.1007/978-3-319-57586-5_26 2017

  14. [14]

    Theoretical Computer Science , volume =

    On maximin share allocations in matroids , author =. Theoretical Computer Science , volume =. 2019 , publisher =. doi:10.1016/j.tcs.2018.05.018 , _bib2doi_selected =

    work page doi:10.1016/j.tcs.2018.05.018 2019

  15. [15]

    Journal of the ACM (JACM) , volume =

    Using dual approximation algorithms for scheduling problems theoretical and practical results , author =. Journal of the ACM (JACM) , volume =. 1987 , publisher =. doi:10.1145/7531.7535 , _bib2doi_selected =

    work page doi:10.1145/7531.7535 1987

  16. [16]

    and Karp, Richard M

    John E. Hopcroft and Richard M. Karp , journal =. An n^. 1973 , timestamp =. doi:10.1137/0202019 , _bib2doi_selected =

    work page doi:10.1137/0202019 1973

  17. [17]

    ACM Transactions on Economics and Computation , volume =

    Maximin shares in hereditary set systems , author =. ACM Transactions on Economics and Computation , volume =. 2025 , publisher =. doi:10.1145/3727149 , _bib2doi_selected =

    work page doi:10.1145/3727149 2025

  18. [18]

    Proceedings of the European Conference on Multi-Agent Systems (EUMAS) , pages =

    Maximin shares under cardinality constraints , author =. Proceedings of the European Conference on Multi-Agent Systems (EUMAS) , pages =. 2022 , organization =. doi:10.1007/978-3-031-20614-6_11 , volume =

    work page doi:10.1007/978-3-031-20614-6_11 2022

  19. [19]

    SIAM Journal on Computing , volume =

    Parameterized approximation scheme for the multiple knapsack problem , author =. SIAM Journal on Computing , volume =. 2009 , timestamp =. doi:10.1137/080731207 , _bib2doi_selected =

    work page doi:10.1137/080731207 2009

  20. [20]

    Proceedings of the 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) , pages =

    A fast approximation scheme for the multiple knapsack problem , author =. Proceedings of the 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) , pages =. 2012 , timestamp =. doi:10.1007/978-3-642-27660-6_26 , publisher =

    work page doi:10.1007/978-3-642-27660-6_26 2012

  21. [21]

    Minkowski's Convex Body Theorem and Integer Programming , volume =

    Ravi Kannan , journal =. Minkowski's Convex Body Theorem and Integer Programming , volume =. 1987 , timestamp =. doi:10.1287/moor.12.3.415 , _bib2doi_selected =

    work page doi:10.1287/moor.12.3.415 1987

  22. [22]

    Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX) , pages =

    A polynomial time approximation scheme for the multiple knapsack problem , author =. Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX) , pages =. 1999 , timestamp =. doi:10.1007/978-3-540-48413-4_6 , publisher =

    work page doi:10.1007/978-3-540-48413-4_6 1999

  23. [23]

    Algorithmica , volume =

    Polynomial-time Combinatorial Algorithm for General Max--Min Fair Allocation , author =. Algorithmica , volume =. 2024 , timestamp =. doi:10.1007/s00453-023-01105-3 , _bib2doi_selected =

    work page doi:10.1007/s00453-023-01105-3 2024

  24. [24]

    Shmoys and

    Jan Karel Lenstra and David B. Shmoys and. Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS) , title =. 1987 , pages =. doi:10.1109/SFCS.1987.8 , timestamp =

    work page doi:10.1109/sfcs.1987.8 1987

  25. [25]

    Mathematical Programming , volume =

    Approximation algorithms for scheduling unrelated parallel machines , author =. Mathematical Programming , volume =. 1990 , publisher =. doi:10.1007/BF01585745 , _bib2doi_selected =

    work page doi:10.1007/bf01585745 1990

  26. [26]

    Random Structures & Algorithms , volume =

    A new approximation technique for resource-allocation problems , author =. Random Structures & Algorithms , volume =. 2018 , timestamp =. doi:10.1002/rsa.20756 , _bib2doi_selected =

    work page doi:10.1002/rsa.20756 2018

  27. [27]

    2011 , publisher =

    The design of approximation algorithms , author =. 2011 , publisher =

    2011

  28. [28]

    Operations Research Letters , volume =

    A polynomial-time approximation scheme for maximizing the minimum machine completion time , author =. Operations Research Letters , volume =. 1997 , timestamp =. doi:10.1016/S0167-6377(96)00055-7 , _bib2doi_selected =

    work page doi:10.1016/s0167-6377(96)00055-7 1997

  29. [29]

    Journal of Scheduling , volume =

    Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard , author =. Journal of Scheduling , volume =. 2004 , publisher =. doi:10.1023/B:JOSH.0000036858.59787.c2 , number =

    work page doi:10.1023/b:josh.0000036858.59787.c2 2004

  30. [30]

    SIAM Journal on Optimization , volume=

    The multiple subset sum problem , author=. SIAM Journal on Optimization , volume=

  31. [31]

    Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , volume=

    Tight approximation algorithms for maximum general assignment problems , author=. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , volume=

  32. [32]

    ACM Transactions on Economics and Computation , volume=

    Maximin shares in hereditary set systems , author=. ACM Transactions on Economics and Computation , volume=. 2025 , publisher=

    2025

  33. [33]

    Optimization Letters , pages=

    The budgeted maximin share allocation problem , author=. Optimization Letters , pages=

  34. [34]

    SIAM Journal on Computing , volume=

    A polynomial time approximation scheme for the multiple knapsack problem , author=. SIAM Journal on Computing , volume=

  35. [35]

    Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) , pages=

    A fast approximation scheme for the multiple knapsack problem , author=. Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) , pages=

  36. [36]

    Caprara, Alberto and Kellerer, Hans and Pferschy, Ulrich , journal=. A

  37. [37]

    1990 , publisher=

    Knapsack problems: algorithms and computer implementations , author=. 1990 , publisher=

    1990

  38. [38]

    2004 , publisher=

    Knapsack problems , author=. 2004 , publisher=

    2004

  39. [39]

    Naval Research Logistics (NRL) , volume=

    Multiple subset sum with inclusive assignment set restrictions , author=. Naval Research Logistics (NRL) , volume=

  40. [40]

    International Journal of Operational Research , volume=

    Heuristics for the multiple knapsack problem with conflicts , author=. International Journal of Operational Research , volume=

  41. [41]

    Information Processing Society of Japan Journal , volume=

    Heuristic and exact algorithms for the disjunctively constrained knapsack problem , author=. Information Processing Society of Japan Journal , volume=

  42. [42]

    The knapsack problem with conflict graphs , author=. J. Graph Algorithms Appl. , volume=

  43. [43]

    Operations Research Letters , volume=

    A polynomial-time approximation scheme for maximizing the minimum machine completion time , author=. Operations Research Letters , volume=

  44. [44]

    Proceedings of the 1st International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX) , pages=

    Approximation schemes for covering and scheduling in related machines , author=. Proceedings of the 1st International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX) , pages=

  45. [45]

    Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages=

    On allocating goods to maximize fairness , author=. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages=

  46. [46]

    Algorithmica , volume=

    Restricted max-min allocation: Integrality gap and approximation algorithm , author=. Algorithmica , volume=

  47. [47]

    Journal of Political Economy , volume=

    The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes , author=. Journal of Political Economy , volume=

  48. [48]

    Journal of the ACM , volume=

    Fair enough: Guaranteeing approximate maximin shares , author=. Journal of the ACM , volume=

  49. [49]

    Proceedings of the 19th ACM Conference on Economics and Computation (EC) , pages=

    Fair allocation of indivisible goods: Improvements and generalizations , author=. Proceedings of the 19th ACM Conference on Economics and Computation (EC) , pages=

  50. [50]

    Proceedings of the 21st ACM Conference on Economics and Computation (EC) , pages=

    An improved approximation algorithm for maximin shares , author=. Proceedings of the 21st ACM Conference on Economics and Computation (EC) , pages=

  51. [51]

    Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Breaking the 3/4 barrier for approximate maximin share , author=. Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

  52. [52]

    Doklady Akademii Nauk SSSR , volume=

    A polynomial algorithm for linear programming , author=. Doklady Akademii Nauk SSSR , volume=

  53. [53]

    Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC) , pages=

    A new polynomial-time algorithm for linear programming , author=. Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC) , pages=

  54. [54]

    Hopcroft, John and Karp, Richard , journal=. An n^

  55. [55]

    SIAM Journal on Computing , volume=

    Parameterized approximation scheme for the multiple knapsack problem , author=. SIAM Journal on Computing , volume=

  56. [56]

    SIAM Journal on Discrete Mathematics , volume=

    Bounding the running time of algorithms for scheduling and packing problems , author=. SIAM Journal on Discrete Mathematics , volume=

  57. [57]

    Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    A quasi-PTAS for the two-dimensional geometric knapsack problem , author=. Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

  58. [58]

    Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC) , pages=

    A structural lemma in 2-dimensional packing, and its implications on approximability , author=. Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC) , pages=

  59. [59]

    European Journal of Operational Research , volume=

    Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses , author=. European Journal of Operational Research , volume=

  60. [60]

    Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages=

    Approximating geometric knapsack via L-packings , author=. Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages=

  61. [61]

    arXiv preprint arXiv:2103.10406 , year=

    Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple l-shapes, spirals, and more , author=. arXiv preprint arXiv:2103.10406 , year=

    work page arXiv

  62. [62]

    arXiv preprint arXiv:1906.10982 , year=

    Parameterized approximation schemes for independent set of rectangles and geometric knapsack , author=. arXiv preprint arXiv:1906.10982 , year=

    work page arXiv 1906

  63. [63]

    ACM Transactions on Algorithms , volume=

    Faster approximation schemes for the two-dimensional knapsack problem , author=. ACM Transactions on Algorithms , volume=

  64. [64]

    Information Processing Letters , volume=

    There is no EPTAS for two-dimensional knapsack , author=. Information Processing Letters , volume=

  65. [65]

    1997 , publisher=

    Introduction to linear optimization , author=. 1997 , publisher=

    1997

  66. [66]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC) , pages=

    A nearly quadratic-time FPTAS for knapsack , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC) , pages=

  67. [67]

    Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX) , pages=

    A polynomial time approximation scheme for the multiple knapsack problem , author=. Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX) , pages=

  68. [68]

    Journal of Heuristics , volume=

    A 3/4-approximation algorithm for multiple subset sum , author=. Journal of Heuristics , volume=

  69. [69]

    Journal of the ACM , volume=

    Approximate algorithms for the 0/1 knapsack problem , author=. Journal of the ACM , volume=

  70. [70]

    Journal of the ACM , volume=

    Fast approximation algorithms for the knapsack and sum of subset problems , author=. Journal of the ACM , volume=

  71. [71]

    Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) , year=

    An Improved FPTAS for 0-1 Knapsack , author=. Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) , year=

  72. [72]

    Mathematics of Operations Research , volume=

    Fast Approximation Algorithms for Knapsack Problems , author=. Mathematics of Operations Research , volume=

  73. [73]

    Journal of Combinatorial Optimization , volume=

    Improved dynamic programming in connection with an FPTAS for the knapsack problem , author=. Journal of Combinatorial Optimization , volume=

  74. [74]

    Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA) , year=

    Approximation schemes for 0-1 knapsack , author=. Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA) , year=

  75. [75]

    Algorithmica , volume=

    Approximation schemes for scheduling on uniformly related and identical parallel machines , author=. Algorithmica , volume=

  76. [76]

    INFORMS Journal on Computing , volume=

    When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? , author=. INFORMS Journal on Computing , volume=

  77. [77]

    Bansal, Nikhil and Sviridenko, Maxim , booktitle=. The

  78. [78]

    ACM SIGecom Exchanges , volume=

    Allocating indivisible goods , author=. ACM SIGecom Exchanges , volume=

  79. [79]

    Random Structures & Algorithms , volume=

    A new approximation technique for resource-allocation problems , author=. Random Structures & Algorithms , volume=

  80. [80]

    Algorithmica , volume=

    Polynomial-time Combinatorial Algorithm for General Max--Min Fair Allocation , author=. Algorithmica , volume=

Showing first 80 references.