Pith. sign in

REVIEW 2 major objections 5 minor 47 references

Proportionally Fair Makespan Approximation

T0 review · 2 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that a payment-based proportional schedule can always reach 3/2 of the optimal makespan, and that no proportional mechanism can do better when n ≥ m.

desk verdict Tight 3/2 price of proportionality with payments is new and mostly right, but Theorem 1's proof has a repairable gap that should be fixed before publication. read the letter →

arxiv 2412.08572 v2 pith:YLP3F5YI submitted 2024-12-11 cs.GT

Michal Feldman , Jugal Garg , Vishnu V. Narayan , Tomasz Ponitka This is my paper · ORCID
classification cs.GT MSC 68W2590B3591B32
keywords jobschedulingunrelatedmachinesmakespanapproximationproportionalitymeanefficiencyfairdivisionofchoresmechanismdesignwithpaymentsegalitarianwelfare
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks how much makespan efficiency must be sacrificed when a scheduler also demands fairness toward the machines. Its answer: for the fairness notion of proportionality, the loss is exactly a factor of 3/2 — no more and no less. The positive half is a mechanism, the Anti-Diagonal Mechanism, that converts any schedule into a proportionable one while increasing makespan by at most 3/2. The negative half shows that when there are at least as many jobs as machines, every proportional mechanism must sometimes pay this full factor. The paper also shows that when every machine has the same total cost, a proportional mechanism can achieve the optimal makespan exactly, and it extends these ideas to the dual goods-allocation problem.

What carries the argument

The central object is mean efficiency (Definition 3.1), a budget on the total cost of an allocation, proved equivalent to proportionability in Theorem 6 and therefore the exact condition that payments must be able to fix. The main algorithmic engine is the Anti-Diagonal Mechanism (Algorithm 1): it reads any initial allocation, forms the $m \times m$ matrix of costs of each machine for each initial bundle, and picks the anti-diagonal with minimum total cost; because the average of anti-diagonal totals equals the average of the whole matrix, this choice is mean-efficient. Subsequent swap and merge operations lower the total cost, preserving mean efficiency, while a careful case analysis bounds every machine's final bundle cost by 3/2 times the input makespan. For normalized instances, the mechanism instead takes the makespan-minimizing allocation of minimal total cost and proves mean-efficiency through a directed graph with no cycles.

What would settle it

Take the cost matrix from Theorem 2's proof: entries 1 on the diagonal, 1/2 below the diagonal, and $3/2 - \epsilon/2$ above the diagonal, with $m = n$. If any proportional mechanism (using Definition 2.4) returns an allocation whose makespan is below $(3/2 - \epsilon)$, that would falsify the tightness claim; the paper's own argument shows such an allocation would have to be the identity allocation with total cost $m$, violating mean efficiency.

Watch

Extended reading notes

Core claim

The central claim is a tight equivalence between fairness and efficiency. An allocation function is proportionable — meaning it can be paired with payments so that each machine's net cost is at most its average share — if and only if it is mean-efficient: the total cost of the allocation is no larger than the average row cost of the cost matrix times the number of machines. The theorem comes with an explicit payment formula, $p_i = c_i(A_i) - (1/m)c_i([n])$, that realizes proportionality. On top of this characterization sits the Anti-Diagonal Mechanism, which selects a cost-minimizing anti-diagonal of the matrix of machine costs under the initial allocation, then applies swap and merge operations that preserve mean-efficiency while capping makespan at 3/2 of the initial schedule's makespan. For normalized instances the paper shows the cheapest makespan-optimal allocation is mean-efficient, giving an exact proportional mechanism.

Load-bearing premise

The whole result rests on Definition 2.4's notion of proportionality, where machine i's fair share is computed from i's own costs minus the average payment; if one uses another definition of proportional fairness, the 3/2 bound is not shown to hold.

Editorial extensions

If this is right

  • The price of proportionality for makespan is exactly 3/2: Theorem 1's mechanism achieves it and Theorem 2's instance rules out any $(3/2 - \epsilon)$-approximation when $n \ge m$.
  • Feeding the Anti-Diagonal Mechanism with the polynomial-time 2-approximation of [37] yields a polynomial-time proportional mechanism with a 3-approximation to the optimal makespan.
  • Under normalized costs, proportionality costs nothing in efficiency: a proportional mechanism attains the optimal makespan, while envy-free mechanisms still incur a logarithmic loss.
  • For the goods-allocation counterpart (maximizing egalitarian welfare), no proportional mechanism can guarantee any finite approximation in general, but normalized instances admit an exact proportional mechanism.
  • The cyclic lower-bound technique behind the envy-free impossibility does not extend to approximate envy-freeness: for every $\epsilon > 0$ there is a $(1-\epsilon)$-cyclic-envy-free mechanism with $1/\epsilon$ makespan approximation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The 3/2 ratio matches the classic inapproximability threshold for makespan minimization without any fairness constraint, which suggests that in this payment model proportionality may not be the binding obstacle to efficiency.
  • Because the characterization equates proportionality with an average-cost bound, fair scheduling is effectively a bicriteria problem: fairness is guaranteed as soon as total cost is controlled, so future work can focus on allocations that simultaneously control makespan and average cost.
  • The exactness for normalized instances hints that settings with comparable total costs may be qualitatively easier for fair mechanisms; a natural test is whether other fairness relaxations, such as EF1 or EFX with payments, also become constant-factor or exact in that regime.
  • The lower-bound instance is highly structured, almost a triangular matrix; exploring perturbations of it could show whether 3/2 is stable or an artifact of extreme cost asymmetry.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies fair mechanisms for unrelated-machine scheduling, viewing jobs as chores and machines as agents, in a quasi-linear model with payments. It defines proportionality (Definition 2.4) and characterizes proportionable allocations by a mean-efficiency condition (Theorem 6). The main results are a proportional mechanism with a 3/2 makespan approximation for general instances (Theorem 1), a matching lower bound (Theorem 2), an exact proportional mechanism for normalized instances (Theorem 3), analogous results for goods allocation (Theorems 4 and 5), a characterization of approximately envy-freeable allocations (Theorem 8), and a result showing that the known envy-free lower-bound technique does not extend to approximate cyclic envy-freeness (Theorem 9).

Significance. If the main theorem is established, the paper gives a striking contrast with the logarithmic impossibility for envy-freeness: proportionality with payments has a tight constant price of fairness, 3/2, for the makespan objective. The mean-efficiency characterization is elegant and reduces proportionality to a simple total-cost condition with an explicit payment formula. The lower-bound construction is explicit and the normalized-instance exact result is a clean graph argument. The goods-allocation and approximate-envy-freeness results broaden the scope. However, the proof of Theorem 1 as written contains a genuine gap, so the central upper bound is not yet established; the gap appears local and repairable. All results are tied to the paper's specific Definition 2.4, and alternative payment-aware proportionality notions would not automatically inherit these bounds.

major comments (2)
  1. [Section 4.1, proof of Theorem 1] The case analysis for A_l = B_l ∪ B_h is incomplete. The text asserts that the only way A_l can become B_l ∪ B_h is the merge in Line 10 at iteration i = l. This is false: if at iteration i = h the merge in Line 10 creates A_h = B_l ∪ B_h and sets A_l = ∅, then at the later iteration i = l the swap in Line 7 can move that union into A_l. The written proof contains no bound on c_l(B_l ∪ B_h) for this path. The gap is repairable: the merge at i = h gives c_h(B_l ∪ B_h) ≤ 3M/2, and the swap at i = l is executed only if c_l(A_h) + c_h(A_l) < c_l(A_l) + c_h(A_h); since A_l = ∅ in this path, that inequality yields c_l(B_l ∪ B_h) < c_h(B_l ∪ B_h) ≤ 3M/2. The proof should include this case explicitly.
  2. [Section 4.1, proof of Theorem 1, final case] The contradiction step in the final case is not written correctly. The displayed inequality c_h(B_l) < c_l(B_l) does not by itself imply that the merge condition in Line 10 was met at iteration i = h; with no prior swap, that condition is c_h(B_h) < c_l(B_h), not c_h(B_l) < c_l(B_l). The intended contradiction does follow, but from the two facts c_h(B_h) ≤ M < 3M/2 < c_l(B_h) and c_h(B_l) ≤ M/2, which together give c_h(B_h) < c_l(B_h) and c_h(B_h) + c_h(B_l) ≤ 3M/2. The proof should be rewritten to state this reasoning explicitly.
minor comments (5)
  1. [Section 4.2, proof of Theorem 3] In the normalization argument, the text writes c_i([m]) where it should write c_i([n]); additionally, the displayed inequality in the cycle argument contains a self-comparison c_{i_j}(A_{i_j}) < c_{i_j}(A_{i_j}), which should read c_{i_{j+1}}(A_{i_j}) < c_{i_j}(A_{i_j}). The intended argument is clear, but these typos should be fixed.
  2. [Section 5, proof of Theorem 4] In the proof of Theorem 4, the average of the values for good m is (m^2 + m + 1)/m = m + 1 + 1/m, not m + 1 as printed. The conclusion is unaffected because this value is still greater than m.
  3. [Section 6, Definition 6.4 and Theorem 9] The phrase 'stronger version of envy-freeness' is misleading: α-cyclic-envy-freeness imposes constraints only between adjacent machines in a cycle, so it is a weaker condition than envy-freeness. The intended statement is that the lower bound is strengthened because it holds even for a weaker fairness notion; the wording should be adjusted.
  4. [Section 4.1, proof of Theorem 1] The assertion that if A_l = B_h at the end then A_l and A_h were neither swapped nor merged in the iterations with i = l or i = h is stated without justification. It is true, because a swap at i = h would make the reverse swap at i = l impossible (the two swap inequalities are mutually exclusive), and a merge at either iteration would change A_l away from B_h, but the proof should say so.
  5. [Section 4.1, Algorithm 2] The termination of Algorithm 2 is not argued. Termination follows because each reallocation strictly decreases the total cost Σ_i c_i(A_i), so the algorithm cannot cycle; this should be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: main results are derived from first principles; self-citations are contextual, not load-bearing.

full rationale

The central claims are proved from first principles. Theorem 6 is established by summing the proportionality inequalities and by an explicit payment construction p_i = c_i(A_i) - (1/m)c_i([n]); neither direction imports an external result. The Anti-Diagonal Mechanism's proportionality follows directly from k being the minimizer of the anti-diagonal sums plus the fact that swaps and merges only decrease total cost, and the 3/2 bound is a case analysis on the possible contents of A_l. The lower bound (Theorem 2) uses Theorem 6 and an explicit cost matrix with a forced identity allocation, so it is not fitted or definitional. Theorem 3's normalized-instance result is self-contained via an acyclicity argument, and Theorem 4 uses an explicit instance plus Corollary 5.3. Citations to work by the present authors ([23], [10], [28]) occur as background, comparison benchmarks, or as part of a list of known characterizations, and none is a premise of the main theorems. The only passage needing scrutiny is the Theorem 1 proof's assertion that 'the only way for A_l to be set to B_l union B_h is in the merge operation in Line 10 during the iteration with i = l'; if false, that is a correctness gap in a written case analysis, not a circular reduction of the conclusion to the inputs. No parameter fitting, renamed prediction, or imported uniqueness theorem appears.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on four explicit modeling assumptions (quasi-linearity, additivity, the specific proportionality benchmark, and unrestricted payments), none of which is ad hoc in a way that hides the result. There are no free parameters or invented entities.

assumptions (4)
  • domain assumption Machines have quasi-linear disutilities: disutility equals cost minus payment (Section 2.2).
    This is the standard utility model in mechanism design; the paper's fairness definitions and payment formulas are built on it.
  • domain assumption Costs are additive over jobs (Section 2.1).
    The makespan is the sum of per-job costs; all proofs of mean efficiency use additivity.
  • domain assumption Proportionality is defined by comparing machine i's net cost to the average of machine i's own costs over all bundles, with payments included (Definition 2.4).
    This specific benchmark is what makes mean efficiency equivalent to proportionability. An alternative proportionality notion without this benchmark would change the results.
  • domain assumption Payments are unrestricted real numbers and can be negative or positive (Definition 2.2).
    The payment formula p_i = c_i(A_i) - (1/m)c_i([n]) can sum to a negative total; unrestricted payments are needed for the characterization.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Proportionally Fair Makespan Approximation." pith.science (2026). https://pith.science/paper/YLP3F5YI

@misc{pith2026241208572,
  author       = {Pith},
  title        = {Pith review of: Proportionally Fair Makespan Approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YLP3F5YI}},
  note         = {Machine review of arXiv:2412.08572}
}
abstract

We study fair mechanisms for the classic job scheduling problem on unrelated machines with the objective of minimizing the makespan. This problem is equivalent to minimizing the egalitarian social cost in the fair division of chores. The two prevalent fairness notions in the fair division literature are envy-freeness and proportionality. Prior work has established that no envy-free mechanism can provide better than an $\Omega(\log m/ \log \log m)$-approximation to the optimal makespan, where $m$ is the number of machines, even when payments to the machines are allowed. In strong contrast to this impossibility, our main result demonstrates that there exists a proportional mechanism (with payments) that achieves a $3/2$-approximation to the optimal makespan, and this ratio is tight. To prove this result, we provide a full characterization of allocation functions that can be made proportional with payments. Furthermore, we show that for instances with normalized costs, there exists a proportional mechanism that achieves the optimal makespan. We conclude with important directions for future research concerning other fairness notions, including relaxations of envy-freeness. Notably, we show that the technique leading to the impossibility result for envy-freeness does not extend to its relaxations.

Figures

Figures reproduced from arXiv: 2412.08572 by the authors.

Figure 1
Figure 1. Illustration of the Anti-Diagonal Mechanism for t [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 43 canonical work pages

  1. [1]

    Approximation schemes for scheduling on parallel machines

    Noga Alon, Yossi Azar, Gerhard J Woeginger, and Tal Yadid . Approximation schemes for scheduling on parallel machines. Journal of Scheduling , 1(1):55–66, 1998

    work page 1998

  2. [2]

    Fair division of indivisib le goods: Recent progress and open questions

    Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Ari s Filos-Ratsikas, Bo Li, Hervé Moulin, Alexan- dros A Voudouris, and Xiaowei Wu. Fair division of indivisib le goods: Recent progress and open questions. Artificial Intelligence , 322:103965, 2023

    2023

  3. [3]

    A derivation of the money rawlsian s olution

    Enriqueta Aragones. A derivation of the money rawlsian s olution. Social Choice and Welfare , 12(3): 267–276, 1995

    work page 1995

  4. [4]

    Aslam, April Rasala, Clifford Stein, and Neal E

    Javed A. Aslam, April Rasala, Clifford Stein, and Neal E. Y oung. Improved bicriteria existence theorems for scheduling. In SODA, pages 846–847. ACM/SIAM, 1999

    work page 1999

  5. [5]

    Optim al bounds on the price of fairness for indivisible goods

    Siddharth Barman, Umang Bhaskar, and Nisarg Shah. Optim al bounds on the price of fairness for indivisible goods. In International Conference on Web and Internet Economics , pages 356–369. Springer, 2020

    work page 2020

  6. [6]

    Achieving envy- freeness with limited subsidies under dichotomous valuati ons

    Siddharth Barman, Anand Krishna, Yadati Narahari, and S oumyarup Sadhukhan. Achieving envy- freeness with limited subsidies under dichotomous valuati ons. In Proceedings of the Thirty-First Inter- national Joint Conference on Artificial Intelligence, IJCAI-22 , pages 60–66, 2022

    work page 2022

  7. [7]

    The price of fairness for indivis- ible goods

    Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, and Warut Suk sompong. The price of fairness for indivis- ible goods. Theory of Computing Systems , 65:1069–1093, 2021

    work page 2021

  8. [8]

    The price of fairness

    Dimitris Bertsimas, Vivek F Farias, and Nikolaos Tricha kis. The price of fairness. Operations research, 59(1):17–31, 2011. 14

    work page 2011

Show all 47 references
  1. [9]

    The price of envy-freeness in machine scheduling

    Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianp iero Monaco, and Luca Moscardelli. The price of envy-freeness in machine scheduling. Theor. Comput. Sci. , 613:65–78, 2016

    2016

  2. [10]

    Narayan, Mash bat Suzuki, and Adrian Vetta

    Johannes Brustle, Jack Dippel, Vishnu V. Narayan, Mash bat Suzuki, and Adrian Vetta. One dollar each eliminates envy. In EC, pages 23–39. ACM, 2020

    2020

  3. [11]

    On the complexity of maximizing social welfare within fair allocations of indivisible good s

    Xiaolin Bu, Zihao Li, Shengxin Liu, Jiaxin Song, and Bia oshuai Tao. On the complexity of maximizing social welfare within fair allocations of indivisible good s. CoRR, abs/2205.14296, 2022

    2022 arXiv

  4. [12]

    The combinatorial assignment problem: Ap proximate competitive equilibrium from equal incomes

    Eric Budish. The combinatorial assignment problem: Ap proximate competitive equilibrium from equal incomes. Journal of Political Economy , 119(6):1061 – 1103, 2011

    2011

  5. [13]

    Computin g envy-freeable allocations with limited subsi- dies

    Ioannis Caragiannis and Stavros D Ioannidis. Computin g envy-freeable allocations with limited subsi- dies. In International Conference on Web and Internet Economics , pages 522–539. Springer, 2021

    2021

  6. [14]

    The efficiency of fair division

    Ioannis Caragiannis, Christos Kaklamanis, Panagioti s Kanellopoulos, and Maria Kyropoulou. The efficiency of fair division. Theory of Computing Systems , 50:589–610, 2012

    2012

  7. [15]

    Envy- freeness up to any item with high nash welfare: The virtue of donating items

    Ioannis Caragiannis, Nick Gravin, and Xin Huang. Envy- freeness up to any item with high nash welfare: The virtue of donating items. In EC, pages 527–545. ACM, 2019

    2019

  8. [16]

    The unreasonable fairness of maximum nash welfare

    Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ar iel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC) , 7(3):1–32, 2019

    2019

  9. [17]

    Egalitarian price of fairness for indivisible goods

    Karen Frilya Celine, Muhammad Ayaz Dzulfikar, and Ivan A drian Koswara. Egalitarian price of fairness for indivisible goods. In Pacific Rim International Conference on Artificial Intelligence , pages 23–28. Springer, 2023

    2023

  10. [18]

    E fx exists for three agents

    Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. E fx exists for three agents. Journal of the ACM, 71(1):1–27, 2024

    2024

  11. [19]

    A lower bound for scheduling mecha- nisms

    George Christodoulou, Elias Koutsoupias, and Angelin a Vidali. A lower bound for scheduling mecha- nisms. In Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1163–1170. SIAM, 2007

    2007

  12. [20]

    On the nisan-ronen conjecture

    George Christodoulou, Elias Koutsoupias, and Annamár ia Kovács. On the nisan-ronen conjecture. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Sc ience (FOCS) , pages 839–850. IEEE, 2022

    2021

  13. [21]

    A proof of the Nisan-Ronen con- jecture

    George Christodoulou, Elias Koutsoupias, and Annamár ia Kovács. A proof of the Nisan-Ronen con- jecture. In Proceedings of the 55th Annual ACM Symposium on Theory of Comp uting, pages 672–685, 2023

    2023

  14. [22]

    An application of bin-packing to multiprocessor scheduling

    Edward G Coffman, Jr, Michael R Garey, and David S Johnson . An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing , 7(1):1–17, 1978

    1978

  15. [23]

    Envy-free makespan approximation

    Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, an d Svetlana Olonetsky. Envy-free makespan approximation. In Proceedings of the 11th ACM conference on Electronic commer ce (EC) , pages 159– 166, 2010

    2010

  16. [24]

    proportional chore-cut ting

    Wikipedia contributors. The "proportional chore-cut ting" section of the "chore division" article. https://en.wikipedia.org/wiki/Chore_division#Proportional_chore-cutting, n.d. Accessed: 2024-12-10

    2024

  17. [25]

    Improved lower bo unds for truthful scheduling

    Shahar Dobzinski and Ariel Shaulker. Improved lower bo unds for truthful scheduling. CoRR, abs/2007.04362, 2020

    2007 arXiv

  18. [26]

    Approximation schemes for scheduling on uniformly related and identical parallel machines

    Leah Epstein and Jiri Sgall. Approximation schemes for scheduling on uniformly related and identical parallel machines. Algorithmica, 39:43–57, 2004. 15

    2004

  19. [27]

    On the c omplexity of chore division

    Alireza Farhadi and MohammadTaghi Hajiaghayi. On the c omplexity of chore division. In IJCAI, pages 226–232. ijcai.org, 2018

    2018

  20. [28]

    On op timal tradeoffs between EFX and nash welfare

    Michal Feldman, Simon Mauras, and Tomasz Ponitka. On op timal tradeoffs between EFX and nash welfare. In AAAI, pages 9688–9695. AAAI Press, 2024

    2024

  21. [29]

    Tight lower bounds on envy-f ree makespan approximation

    Amos Fiat and Ariel Levavi. Tight lower bounds on envy-f ree makespan approximation. In WINE, volume 7695 of Lecture Notes in Computer Science , pages 553–558. Springer, 2012

    2012

  22. [30]

    D. Foley. Resource allocation and the public sector. Yale Econ Essays , 7(1):45–98, 1967

    1967

  23. [31]

    Bounds for certain multiprocessing an omalies

    Ronald L Graham. Bounds for certain multiprocessing an omalies. Bell system technical journal , 45(9): 1563–1581, 1966

    1966

  24. [32]

    Fair division with subs idy

    Daniel Halpern and Nisarg Shah. Fair division with subs idy. In SAGT, volume 11801 of Lecture Notes in Computer Science , pages 374–389. Springer, 2019

    2019

  25. [33]

    Multi-dimensional envy-free scheduling mechanisms

    Jason Hartline, Sam Ieong, Ahuva Mualem, Michael Schap ira, and A viv Zohar. Multi-dimensional envy-free scheduling mechanisms. Technical Report 1144, T he Hebrew University, 2008

    2008

  26. [34]

    Mertzios, Hend rik Molter, Rolf Niedermeier, and Dvir Shab- tay

    Klaus Heeger, Danny Hermelin, George B. Mertzios, Hend rik Molter, Rolf Niedermeier, and Dvir Shab- tay. Equitable scheduling on a single machine. J. Sched., 26(2):209–225, 2023

    2023

  27. [35]

    Exact and approximate algorithms for scheduling nonidentical proces- sors

    Ellis Horowitz and Sartaj Sahni. Exact and approximate algorithms for scheduling nonidentical proces- sors. Journal of the ACM (JACM) , 23(2):317–327, 1976

    1976

  28. [36]

    A lower bound of 1+phi for truthful scheduling mechanisms

    Elias Koutsoupias and Angelina Vidali. A lower bound of 1+phi for truthful scheduling mechanisms. In MFCS, volume 4708 of Lecture Notes in Computer Science , pages 454–464. Springer, 2007

    2007

  29. [37]

    Appro ximation algorithms for scheduling unre- lated parallel machines

    Jan Karel Lenstra, David B Shmoys, and Éva Tardos. Appro ximation algorithms for scheduling unre- lated parallel machines. Mathematical programming, 46:259–271, 1990

    1990

  30. [38]

    A complete landscape for the price of envy-freeness

    Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao, and Y ichen Tao. A complete landscape for the price of envy-freeness. In Proceedings of the 23rd International Conference on Autonomo us Agents and Multiagent Systems , pages 1183–1191, 2024

    2024

  31. [39]

    Mixed fair division: A survey

    Shengxin Liu, Xinhang Lu, Mashbat Suzuki, and Toby Wals h. Mixed fair division: A survey. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 38, pages 22641–22649, 2024

    2024

  32. [40]

    On the fair allocation of indivisible goo ds

    Eric S Maskin. On the fair allocation of indivisible goo ds. In Arrow and the Foundations of the Theory of Economic Policy , pages 341–349. Springer, 1987

    1987

  33. [41]

    Algorithmic mechanism desig n

    Noam Nisan and Amir Ronen. Algorithmic mechanism desig n. In Proceedings of the thirty-first annual ACM symposium on Theory of computing , pages 129–140, 1999

    1999

  34. [42]

    Existence theorems, lower bounds and algorithms for scheduling to meet two objectives

    April Rasala, Clifford Stein, Eric Torng, and Patchrawa t Uthaisombut. Existence theorems, lower bounds and algorithms for scheduling to meet two objectives . In SODA, pages 723–731. ACM/SIAM, 2002

    2002

  35. [43]

    Algorithms for scheduling independent tasks

    Sartaj K Sahni. Algorithms for scheduling independent tasks. Journal of the ACM (JACM) , 23(1): 116–127, 1976

    1976

  36. [44]

    On the existence of schedul es that are near-optimal for both makespan and total weighted completion time

    Clifford Stein and Joel Wein. On the existence of schedul es that are near-optimal for both makespan and total weighted completion time. Oper. Res. Lett. , 21(3):115–122, 1997

    1997

  37. [45]

    The problem of fair division

    Hugo Steinhaus. The problem of fair division. Econometrica, 16:101–104, 1948

    1948

  38. [46]

    One quarter e ach (on average) ensures proportionality

    Xiaowei Wu, Cong Zhang, and Shengwei Zhou. One quarter e ach (on average) ensures proportionality. In WINE, volume 14413 of Lecture Notes in Computer Science , pages 582–599. Springer, 2023

    2023

  39. [47]

    On the exact upper bound for the multifit proce ssor scheduling algorithm

    Minyi Yue. On the exact upper bound for the multifit proce ssor scheduling algorithm. Annals of Operations Research, 24(1):233–259, 1990. 16 A Missing Proofs Lemma 4.2. Fix α ∈ (0, 1] and β ∈ [1,∞). Suppose that there is an α-envy-free mechanism for the job scheduling problem o...

    1990

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.