{"id":"e22e49a3-d1ab-493e-9164-dac7d35fb8d3","arxiv_id":"2507.17063","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For metric k-facility location, all pairs of the four sum/max objectives admit a single solution that is within a constant (or sqrt(k)) factor of optimal for both.","lead":"This paper proves that several natural sum and max objectives in committee selection and facility location are compatible, meaning a single solution can be near-optimal for two objectives at once. It extends earlier single-facility results to any number of facilities, but some proof steps need correction.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the Theorem 4.4 inequality flagged by the reader follows directly from Lemma 4.1 with the correct substitutions.","rationale":"The reader's verdict was CONDITIONAL based on an alleged gap in Theorem 4.4. A direct application of Lemma 4.1 with the singleton client set resolves the disputed inequality exactly, so the condition is unnecessary. I also verified the remaining key steps: the 3-approximation of Sum-Sum for the other objectives (§3), the even/odd k' constructions (§4.1), and the 2-approximation for Max-Max/Max-Sum (§4.3) all follow from the stated lemmas. The paper has minor typos (a wrong subscript in a 'recall' line, some table constants), but none is load-bearing. Therefore I recommend keeping the reader's verdict unchanged.","tokens_in":24366,"tokens_out":36906,"duration_ms":303676,"concrete_test":"Independently re-derive Theorem 4.4's first inequality by substituting A={i}, B=Q_SumSum, C=R_MaxSum into Lemma 4.1 and the second by substituting A=R_MaxSum, B=Q_SumSum, C={i}; confirm the coefficients match the paper's 1, 2/(k'+1) and (k'+1)/2, (k'+1)/2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked the reader's flagged step. Lemma 4.1 states f(A,B) ≤ (|B|/|C|) f(A,C) + (|A|/|C|) f(B,C). In Theorem 4.4, set A={i}, B=Q_SumSum, C=R_MaxSum. Since |B|=|C|=(k'+1)/2, this gives f(i,Q_SumSum) ≤ f(i,R_MaxSum) + [2/(k'+1)] f(R_MaxSum, Q_SumSum), exactly the paper's inequality. The second inequality follows by setting A=R_MaxSum, B=Q_SumSum, C={i}, yielding coefficients (k'+1)/2 and (k'+1)/2 as stated. Thus the reader's concern does not land. The only genuine issue is typographical: in the proof of Theorem 4.4, the line 'QΣΣ = argmin_{A⊆OΣΣ\\O:|A|=(k'−1)/2}' should read (k'+1)/2; the surrounding algebra uses the correct size, so the proof is intact. I found no load-bearing gap in the upper-bound arguments (Theorems 3.4, 4.2, 4.4, 4.12) or in the lower-bound constructions; minor table typos in the lower-bound instances do not affect the asymptotic ratios used.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the k-facility location / committee-selection problem in an arbitrary metric space under four objectives: Max-Max, Max-Sum, Sum-Max, and Sum-Sum. It asks whether one can always choose k facilities that are simultaneously close to optimal for a pair of these objectives. The paper first proves that the optimal Sum-Sum solution is a 3-approximation for all four objectives, and it extends prior single-facility results of [15] to multiple facilities via a reduction that maps each k-subset to a point in a derived metric. It then gives pair-specific improved bounds: Sum-Sum and Max-Sum are simultaneously approximable within 1+√(5/3) ≈ 2.29 for k ≥ 3, with a lower bound of (4+√7)/3 ≈ 2.215; Max-Sum and Max-Max are 2-compatible for all k, with a √2 lower bound for k = 2; Sum-Max and Max-Max remain 1+√2-compatible; and Sum-Sum and Sum-Max are simultaneously approximable within min(√k, 3). An appendix also gives a polynomial-time multi-winner voting rule with distortion at most 3 for l-centrum objectives.","tokens_in":24644,"tokens_out":34767,"duration_ms":306868,"significance":"If the proofs are repaired, the paper makes a solid contribution to the small literature on simultaneous approximation of facility-location objectives. The main results are clean and use elementary metric arguments; the constants are explicit, there are no free parameters, and the lower-bound instances are explicit and falsifiable. The 2-compatibility of Max-Sum and Max-Max and the near-tight bounds for Sum-Sum/Max-Sum are genuinely new for k > 1, and the reduction framework of Section 2 is useful. The weaknesses are concentrated in presentation and verification: several displayed equalities and table entries in the lower-bound constructions are inconsistent, and one theorem statement in Section 4.4 is false as written. These issues are local and repairable rather than evidence against the main approach.","major_comments":[{"comment":"The claimed identity αΣΣ(OΣM)·αΣM(OΣΣ) = k is false. For example, with two clients at distinct points and k = 2, if the facility multiset contains two copies of each client location, both Sum-Max and Sum-Sum are optimized by the same pair of facilities, giving product 1, not 2. The proof actually establishes only the inequality αΣΣ(OΣM)·αΣM(OΣΣ) ≤ k, and that inequality is sufficient for Corollary 4.14.1. Please replace the equality with an inequality and correct the proof accordingly.","section":"§4.4, Theorem 4.14"},{"comment":"The lower-bound instance is described inconsistently. With H defined as one facility from OΣΣ (all D) and two from OMΣ (all B), the correct asymptotic ratios are αΣΣ = (5+2√7)/3 and αMΣ = (10+√7)/9, whereas Table 2 lists for H the values (4+√7)/3 and (11+2√7)/9, which are the values for the two-D/one-B mixture. The statement that choosing either OΣΣ or H gives a (4+√7)/3 approximation is true only for the two-D/one-B mixture. Please swap or rename H and H′ and recheck every entry in Table 2.","section":"§4.1, Theorem 4.7 and Table 2"},{"comment":"The displayed derivation contains an inverted factor. Since αMΣ(OMM) = Max-Sum(OMM)/Max-Sum(OMΣ), the second displayed equality should contain 1/(k1·αMΣ(OMM)), not αMΣ(OMM) in the numerator. As printed, the equality αMM(OMΣ)·αMΣ(OMM) = k2/k1 does not follow from the surrounding equations. The statement of Theorem 4.9 is true and the proof is easily repaired, but the current proof is not correct.","section":"§4.3, proof of Theorem 4.9"},{"comment":"The stitching proofs contain two load-bearing typos. In the proof of Theorem 4.2, the inequality \"f(i,QMΣ) ≤ f(i,RMΣ) + (2/k′)f(RMΣ,QΣΣ)\" should have f(i,QΣΣ) on the left. In the proof of Theorem 4.4, the line \"QΣΣ = argmin_{A⊆OΣΣ\\O:|A|=(k′−1)/2}\" contradicts the definition with |A|=(k′+1)/2, and the subsequent bound Σ_i f(i,QΣΣ) ≤ ((k′+1)/(k′−1)) Σ_i f(i,RΣΣ) is not immediate from the definition alone; it requires a short averaging argument over the subsets RΣΣ∪{q}. The final optimization \"similar to the proof for Lemma 4.3\" is also asserted rather than proved. Please correct the typos and include the missing justification.","section":"§4.1, Theorems 4.2 and 4.4"}],"minor_comments":[{"comment":"The Sum-Sum entry for OΣΣ should be (√2−1)n+2 rather than (√2−1)n+1; the asymptotic ratios in the table are unaffected.","section":"§4.1, Theorem 4.5, Table 1"},{"comment":"For k = 3 the text says \"both facilities on B\" and \"both facilities on D\"; these should read \"all three facilities\" for both OMΣ and OΣΣ.","section":"§4.1, Theorem 4.7, text"},{"comment":"The entries for the mixed solution H are marked with asterisks; please provide the exact asymptotic ratios or an argument that every mixture yields simultaneous ratio at least 1+√2.","section":"§4.2, Theorem 4.8, Table 3"},{"comment":"The edge labels in the figure are difficult to associate with the four objective pairs; please make the correspondence between each edge and its [lower, upper] bound label explicit.","section":"Figure 1"},{"comment":"The proof uses a matching property of Plurality Veto without stating it formally; please state or cite the exact property being invoked.","section":"Appendix B, Theorem B.1"}],"recommendation":"major_revision","confidential_remarks":"The main theorems appear salvageable, but the density of algebraic and table inconsistencies is high. In particular, Theorem 4.14 is false as stated, and the verification of the lower bound in Theorem 4.7 is internally inconsistent; both must be fixed before the paper can be accepted. I do not see a circularity problem: the dependence on [15] is legitimate prior work by the same group, and the new k > 1 arguments are self-contained. The paper fits the journal's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Good news: the main theorems hold up better than the reader's verdict implies. The concern about Theorem 4.4 does not land. The inequality f(i,Q_SS) ≤ f(i,R_MS) + (2/(k'+1)) f(R_MS,Q_SS) is exactly Lemma 4.1 with A={i}, B=Q_SS, C=R_MS. The subsequent bound f(Q_SS) ≤ ((k'+1)/(k'-1)) f(R_SS) is also valid but the proof omits the sorting argument: Q_SS is the (k'+1)/2 lightest facilities, R_SS the remaining (k'-1)/2 heaviest, so the sum of the light q is at most (q/r) times the sum of the heavy r. The text has a typo there (argmin size written as (k'-1)/2), but the algebra around it uses the right size.\n\nThe paper's real problems are two localized algebra slips. Theorem 4.9's proof drops a reciprocal: the correct relation is α_MM(O_MS) = (k2/k1) / α_MS(O_MM), which gives the stated product identity, but the displayed derivation says times α_MS and is wrong. Theorem 4.14 is overstated as equality; the derivation only yields ≤, and the equality is actually false (a simple two-client, three-facility line example with k=2 gives product 4/3). The corollary only needs the inequality, so the √k bound survives unchanged.\n\nWhat's genuinely new and good: the 3-compatibility of all four objectives via the Sum-Sum optimum (Theorem 3.4) is clean and immediately useful; the stitching technique for Sum-Sum and Max-Sum when k≥3 is a real contribution; the 2-compatibility for Max-Max and Max-Sum is a new result not implied by the single-facility framework. The reduction in Section 2 correctly carries [15] over to k>1, and the self-citation is legitimate prior work, not circular.\n\nThe lower-bound constructions look solid, and the claimed constants are credible. The paper is for people working on multi-objective facility location, committee selection, or distortion. It deserves a serious referee; with the flagged corrections it should be accepted for a major conference or journal. The issues are minor, concentrated in three spots, and none of them affect the main compatibility results.","headline":"The main compatibility results are correct and the Theorem 4.4 concern raised by the reader does not land; the paper's real issues are localized algebra errors in Theorems 4.9 and 4.14 that are fixable without changing the conclusions.","tokens_in":25142,"tokens_out":15145,"would_cite":true,"duration_ms":116393,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90B80"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that, in any metric space, for every pair of the four natural sum/max objectives for choosing $k$ facilities, there exists a single solution that is within a small constant factor of optimal for both objectives…","keywords":["simultaneous approximation","committee selection","metric facility location","sum objective","max objective","approximation ratio","compatibility","k-facility location"],"falsifier":"Enumerate all metric spaces on a small set of points (say 4 clients and 3–4 facility locations) and all choices of $k=3$; compute $O_{\\Sigma\\Sigma}$, $O_{M\\Sigma}$, the stitched solution, and the exact simultaneous approximation ratio. If any instance has ratio strictly larger than $1+\\sqrt{5/3}$, or the coefficient inequality $f(i,Q_{\\Sigma\\Sigma})\\le f(i,R_{M\\Sigma})+\\frac{2}{k'+1}f(R_{M\\Sigma},Q_{\\Sigma\\Sigma})$ fails while the ratio exceeds the claimed bound, Theorem 4.4 is false.","tokens_in":24168,"feed_emoji":"📍","tokens_out":11607,"duration_ms":112889,"temperature":0.7,"pith_summary":"Choosing $k$ facilities for clients raises a question: should each client minimize the total distance to all facilities or the farthest one, and should society aggregate those costs by sum or by maximum? This paper's central claim is that this choice does not force a sacrifice: for any pair of these four objectives, in any metric space, some placement of $k$ facilities is close to optimal for both at once. The optimal $\\text{Sum-Sum}$ solution alone is already a 3-approximation for the other three objectives, and more careful bounds improve specific pairs: $\\text{Sum-Sum}$ with $\\text{Max-Sum}$ to $1+\\sqrt{5/3}\\approx 2.29$ when $k\\ge 3$, and $\\text{Max-Max}$ with $\\text{Max-Sum}$ to factor 2 for every $k$. The upshot is that a planner who is unsure which objective is the right one can use a single committee that is reasonable under all of them.","feed_headline":"One set of facilities fits sum and max goals within 2.29","feed_subtitle":"A single committee is near-optimal for all four objectives; Max-Sum and Max-Max stay within factor 2.","key_machinery":"The engine is a set-valued triangle inequality: a client-cost function $f$ over facility sets obeys $f(i,A)\\le f(i,B)+f(j,B)+f(j,A)$ for all clients $i,j$ and facility sets $A,B$. Both $\\sum_{a\\in A} d(i,a)$ and $\\max_{a\\in A} d(i,a)$ satisfy it, which lets Section 2 embed every choice of $k$ facilities as a single point in a new metric and import the known $1+\\sqrt{2}$ single-facility simultaneous-approximation result. The improved bounds for $\\text{Sum-Sum}$ vs $\\text{Max-Sum}$ are carried by a second identity, Lemma 4.1: $f(A,B)\\le \\frac{|B|}{|C|}f(A,C)+\\frac{|A|}{|C|}f(B,C)$, which controls the cross-cost between the parts of the two optimal solutions; the paper's candidate is $A=O\\cup Q_{M\\Sigma}\\cup Q_{\\Sigma\\Sigma}$, the overlap plus the cheapest halves of each optimum. For the different-client-cost pair $\\text{Max-Max}$/$\\text{Max-Sum}$, the key object is the ratio identity $\\alpha_{M\\Sigma}(O_{MM})\\cdot\\alpha_{MM}(O_{M\\Sigma})=k_2/k_1$, where $k_1,k_2$ record how many times the worst client's max distance fits into its sum distance for each optimum.","core_discovery":"On its own terms, the discovery is a compatibility theorem: the four objectives defined by client-level max or sum and society-level max or sum are pairwise compatible with small constant factors, and the paper supplies matching or near-matching lower bounds. For $\\text{Sum-Sum}$ versus $\\text{Max-Sum}$, the optimal $\\text{Sum-Sum}$ solution is a 3-approximation for $\\text{Max-Sum}$, while for $k\\ge 3$ the best of the two optima and a 'stitched' solution that keeps the cheapest halves of each optimum achieves $1+\\sqrt{5/3}$, with no algorithm able to beat $(4+\\sqrt{7})/3$. For $\\text{Max-Max}$ versus $\\text{Max-Sum}$, whose individual client cost functions differ, at least one of the two optima is always a 2-approximation for the other objective, so the pair is 2-compatible for every $k$; the lower bound is $\\sqrt{2}$ at $k=2$. The paper also shows $\\text{Sum-Sum}$ versus $\\text{Sum-Max}$ is approximable within $\\min(\\sqrt{k},3)$, so small committees need not trade one desideratum for the other.","pith_inferences":["A natural next step, beyond what the paper proves, is that the stitching technique should extend to any pair of client-cost functions satisfying the set-valued triangle inequality, plausibly producing constants analogous to $1+\\sqrt{5/3}$.","The paper's results are existential rather than algorithmic; testing whether the stitched solution or a factor-2 $\\text{Max-Max}$/$\\text{Max-Sum}$ solution can be found in polynomial time would be a direct computational follow-up.","Because the lower-bound examples are line metrics, the compatibility constants may be smaller in structured metrics such as trees or low-dimensional Euclidean spaces; checking this is a concrete testable extension."],"forward_implications":["If the theorems are correct, a decision-maker can take the optimal $\\text{Sum-Sum}$ committee and be within factor 3 of every other objective, with no need to know which objective is the correct one.","For $k\\ge 3$, the $\\text{Sum-Sum}$/$\\text{Max-Sum}$ gap shrinks to $1+\\sqrt{5/3}\\approx 2.29$, and the lower bound $(4+\\sqrt{7})/3\\approx 2.22$ shows the remaining gap is small and structural.","$\\text{Max-Max}$ and $\\text{Max-Sum}$ can be optimized simultaneously within factor 2 for any $k$, a pair whose compatibility had not been studied before.","For $\\text{Sum-Sum}$ vs $\\text{Sum-Max}$, the simultaneous ratio is at most $\\min(\\sqrt{k},3)$, so for small committees the bound is often better than the generic 3.","The same inequality framework yields a polynomial-time multi-winner voting rule whose distortion is at most 3 for any $l$-centrum objective whose single-voter cost obeys the triangle inequality."],"supporting_citations":[{"why":"Supplies the single-facility simultaneous-approximation theorem and the inequality-reduction framework that Section 2 generalizes to k facilities.","marker":"[15]"},{"why":"Identifies q-social cost as a client-cost family satisfying the set-valued triangle inequality, the same structural property used for sum and max costs.","marker":"[4]"},{"why":"Provides the Plurality Veto voting rule used in the appendix to turn the 3-compatibility bound into a polynomial-time 3-distortion multi-winner rule.","marker":"[17]"}],"fun_headline_variants":["One facility set: sum and max objectives within 2.29","Sum vs max: same choice near-optimal for both, 2.29","Compatible objectives: sum and max, a single solution works","Facility selection: sum and max goals can both be met","Sum-Sum and Max-Sum: one solution, factor 2.29"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the coefficient inequality used in Theorem 4.4: for an odd leftover count $k'$, the cost of the cheapest half of the Sum-Sum optimum to any client is at most the cost of the leftover Max-Sum facilities plus $\\frac{2}{k'+1}$ times the cross-cost between those two parts; if that inequality fails, the $1+\\sqrt{5/3}$ bound fails with it.","fun_headline_variants_meta":{"raw":{"variants":["One facility set: sum and max objectives within 2.29","Sum vs max: same choice near-optimal for both, 2.29","Compatible objectives: sum and max, a single solution works","Facility selection: sum and max goals can both be met","Sum-Sum and Max-Sum: one solution, factor 2.29"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000437,"raw_usage":{"total_tokens":2231,"prompt_tokens":965,"completion_tokens":1266,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":1171}},"tokens_in":581,"tokens_out":1266,"duration_ms":13695,"temperature":1.0,"reasoning_tokens":1171,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T14:59:57.498733+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all metric spaces on a small set of points (say 4 clients and 3–4 facility locations) and all choices of $k=3$; compute $O_{\\Sigma\\Sigma}$, $O_{M\\Sigma}$, the stitched solution, and the exact simultaneous approximation ratio. If any instance has ratio strictly larger than $1+\\sqrt{5/3}$, or the coefficient inequality $f(i,Q_{\\Sigma\\Sigma})\\le f(i,R_{M\\Sigma})+\\frac{2}{k'+1}f(R_{M\\Sigma},Q_{\\Sigma\\Sigma})$ fails while the ratio exceeds the claimed bound, Theorem 4.4 is false.","supporting_citations":[{"cited_title":"Optimizing multiple simultaneous ob- jectives for voting and facility location","cited_arxiv_id":null,"evidence_quote":"Supplies the single-facility simultaneous-approximation theorem and the inequality-reduction framework that Section 2 generalizes to k facilities."},{"cited_title":"The metric distortion of multiwinner voting.Artificial Intelligence, 313:103802, 2022","cited_arxiv_id":null,"evidence_quote":"Identifies q-social cost as a client-cost family satisfying the set-valued triangle inequality, the same structural property used for sum and max costs."},{"cited_title":"Plurality veto: A simple voting rule achieving optimal metric distortion","cited_arxiv_id":null,"evidence_quote":"Provides the Plurality Veto voting rule used in the appendix to turn the 3-compatibility bound into a polynomial-time 3-distortion multi-winner rule."}],"review_version":1}