Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Subadditive Load Balancing

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Subadditive load balancing gets a worst-case guarantee, with a curvature-aware bound for the modularization-minimization algorithm.

desk verdict Theorem 5's guarantee covers only the initial partition, not MMin's final output — a load-bearing overclaim — but the subadditivity proofs and lower-bound technique are solid and worth salvaging. read the letter →

arxiv 1908.09135 v1 pith:F7I3MFWR submitted 2019-08-24 cs.DS

Kiyohito Nagano , Akihiro Kishimoto This is my paper · ORCID
classification cs.DS MSC 68W2590C27
keywords subadditivesetfunctionsloadbalancingmodularization-minimizationapproximationfactorcurvaturemulti-robotroutingminimumspanningtreesubmodular
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

Subadditive set functions generalize submodular functions, but have resisted the approximation tools that make submodular load balancing tractable. This paper claims that a modularization-minimization algorithm, MMin, carries a worst-case approximation factor for the nondecreasing subadditive load-balancing problem, with the factor depending on the sizes of the optimal blocks and on the curvatures of the subadditive costs. The guarantee extends a line of analysis previously available only for submodular costs. The paper also gives lower-bound computations based on cost sharing and applies the algorithm to multi-robot routing, where the relevant cost is a minimum-spanning-tree function.

What carries the argument

The load-bearing object is the curvature $\kappa_g(S)=1-\min_{A\subseteq S,\, i\in A} \frac{g(i\mid A\setminus\{i\})}{g(\{i\})}$ of a nondecreasing nonnegative subadditive function, which measures how much singleton costs understate the cost of building a set. Around it, Lemma 7 gives the inequality that carries the approximation: for every $S\subseteq V$ with $0<\kappa_g(S)<1$, the singleton sum $\sum_{i\in S} g(\{i\})$ is sandwiched between $g(S)$ and $\frac{|S|}{1+(|S|-1)(1-\kappa_g(S))}g(S)$. MMin uses this by solving a modular load-balancing problem whose costs are singleton sums, then iterating with modular approximations built around the current partition. The sandwich inequality is what turns a solution of the modular surrogate into a solution of the subadditive problem.

What would settle it

Run MMin on a small subadditive load-balancing instance whose costs are minimum-spanning-tree functions, compute the initial partition $S^{(0)}$, perform one modularization-minimization iteration, and compare $\max_j g_j(S^{(1)})$ with $\max_j g_j(S^{(0)})$. If the objective strictly increases, the stated theorem cannot cover the algorithm's final output, since the proof bounds only $S^{(0)}$.

Watch

Extended reading notes

Core claim

The paper's central claim is that minimax subadditive load balancing admits a modularization-minimization algorithm with a worst-case approximation factor of $2 \cdot \max_{j\in[m]} \frac{|S^*_j|}{1+(|S^*_j|-1)(1-\kappa_{g_j}(S^*_j))}$, where $S^*$ is an optimal partition and $\kappa_{g_j}(S^*_j)$ is the curvature of the $j$-th subadditive cost at that block. The engine is the two-sided inequality $g(S) \le \sum_{i\in S} g(\{i\}) \le \frac{|S|}{1+(|S|-1)(1-\kappa_g(S))} g(S)$, which lets the optimality of a modular initial partition be transferred back to the original subadditive objective. The proof in Section 3.2 establishes the bound for the initial partition $S^{(0)}$ produced in Step 0; the paper notes in Section 7 that whether the iterative loop improves the worst-case factor remains open. Alongside this, the paper shows that unconstrained subadditive minimization and curvature computation are NP-hard, introduces a tractable pseudo-curvature, and gives cost-sharing-based lower bounds for the minimum-spanning-tree costs that arise in multi-robot routing.

Load-bearing premise

The proof of the worst-case factor applies only to the initial partition the algorithm starts from; the guarantee would also need the later update steps never to increase the objective, and the paper does not establish that.

Editorial extensions

If this is right

  • If Theorem 5 holds, every nondecreasing subadditive load-balancing instance with bounded curvature has a modular surrogate whose optimal partition is within the stated factor of optimal.
  • The result specializes to the submodular case, recovering the majorization-minimization guarantee as a special case for a broader class of costs.
  • For minimum-spanning-tree-based multi-robot routing, the lower-bound method gives a certificate of solution quality without solving the NP-hard routing problem itself.
  • Curvature values close to 1 make the factor approach $2\cdot\max_j |S^*_j|$, while smaller curvatures give sharper guarantees.
  • The NP-hardness of curvature computation means the stated factor is mostly existential; the algorithm itself never needs to evaluate the curvature.

Reading between the lines

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

  • If one could construct modular approximations that majorize the subadditive costs along the algorithm's trajectory, the proof would extend from the initial partition to the final output; a natural safeguard is to keep the best partition seen during iterations.
  • The interpolation construction suggests a practical recipe: replace a costly submodular function by its subadditive interpolation, solve the surrogate, and measure the quality gap empirically on feature selection or summarization tasks.
  • The pseudo-curvature for minimum-spanning-tree-plus-waiting-time costs could be substituted into the theorem's bound to get instance-dependent factors without computing the exact, NP-hard curvature.
  • The lower-bound framework is not tied to spanning-tree costs: any subadditive cost admitting a core-like vector with a bounded approximation ratio would yield a valid lower bound by the same argument.
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

3 major / 4 minor

Summary. The paper studies the minimax subadditive load balancing (SALB) problem, in which an m-partition of a ground set V minimizes the maximum value of m nonnegative subadditive set functions. It establishes subadditivity for several concrete functions (minimum spanning tree, facility location, and an interpolation construction), proposes the modularization-minimization algorithm MMin, and claims in Theorem 5 a curvature-dependent worst-case approximation factor for nondecreasing SALB. It also proves NP-hardness for unconstrained subadditive minimization and for curvature computation, introduces a pseudo-curvature, and evaluates the approach on a multi-robot routing problem with MST-based cost functions, including a lower-bound computation technique. The proof of the main approximation theorem, however, bounds only the initial partition computed in Step 0, not the final output of the iterative algorithm.

Significance. If the main theorem held for the output of MMin, the paper would provide the first worst-case guarantee for a majorization-minimization-type algorithm for subadditive load balancing, generalizing the result of Wei et al. to a broader class of set functions. The curvature-based bound for the initial partition appears correct and is a useful result in its own right; the lower-bound technique for MST-based SALB is concrete and is empirically evaluated; and the paper contains useful examples and observations about subadditive functions. However, the central claim as stated is not proven, and Section 7 explicitly leaves the effect of the iterative updates on the worst-case factor open. The contribution is therefore significant but currently incomplete.

major comments (3)
  1. [Section 3.2, Lemma 8 and Theorem 5] The proof of Theorem 5 only establishes the approximation factor for the initial partition S(0). After Step 0, MMin continues to iterate and outputs S(k) at termination, and the manuscript gives no argument that max_j g_j(S(k)_j) is no larger than max_j g_j(S(0)_j). The modular approximations used in Steps 1 and 2 are not majorizing functions; Section 3.1 and Appendix A.2 explicitly show that the natural analogues M_1 and M_2 fail to majorize g in the subadditive case, and Section 7 states that whether the iterative procedure contributes to improving the worst-case approximation factor remains unanswered. Since an iteration can in principle return a partition with a larger objective value, the guarantee in Theorem 5 for MMin as stated is unsupported. The theorem can be repaired by modifying the algorithm to output the best partition seen (including S(0)) and restating the proof accordingly, or by proving monotonicity of the objective under the modularization update in equation (5).
  2. [Section 3.2, Lemma 8 versus Theorem 5] Lemma 8 assumes that S(0) is an optimal partition of problem (6) and concludes that S(0) is a (max_j gamma*_j)-approximation solution, whereas Theorem 5 claims factor 2 times that quantity. The factor 2 presumably comes from the gamma_MLB-approximation algorithm used in Step 0, but Lemma 8 and its proof, in particular inequality (10), do not contain gamma_MLB. As written, the proof of Theorem 5 through Lemma 8 does not yield the stated factor. Lemma 8 should be restated with the gamma_MLB factor inserted, and inequality (10) should be adjusted accordingly.
  3. [Section 4.1, Theorem 10] The reduction for the NP-hardness of curvature computation constructs a subadditive function g with g({i*})=0 and with g not nondecreasing, but the curvature kappa_g(S) defined in Section 3.2 is for normalized nondecreasing subadditive functions with positive singleton values. The ratio in the curvature formula is therefore undefined at i* for the constructed function, so the proof does not establish NP-hardness for the class of functions to which the rest of the paper's curvature analysis applies. The reduction needs to be modified, for example by assigning a positive value to sets containing i* and arguing that the minimum in the curvature formula is controlled by the i* term.
minor comments (4)
  1. [Section 3.2, Theorem 5] In the statement of Theorem 5, the curvature is written as kappa_g(S*_j); the subscript j should be attached to g so that it reads kappa_{g_j}(S*_j).
  2. [Section 3.2, Lemma 7 proof] The proof of Lemma 7 refers to 'inequality (A1)', but the relevant display in the main text is inequality (8).
  3. [Section 3, Algorithm Greedy] In Algorithm Greedy, Step 1 chooses i_j from a set R that is not defined; it should presumably be the remaining target set U.
  4. [Section 3.1, Algorithm MMin and Section 6] The algorithm description gives the termination condition as S(k)=S(k-1), while the experimental section says MMin terminates when the value of the LP problem agrees with one from a previous iteration; the two termination conditions should be reconciled.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the approximation and lower-bound derivations are self-contained, with an acknowledged open proof gap that is a correctness issue rather than a circular step.

full rationale

The paper's main derivation chain is self-contained and does not feed its conclusions back into its inputs. Theorem 5's factor is proven by Lemmas 6-8, which use only the definition of curvature, subadditivity, and optimality of the initial modular problem (6); the bound on the initial partition follows from the inequality sum_{i in S*_j} g_j({i}) <= gamma^*_j g_j(S*_j) supplied by Lemma 7. No fitted parameter is later renamed as a prediction, and no quantity appearing in the theorem is defined in terms of the theorem's conclusion. The lower-bound method in Section 3.3 relies on Bird's cost-sharing for the MST game and Edmonds' greedy algorithm for polymatroids, both external and independently established; the paper even describes the greedy algorithm in detail to keep the argument self-contained. The empirical evaluation compares MMin, MMin+MST, MST, and Path on independently generated instances, and the pseudo-curvature in Section 4.2 is computed from the problem data, not from the results it is used to discuss. Self-citations are incidental (e.g., [29] in the introduction on clustering) and are not load-bearing. The skeptical concern about Theorem 5 is a genuine proof-to-algorithm gap, not circularity: as the paper itself states in Section 3.1, a majorizing modular function 'cannot be constructed' for subadditive functions, and Section 7 admits that 'the question whether or not the iterative procedure currently contributes to improving the worst-case approximation factor remains unanswered.' That limitation is explicitly flagged in the manuscript, but it concerns monotonicity of the iterates and the applicability of the bound to the final output, not a reduction of the result to its own assumptions. Accordingly, the circularity score is 0.

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

The paper introduces no fitted free parameters; the main theoretical results rely on standard metric and monotonicity assumptions on the set functions. The pseudo-curvature is a new defined quantity rather than a postulated entity, so it is not listed as an invented entity.

assumptions (5)
  • domain assumption Distance function d is symmetric and satisfies the triangle inequality (Section 2.2.1, Section 5).
    This is assumed for the minimum spanning tree function and for the multi-robot routing application; it is not proven but is standard for metric inputs.
  • domain assumption The functions g_1,...,g_m are normalized, nonnegative, and subadditive, with g_j({i}) > 0 for the curvature analysis (Section 3.2).
    The approximation factor and curvature definitions require these properties; they are stated as assumptions in the problem setup.
  • domain assumption For the pseudo-curvature of Section 4.2, g is assumed to decompose as g = g_+ + f_+ with g_+ (approximately) nondecreasing subadditive and f_+ nonnegative submodular or modular.
    This decomposition is not shown to exist for general subadditive functions; it is demonstrated only for specific cases such as MST_β.
  • standard math The greedy algorithm of Edmonds correctly optimizes linear objectives over a polymatroid (Section 3.3.3), and Bird's cost-sharing gives a core allocation for the MST game (Section 3.3.2).
    These are classical results cited from [7] and [5], used to construct minorization functions for lower bounds.
  • standard math The NP-hardness reductions rely on the NP-hardness of prize-collecting Steiner tree ([12]) and of maximizing a nondecreasing submodular function (Section 4.1).
    Known hardness results are used as the basis for the intractability proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Subadditive Load Balancing." pith.science (2026). https://pith.science/paper/F7I3MFWR

@misc{pith2026190809135,
  author       = {Pith},
  title        = {Pith review of: Subadditive Load Balancing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F7I3MFWR}},
  note         = {Machine review of arXiv:1908.09135}
}
read the original abstract

Set function optimization is essential in AI and machine learning. We focus on a subadditive set function that generalizes submodularity, and examine the subadditivity of non-submodular functions. We also deal with a minimax subadditive load balancing problem, and present a modularization-minimization algorithm that theoretically guarantees a worst-case approximation factor. In addition, we give a lower bound computation technique for the problem. We apply these methods to the multi-robot routing problem for an empirical performance evaluation.

Figures

Figures reproduced from arXiv: 1908.09135 by the authors.

Figure 1
Figure 1. Minimum spanning tree functions Let us consider an MST function with nonnegative node weights. Given an MST function MST : 2V → R and a nonnegative uniform node weight β ≥ 0, the function MST β : 2V → R defined by MST β (S) = MST (S) + β|S| (∀S ⊆ V ) (1) is also subadditive. The functions MST and MST β will be used in the computational experiments on multi-robot routing problems in Section 6. Facility location funct… view at source ↗
Figure 2
Figure 2. Facility location function 2.2.2 Interpolation of a submodular set function Let f : 2V → R be a nondecreasing submodular set function with f(∅) = 0. Assume that we have only a part of the function values of f. That is, for a given collection C = {C1, C2, . . . , Cm} ⊆ 2 V , the function values f(Ci) = fi are known for each i = 1, . . . , m and the value f(S) are unknown for any S ∈ 2 V \ C. The objective here is to … view at source ↗
Figure 3
Figure 3. Polymatroid P(f) and imitated polymatroid PC(f) 2.3 Subadditive load balancing We define the submodular load balancing (SMLB) and the subadditive load balancing (SALB) problems. S = (S1, . . . , Sm) is an m-partition of V = {1, . . . , n} if S1∪· · ·∪Sm = V and Sj∩Sj ′ = ∅ for 1 ≤ j < j′ ≤ m (some Sj can be empty). Suppose that set functions f1, . . . , fm : 2V → R are normalized, nonnegative, and 4 [PITH_FULL_IMAG… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Scheduling on Identical Machines with Setup Time and Unknown Execution Time

    cs.DS 2025-07 conditional novelty 6.0 of 10

    The paper proves asymptotically optimal competitive ratios for four online scheduling settings with known setup times and unknown execution times, from Θ(m) and Θ(n^{1/3}) down to Θ(log n / log log n).

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · cited by 1 Pith paper

  1. [1]

    F. Bach. Learning with submodular functions: A convex op timization perspective. Foundations and Trends in Machine Learning, 6(2–3):145–373, 2013

    work page 2013

  2. [2]

    Badanidiyuru, S

    A. Badanidiyuru, S. Dobzinski, H. Fu, R. Kleinberg, N. Ni san, and T. Roughgarden. Sketching valuation functions. In SODA ’12, pages 1025–1035, 2012

    work page 2012

  3. [3]

    Balcan and N

    M.-F. Balcan and N. Harvey. Submodular functions: Learn ability, structure, and optimization. SIAM Journal on Computing , 47:703–754, 2018

    work page 2018

  4. [4]

    A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek. Guarantees for greedy maximization of non- submodular functions with applications. In ICML, pages 498–507, 2017

    work page 2017

  5. [5]

    C. G. Bird. On cost allocation for a spanning tree: A game t heoretic approach. Networks, 6:335–350, 1976. 14

    work page 1976

  6. [6]

    Dobzinski, N

    S. Dobzinski, N. Nisan, and M. Schapira. Approximation a lgorithms for combinatorial auctions with complement- free bidders. Mathematics of Operations Research , 35:1–13, 2010

    work page 2010

  7. [7]

    J. Edmonds. Submodular functions, matroids, and certai n polyhedra. In Combinatorial Structures and Their Applications (R. Guy, H. Hanani, N. Sauer, J. Schonheim, eds .), pages 69–87. Gordon and Breach, 1970

    work page 1970

  8. [8]

    U. Feige. On maximizing welfare when utility functions a re subadditive. SIAM J. Comput. , 39(1):122–142, 2009

    work page 2009

Show all 39 references
  1. [9]

    Feldman and J

    V. Feldman and J. Vondr´ ak. Optimal bounds on approximat ion of submodular and xos functions by juntas. SIAM Journal on Computing , 45:1129–1170, 2016

    2016

  2. [10]

    M. X. Goemans, N. Harvey, S. Iwata, and V. Mirrokni. Appr oximating submodular functions everywhere. In SODA ’09, pages 535–544, 2009

    2009

  3. [11]

    M. X. Goemans and M. Skutella. Cooperative facility loc ation games. Journal of Algorithms , 50:194–214, 2004

    2004

  4. [12]

    M. X. Goemans and D. P. Williamson. A general approximat ion technique for constrained forest problems. SIAM Journal on Computing , 24:296–317, 1995

    1995

  5. [13]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization . Springer, 1988

    1988

  6. [14]

    Guestrin, A

    C. Guestrin, A. Krause, and A.P. Singh. Near-optimal se nsor placements in gaussian processes. In ICML, pages 265–272, 2005

    2005

  7. [15]

    Iwata, L

    S. Iwata, L. Fleischer, and S. Fujishige. A combinatori al strongly polynomial algorithm for minimizing submod- ular functions. Journal of the ACM , 48:761–777, 2001

    2001

  8. [16]

    Iwata and K

    S. Iwata and K. Nagano. Submodular function minimizati on under covering constraints. In FOCS’09, pages 671–680, 2009

    2009

  9. [17]

    R. K. Iyer, S. Jegelka, and J. Bilmes. Curvature and opti mal algorithms for learning and minimizing submodular functions. In NIPS, pages 2742–2750, 2013

    2013

  10. [18]

    Jegelka and J

    S. Jegelka and J. Bilmes. Submodularity beyond submodu lar energies: coupling edges in graph cuts. In CVPR’11, pages 1897–1904, 2011

    1904

  11. [19]

    Kempe, J

    D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the sp read of influence through a social network. In KDD’03, pages 137–146, 2003

    2003

  12. [20]

    Kishimoto and N

    A. Kishimoto and N. Sturtevant. Optimized algorithms f or multi-agent routing. In AAMAS, pages 1585–1588, 2008

    2008

  13. [21]

    Koenig, P

    S. Koenig, P. Keskinocak, and C. Tovey. Progress on agen t coordination with cooperative auctions. In AAAI, pages 1713–1717, 2010

    2010

  14. [22]

    Koenig, C

    S. Koenig, C. Tovey, X. Zheng, and I. Sungur. Sequential bundle-bid single-sale auction algorithms for decen- tralized control. In IJCAI, pages 1359–1365, 2007

    2007

  15. [23]

    M. G. Lagoudakis, E. Markakis, D. Kempe, P. Keskinocak, A. Kleywegt, S. Koenig, C. Tovey, A. Meyerson, and S. Jain. Auction-based multi-robot routing. In Proc. of Robotics: Science and Systems , 2005

    2005

  16. [24]

    E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoy s. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization . Wiley Series in Discrete Mathematics and Optimization, 19 85

  17. [25]

    J. K. Lenstra, D. B. Shmoys, and E. Tardos. Approximatio n algorithms for scheduling unrelated parallel machines. Math. Program., 46:259–271, 1990

    1990

  18. [26]

    Leskovec, A

    J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. Va nBriesen, and N. Glance. Cost-effective outbreak detection in networks. In KDD ’07, pages 420–429, 2007

    2007

  19. [27]

    Lin and J

    H. Lin and J. Bilmes. Multi-document summarization via budgeted maximization of submodular functions. In HLT’10, pages 912–920, 2010

    2010

  20. [28]

    Lov´ asz

    L. Lov´ asz. Submodular functions and convexity. In A. Bachem, M. Gr¨ otschel, and B. Korte, editors,Mathematical Programming — The State of the Art , pages 235–257. Springer-Verlag, 1983

    1983

  21. [29]

    Nagano, Y

    K. Nagano, Y. Kawahara, and S. Iwata. Minimum average co st clustering. In NIPS, pages 1759–1767, 2010

    2010

  22. [30]

    Nakashima, S

    H. Nakashima, S. Sano, K. Hirata, Y. Shiraishi, H. Matsu bara, R. Kanamori, H. Koshiba, and Itsuki Noda. One cycle of smart access vehicle service development. In Proc. of the 2nd International Conf. on Serviceology , pages 152–157, 2014

    2014

  23. [31]

    Narasimhan, N

    M. Narasimhan, N. Jojic, and J. Bilmes. Q-clustering. I n NIPS, pages 979–986, 2005. 15

    2005

  24. [32]

    Schrijver

    A. Schrijver. A combinatorial algorithm minimizing su bmodular functions in strongly polynomial time. Journal of Combinatorial Theory (B) , 80:346–355, 2000

    2000

  25. [33]

    Stobbe and A

    P. Stobbe and A. Krause. Efficient minimization of decomp osable submodular functions. In NIPS, pages 2208– 2216, 2010

    2010

  26. [34]

    Sviridenko, J

    M. Sviridenko, J. Vondr´ ak, and J. Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. In SODA’15, pages 1134–1148, 2015

    2015

  27. [35]

    Svitkina and L

    Z. Svitkina and L. Fleischer. Submodular approximatio n: sampling-based algorithms and lower bounds. In FOCS’08, pages 697–706, 2008

    2008

  28. [36]

    Vazirani

    Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag New York, Inc., 2001

    2001

  29. [37]

    Submodularity and curvature: the optimal algorithm

    Jan Vondrak. Submodularity and curvature: the optimal algorithm. In RIMS Kokyuroku Bessatsu, volume B23 , volume B23, pages 253–266, 2010

    2010

  30. [38]

    K. Wei, R. K. Iyer, S. Wang, W. Bai, and J. A. Bilmes. Mixed robust/average submodular partitioning: Fast algorithms, guarantees, and applications. In NIPS, pages 2233–2241, 2015

    2015

  31. [39]

    Zheng, S

    X. Zheng, S. Koenig, and C. Tovey. Improving sequential single-item auctions. In IROS, pages 2238– 2244, 2006. Supplementary Material A.1 Proofs of Subadditivity We show the subadditivity of the minimum spanning tree function M ST and the facility location function F L defined ...

    2006

Pith tools

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