{"id":"abcfa9a2-3cc0-48fb-8efa-14302c9b03d3","arxiv_id":"1908.09135","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors introduce subadditive load balancing, prove an approximation bound for a modularization-minimization algorithm, give a lower-bound method, and test the approach on multi-robot routing.","lead":"This paper generalizes submodular load balancing to subadditive cost functions, where the cost of a group of tasks is only required to be no more than the sum of its parts. It presents an iterative algorithm with a claimed worst-case guarantee, lower-bound techniques, and an application to multi-robot routing.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5 is proven only for the initial partition S(0); the final output of MMin is not guaranteed because subadditive modular approximations are not majorizing, a gap the paper itself leaves open.","rationale":"The reader's weakest assumption identifies exactly the invalid inference in Section 3.2: Lemma 8 bounds S(0), but the algorithm's output is the terminal partition. I reviewed the full text and found that the paper itself acknowledges the gap: Section 3.1 states that majorizing modular functions cannot be constructed, and Section 7 says the effect of iterations on the worst-case factor remains unanswered. Appendix A.2 provides explicit subadditive functions where the modular approximations fail to majorize, so the usual monotonicity argument from the submodular case is unavailable. Therefore Theorem 5, as a statement about MMin's final output, is not proven. This is load-bearing because the abstract and introduction advertise a worst-case guarantee for MMin. The paper has real value: the S(0) bound, the lower-bound technique, the hardness reductions, and the empirical evaluations are all useful. A simple repair would be to output the best partition seen or to state the guarantee only for S(0), but as written the central guarantee is unsupported. I agree with the reader's REJECT verdict and recommend no change.","tokens_in":18411,"tokens_out":7172,"duration_ms":75212,"concrete_test":"Enumerate all normalized, nondecreasing, subadditive set functions on n=4 elements with values in {0,...,3} and all m=2 partitions; for each, run MMin using the modular approximation of Eq. (5) and compare max_j g_j(S(0)_j) with the objective of the output. Any instance with a strict increase shows that the initial-bound proof does not transfer to the final output. If no violation is found, expand the domain or use an SMT solver to search for a monotonicity violation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2 proves Theorem 5 through Lemma 8, which bounds only the initial partition S(0) obtained from the modular problem (6). But MMin outputs S(k) at termination after iterating Steps 1-2, not S(0). For the theorem to apply to the final output, the sequence max_j g_j(S(k)_j) must be nonincreasing. In the submodular case this follows from majorizing modular approximations; Section 3.1 states explicitly that such majorizers \"cannot be constructed\" for subadditive functions, and Eq. (5) is only \"intuitively natural.\" Appendix A.2 gives concrete subadditive MST functions for which the analogous modular functions M1 and M2 fail to majorize g. Consequently, an iteration can return a partition with larger objective value, so the initial bound does not transfer. The proof simply asserts \"it suffices to show the initial partition attains the factor,\" which is valid only for an algorithm that outputs S(0) or keeps the best solution seen. Section 7 admits the question remains open. Thus the central approximation guarantee for MMin as stated is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18477,"tokens_out":12081,"duration_ms":119476,"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":[{"comment":"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).","section":"Section 3.2, Lemma 8 and Theorem 5"},{"comment":"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.","section":"Section 3.2, Lemma 8 versus Theorem 5"},{"comment":"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.","section":"Section 4.1, Theorem 10"}],"minor_comments":[{"comment":"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).","section":"Section 3.2, Theorem 5"},{"comment":"The proof of Lemma 7 refers to 'inequality (A1)', but the relevant display in the main text is inequality (8).","section":"Section 3.2, Lemma 7 proof"},{"comment":"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.","section":"Section 3, Algorithm Greedy"},{"comment":"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.","section":"Section 3.1, Algorithm MMin and Section 6"}],"recommendation":"major_revision","confidential_remarks":"The gap in Theorem 5 is substantial: as stated, the main theoretical claim is not proven. I view the fix as within the scope of a revision because a small algorithmic change, namely outputting the best partition seen during the iterations, would make the bound valid, and the gamma_MLB inconsistency in Lemma 8 is also readily repairable. If the authors cannot make such a change or provide a monotonicity argument, the main guarantee would need to be withdrawn rather than presented as a property of the iterative algorithm."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick read on 1908.09135. The paper has a real core and a genuine overclaim. Theorem 5 — and Proposition 4, for the same reason — is proved only for the initial partition S(0), not for the final partition MMin returns. The paper itself says majorizing modular functions cannot be constructed in the subadditive case, Appendix A.2 shows concrete MST examples where the natural candidates fail to majorize, and Section 7 explicitly leaves open whether the iterative updates help the worst-case factor. An iteration can in principle worsen the objective, so the guarantee does not transfer to the algorithm's output. The fix is easy: state the theorem for S(0), or run the algorithm and keep the best partition encountered.\n\nThe paper still has real value. SALB is a natural generalization of submodular load balancing. Lemma 7's non-uniform curvature bound genuinely extends the submodular analysis. The subadditivity proofs for the MST and facility location functions are clean and self-contained. The NP-hardness result for curvature computation is a simple reduction and it is correct; the pseudo-curvature is a sensible workaround. The lower-bound technique using Bird's cost-sharing is a nice transfer and appears sound. The multi-robot routing experiments show empirical value, though they do not close the theoretical gap.\n\nMinor issue: the algorithm description says Step 0 simply 'find an initial partition,' but the analysis assumes S(0) is optimal for the modular problem (6). That assumption needs to be explicit in the algorithm or in the theorem statement.\n\nWho gets value: people in set-function optimization, load balancing, and multi-robot routing. I would send this to peer review; it deserves referee time. But the authors need to restate the central claim and either modify the algorithm or the theorem. With that revision, this is a solid contribution.","headline":"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.","tokens_in":19112,"tokens_out":5727,"would_cite":true,"duration_ms":54249,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Subadditive load balancing gets a worst-case guarantee, with a curvature-aware bound for the modularization-minimization algorithm.","keywords":["subadditive set functions","load balancing","modularization-minimization","approximation factor","curvature","multi-robot routing","minimum spanning tree","submodular functions"],"falsifier":"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)}$.","tokens_in":18086,"feed_emoji":"⚖️","tokens_out":9044,"duration_ms":88383,"temperature":0.7,"pith_summary":"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.","feed_headline":"Subadditive load balancing gets a worst-case guarantee","feed_subtitle":"A curvature-aware modularization-minimization algorithm extends submodular load-balancing guarantees to a broader class of costs, with…","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the majorization-minimization template for submodular load balancing that MMin generalizes to subadditive costs.","marker":"[38]"},{"why":"Provides the curvature notion for submodular functions that Theorem 5 extends to subadditive functions.","marker":"[37]"},{"why":"Gives the curvature-based analysis techniques used in Lemmas 6 and 7.","marker":"[17]"},{"why":"The 2-approximation for modular scheduling that fixes the factor of 2 in the algorithm's initial partition step.","marker":"[25]"},{"why":"Edmonds' greedy algorithm is used to build exact minorization functions for the submodular lower-bound computation.","marker":"[7]"},{"why":"Bird's cost-sharing weights for the minimum-spanning-tree game give the approximate minorization functions used in the MST lower bound.","marker":"[5]"},{"why":"The prize-collecting Steiner tree problem supplies the NP-hardness reduction for unconstrained subadditive minimization.","marker":"[12]"},{"why":"Defines the minimax-team multi-robot routing problem used as the empirical application.","marker":"[23]"}],"fun_headline_variants":["Worst-case factor for subadditive load balancing now proven","Subadditive costs tamed: modularization-minimization bound","Load balancing with subadditive costs gets a worst-case bound","Minimax subadditive load balancing: a proven approximation factor"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Worst-case factor for subadditive load balancing now proven","Subadditive costs tamed: modularization-minimization bound","Load balancing with subadditive costs gets a worst-case bound","Minimax subadditive load balancing: a proven approximation factor"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000845,"raw_usage":{"total_tokens":3651,"prompt_tokens":888,"completion_tokens":2763,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":504,"completion_tokens_details":{"reasoning_tokens":2690}},"tokens_in":504,"tokens_out":2763,"duration_ms":20718,"temperature":1.0,"reasoning_tokens":2690,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:20:58.190238+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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)}$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the majorization-minimization template for submodular load balancing that MMin generalizes to subadditive costs."},{"cited_title":"Submodularity and curvature: the optimal algorithm","cited_arxiv_id":null,"evidence_quote":"Provides the curvature notion for submodular functions that Theorem 5 extends to subadditive functions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the curvature-based analysis techniques used in Lemmas 6 and 7."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The 2-approximation for modular scheduling that fixes the factor of 2 in the algorithm's initial partition step."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Edmonds' greedy algorithm is used to build exact minorization functions for the submodular lower-bound computation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Bird's cost-sharing weights for the minimum-spanning-tree game give the approximate minorization functions used in the MST lower bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The prize-collecting Steiner tree problem supplies the NP-hardness reduction for unconstrained subadditive minimization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the minimax-team multi-robot routing problem used as the empirical application."}],"review_version":1}