Pith. sign in

REVIEW 4 major objections 4 minor 296 references

Spectral Dual Fitting for $k$-Means

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

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

Pith's one-line read Improved dual fitting with spectral analysis gives a 3.694-approximation for Euclidean k-means, breaking the 3.94 hardness barrier for general metrics, and a 4.9-approximation for metric k-means.

desk verdict Strong, credible k-Means improvement; the metric 4.9 claim rests on a deferred AI-assisted calculus lemma that must be checked before the headline result can be trusted. read the letter →

arxiv 2607.14654 v1 pith:EPISVXKH submitted 2026-07-16 cs.DS

Aditya Anand , Moses Charikar , Vincent Cohen-Addad , Ruiquan Gao , Fabrizio Grandoni , Euiwoong Lee , Amatya Sharma , Ernest van Wijland This is my paper · ORCID
classification cs.DS MSC 68W2590C27
keywords k-meansapproximationalgorithmsdualfittingspectralanalysisEuclideanmetricLagrangianmultiplierpreservingfacilitylocationhardnessbarrier
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

The paper's central claim is that k-means clustering can be approximated better in Euclidean space than in arbitrary metrics: a polynomial-time (3+ln2+ε)-approximation for Euclidean k-means and a (4.9+ε)-approximation for metric k-means. The Euclidean result passes below 1+8/e≈3.94, the known hardness threshold for metric k-means, implying under P≠NP that the two versions have different optimal approximation ratios — the first such separation for k-median, k-means, or facility location. The improvement comes from a greedy dual-fitting algorithm that charges each directly connected client only its first connection cost, reserving the overpayment, and from replacing factor-revealing linear programs with a spectral analysis that bounds the approximation factor by the largest eigenvalue of a family of matrices. If correct, the algorithm shows Euclidean k-means is strictly easier to approximate than general-metric k-means, improving the previous 4+ε and 5+ε ratios.

What carries the argument

The central object is the reserved first-connection cost R_j: for each client j, R_j is its distance to the first facility that directly connects it, and (ρ−1)R_j² is subtracted from its dual value to make dual accounting tight. The load-bearing analytic machinery is a spectral bound: the dual-feasibility inequality is reduced to showing that a quadratic form in squared distances has largest eigenvalue at most Γ, where Γ=3+ln2 (Euclidean) or Γ=4.9 (metric). In the metric case this spectral bound is obtained through the Collatz–Wielandt formula applied to a nonnegative matrix, which reduces the proof to checking the explicit one-variable bound max F(x)<12/5.

What would settle it

Numerically evaluate F(x) on the interval [1, ∛12] and check whether any value reaches or exceeds 12/5; equivalently, compute the largest eigenvalue of the Collatz–Wielandt matrix for large finite s and verify it stays below 4.9. A counterexample where max F(x) ≥ 12/5, or a direct finite instance whose spectral bound exceeds 4.9, would falsify the claim.

Watch

Extended reading notes

Core claim

On the paper's own terms, the new algorithm establishes Lagrangian-multiplier-preserving (LMP) approximations for facility location with squared distances: (3+ln2) in Euclidean and 4.9 in general metrics, leading through a two-step framework to the stated k-means ratios. The key accounting device is that when a client is first directly connected to a facility, its first connection distance R_j is recorded, and the client permanently reserves (ρ−1)R_j² in its dual budget; subsequent bids to other facilities are made only from the remaining value. This yields a dual payment identity that is exact, while the reserved term feeds into a dual-feasibility analysis. The feasibility proof upper-bound

Load-bearing premise

The metric-side 4.9 guarantee rests on a single numerical analysis bound, max_{x∈[1,∛12]}F(x)<12/5, whose proof is deferred to an appendix and described in the paper as obtained by a computer-assisted computation, later revised by the authors; if that polynomial inequality fails, the spectral eigenvalue bound for the metric case collapses and the 4.9 figure is no longer certified by this argument.

Editorial extensions

If this is right

  • Euclidean k-means admits a (3+ln2+ε)-approximation, below the metric hardness barrier 1+8/e≈3.94, so assuming P≠NP the Euclidean and general-metric versions have different optimal approximability.
  • Metric k-means admits a (4.9+ε)-approximation, improving the previously known 5+ε and 5.83 bounds.
  • The LMP 4.9 (metric) and 3+ln2 (Euclidean) facility-location approximations imply bicriteria solutions opening k+O(log n/ε³) centers with approximation (Γ+O(√ε)).
  • Stable instances: (ζ/log n)-stable metric instances get a (4+ε)-approximation, and Euclidean instances get (2+ε), improving prior results.
  • The dual-payment/bid framework shows how to exactly account for dual overpayments while keeping local dual-feasibility analysis, a technique that carries over to other squared-distance facility location problems.

Reading between the lines

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

  • If the 3+ln2 Euclidean result withstands scrutiny, it suggests the true approximability gap between Euclidean and metric k-means may be wider than just the barrier crossing; the authors' numerical simulations (not paper claims) indicate the spectral framework alone has barriers around 3.51 and 4.67, so further tightening may be possible with different techniques.
  • The dual-reservation idea — charging a client only once for its best connection — is a natural template for other clustering objectives with squared costs; it suggests that overpayment of the direct-connection cost is the fundamental obstacle to dual-fitting barrier arguments and can be isolated by a per-client parameter.
  • The spectral analysis replacing factor-revealing linear programs could be applied directly to other facility-location variants; a testable extension is to see whether the same largest-eigenvalue bound approach yields improved constants for k-median or capacitated versions with squared distances.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. The paper proposes a new dual-fitting algorithm (Algorithm 1) for Facility Location with squared distances, in which each client that becomes directly connected reserves a part (ρ−1)R_j² of its dual value. The authors prove dual-payment and dual-feasibility lemmas (Lemmas 4.5 and 4.6) and combine them with a log-adaptive, MergeSolutions framework to obtain claimed polytime approximation ratios (3+ln2+ε) for Euclidean k-Means (Theorem 1.1) and (4.9+ε) for Metric k-Means (Theorem 1.2), together with bicriteria and stable-instance results (Theorems 1.3–1.5). The analysis is organized through a general constraint system (Lemmas 4.9–4.12) and a spectral framework in which the approximation ratio is bounded by an eigenvalue of an explicitly constructed matrix; the Euclidean and metric cases are handled separately.

Significance. If the proofs are correct, this is a substantial advance: the Euclidean result breaks the metric hardness barrier of 1+8/e ≈ 3.94, giving the first Euclidean-vs-metric separation for k-Means-type objectives, and the spectral dual-fitting framework is a new technical idea. The inlined derivation in Section 2.2 of a weaker Γ < 3.85 for the simplified no-IC Euclidean case is self-contained and elegant, and the dual-payment accounting is well motivated. However, the final constants are not independently verifiable from the submitted manuscript: both the Euclidean (3+ln2) and metric (4.9) results depend on deferred and, in the metric case, AI-assisted proofs. In particular, the metric guarantee rests on the polynomial bound Lemma 6.6 whose proof is deferred to an absent appendix. The significance is therefore conditional on the missing proofs being supplied and correct.

major comments (4)
  1. [§6.1 / Lemma 6.6 (Eq. 27), Appendix C.1] The metric 4.9 result of Theorem 1.2 depends on the claim max_{x∈[1,∛12]} F(x) < 12/5, where F is the degree-6 polynomial in Eq. (27). This is the final step converting the Collatz–Wielandt bound into the concrete constant 12/5, and hence into Γ = 4.9 = 2.5 + 2.4. The proof is deferred to Appendix C.1, which is not included in the manuscript. Moreover, §6.1 explicitly states the proof was obtained by GPT 5.2/5.4 Pro/Thinking, after exchange with the authors. A subtle error in Lemma 6.6, or in the supporting inequalities of Claim 6.5 (Eqs. 28–30), would invalidate the 4.9 approximation guarantee. The paper is not currently self-contained or independently checkable on this load-bearing step.
  2. [§5.3.2 / §5.4 (Lemmas 5.8, 5.20), Appendices B.1/B.2] The Euclidean (3+ln2) result relies on Lemma 5.8, the key Laplacian bound, which is deferred to Appendix B.1, and on Lemma 5.20, the approximate-constraint generalization deferred to Appendix B.2. The inlined derivation in Section 2.2 proves only the special case with no indirectly connected clients and gives the weaker bound λ ≤ 27/32, i.e. Γ < 3.85. Since Lemmas 5.8 and 5.20 are also used in the log-adaptive and robust analysis of Sections 7–8, the Euclidean side of Theorems 1.1 and 1.3 is not fully established in the present manuscript.
  3. [§7.2 / §8 (log-adaptive algorithm, Theorem 8.7)] The conversion from the LMP guarantee to the claimed (3+ln2+ε) and (4.9+ε) k-Means ratios requires the full log-adaptive analysis of Section 7 and the MergeSolutions/robust analysis of Section 8, including Lemma 7.4 and Theorem 8.7. These arguments are long and depend on many ε, δ, η slack parameters; the proof of Section 8.4 is referenced but not included in the submitted text. In particular, the Euclidean subcases in Section 7.2 invoke Lemma 5.20, whose proof is absent, and the robust analysis relies on a generalization of the dual payment and dual feasibility lemmas whose complete derivation is not shown. The main theorems therefore cannot be certified from the manuscript alone.
  4. [§6.1, Claim 6.5 and Eqs. (28)–(30)] Even apart from Lemma 6.6, the Collatz–Wielandt step depends on nontrivial test-vector inequalities: the integral bound on U_t(h) in Eq. (33), the monotonicity argument for g_u h_u, and the treatment of the boundary terms. These inequalities are stated but not proved in a fully formal way; for example, the passage from the Riemann sum to the integral in Eq. (33) uses monotonicity of (1+11z)^{-2/3} but this should be spelled out with the endpoints and the definition of η_t. Since these inequalities are load-bearing for the spectral bound, they need to be verified line-by-line.
minor comments (4)
  1. [Throughout] Typos and formatting: 'F acility' in section headers, 'resp.' shorthand, duplicated 'Algorithm 1 (Greedy Algorithm), restated' titles, and inconsistent use of 'w.l.o.g.' and 'wlog'.
  2. [Table of contents / Appendices] Appendices A, B.1, B.2, C.1, C.2, and Section 9/10 are listed but not present in the submitted manuscript. Even if these are deferred for the arXiv version, a complete journal submission must include them.
  3. [§5.2, p_{tjℓ} definition] The definition ρ_tjℓ = η_{tℓ}/σ_t(j+1) requires care when σ_t(j+1)=0 or when j is not in DC_t; the text says these cases are set to 0, but the normalization condition is not formally verified for all boundary cases.
  4. [Abstract / §1] The phrase 'high-dimensional Euclidean' may be misleading since the algorithm and analysis are dimension-independent; this should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the dual-feasibility constants are analytic consequences of run invariants; the metric 4.9 proof has deferred AI-assisted verification gaps, but these are correctness/verifiability concerns, not circularity.

full rationale

No load-bearing circular step is exhibited. The paper's central bounds are proved, not assumed: Lemma 4.9 and Lemma 4.10 derive the (p_{t,j,\ell}) and (\beta_t) constraints from the greedy algorithm's run events and bid upper bounds; Lemmas 5.3, 5.7, 5.11, 6.1, 6.2, and 6.3 then convert those constraints into a quadratic form. The final constants come from explicit analytic inequalities: the Euclidean bound uses the choice \theta=1/2 to obtain 2+1+\ln 2 = 3+\ln 2, and the metric bound uses \rho=5/2 plus the Collatz--Wielandt bound \max F(x)<12/5 to obtain 2.5+12/5=4.9. The numerical selection of \rho\approx 2.5 in \S2.3 is a parameter search, not an input to the proof; the proof replaces numerical eigenvalue estimates with an analytic inequality chain. The main caveats are verification gaps: Lemma 6.6 is deferred to Appendix C.1 and its derivation is described as 'obtained by GPT 5.2/5.4 Pro/Thinking' and then revised by the authors, and the key Laplacian bound Lemma 5.8 is deferred to Appendix B.1. An omitted or AI-assisted proof affects independent verifiability and correctness risk, but there is no exhibited reduction of a conclusion to its own premise: none of the stated bounds assume the theorems they are used to prove, and the fitted eigenvalue estimate is not used as a proof input. Thus the derivation chain is not circular.

Assumptions & free parameters 4 free parameters · 6 assumptions · 2 invented entities

The central claim rests on the greedy algorithm's invariants (dual payment and dual feasibility), which are derived in-text; the spectral analysis converts the feasibility bound into eigenvalue bounds that are proven analytically. The main external inputs are the borrowed Laplacian bound (Lemma 5.8) and the stability/merge framework from prior papers, both disclosed. The free parameters ρ, Γ and the Collatz–Wielandt witness are tuned by construction or by numerical experiments, but the final bounds are stated as proven inequalities, and the paper discloses its own numerical barriers.

free parameters (4)
  • ρ (bid coefficient) = ρ = 2 (Euclidean), ρ = 2.5 (metric)
    Algorithm parameter controlling how much of a client's dual is reserved via (ρ−1)R²_j. ρ = 2.5 chosen via numerical eigenvalue minimization (§2.3), then proven to suffice with Γ = 4.9; ρ = 2 chosen for the Euclidean analysis to obtain Γ = 3 + ln 2.
  • Γ (LMP approximation ratio) = 3 + ln 2 (Euclidean), 4.9 (metric)
    Target ratio appearing in the dual-feasibility lemma. 4.9 = 2.5 + 12/5: the sum of the bid coefficient and the proven spectral bound; the entire analysis is organized around this constant.
  • Collatz–Wielandt witness: τ = ∛12, h_t = (1+11g_t)^{-2/3}, and F(x) coefficients = τ = ∛12; polynomial coefficients (48, 47, 357, 564, 396, 4665, 2178)
    The test vector and the substitution g = (x³−1)/11 are reverse-engineered to make the maximum of F(x) equal 12/5. This is a witness constructed to hit the target bound — legitimate analysis, but tuned by construction.
  • ε, δ in the log-adaptive algorithm = ε ∈ (0, 10⁻¹⁰⁰), δ = ε/2
    Slack parameters for the O(log n/ε³)-center bicriteria conversion and the (ζ/log n)-stable-instance theorems; inherited from the framework of [CGL+25; CCG+25; CCG+26].
assumptions (6)
  • standard math Weak LP duality for the Facility Location LP (Primal/ Dual FL LP in §3)
    Used in the proof of Theorem 4.1 to convert the dual-feasible solution (α*_j − (ρ−1)R²_j)/Γ into the LMP bound via OPTLP.
  • domain assumption Distance-rounding reductions (Lemmas 3.2, 3.3, 8.1) from [CCG+25], [CCG+26]
    Lets the analysis assume integer distances in [1, n³/ε] or [1, 2n³/ε³+1] while losing a (1+O(ε)) factor; cited from prior work.
  • standard math Squared-distance triangle inequalities (Lemmas 3.4, 3.5) from [CCG+25]
    γx² + γ/(γ−1)y² ≥ (x+y)² and the three-term analogue; used throughout §5 and §6 to expand (r_jt + d(j,ℓ))².
  • domain assumption Lemma 5.8: Laplacian bound Σ_{j<ℓ} w(j)P_{jℓ}(x_j−x_ℓ)² ≤ Σ_j w(j)x²_j, borrowed from [CCG+26]
    The key matrix property for the Euclidean case, stated as 'essentially [CCG+26]' with proof deferred to Appendix B.1; the central claim depends on it.
  • standard math Collatz–Wielandt formula ([Mey00], Theorem 8.3.3)
    Used in §6 to upper bound λ_max of the non-negative matrix K via the test vector h; standard linear algebra.
  • domain assumption LMP-to-bicriteria framework and stability machinery of [CGL+25; CCG+25; CCG+26] (including the (ζ/log n)-stability thresholds and the two-solution merge walk)
    Theorems 1.3–1.5 and the final k-Means theorems inherit this framework; the paper extends it (removing the Γ ≥ 4 condition for the LMP conversion) but relies on its correctness.
invented entities (2)
  • R_j: first direct-connection distance of client j independent evidence
    purpose: Reserves (ρ−1)R²_j of the client's dual so that dual payments become exact instead of overpaying by a factor ρ; the subtraction is carried through the dual-feasibility analysis.
    Deterministically computable from any run of Algorithm 1 (set when a client is first moved to DC); its correctness is checkable in the algorithm trace, and the improved bound depends on it.
  • Free facilities with squared-distance overhead u(·) (Section 8)
    purpose: Analysis device for walking between two solutions during MergeSolutions; u is interpolated between 0 and 10M to sandwich k centers.
    Pure modeling construct with u values set by the merging argument; no falsifiable handle outside the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Spectral Dual Fitting for $k$-Means." pith.science (2026). https://pith.science/paper/EPISVXKH

@misc{pith2026260714654,
  author       = {Pith},
  title        = {Pith review of: Spectral Dual Fitting for $k$-Means},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EPISVXKH}},
  note         = {Machine review of arXiv:2607.14654}
}
abstract

We give a new dual fitting algorithm which gives improved approximation ratios of $3+\ln 2 + \epsilon\ (\approx 3.694)$ and $4.9+\epsilon$ for $k$-Means in (high-dimensional) Euclidean and general metrics respectively, improving upon the previously known ratios of $4+\epsilon$ [Charikar, Cohen-Addad, Gao, Grandoni, Lee, and van Wijland STOC'26] and $5+\epsilon$ [Byrka, Guo, Hu, Li, Wan, Wang FOCS'26], resp. In particular, our result for Euclidean $k$-Means breaks the hardness barrier of $1+8/e\approx 3.94$ for Metric $k$-Means. Prior to our work, no such separation between general and Euclidean metrics was known for $k$-Median, $k$-Means, or Facility Location in terms of their approximability. Unlike prior dual fitting approaches for $k$-Means, our new dual fitting algorithm tightly accounts for dual payments while still facilitating an effective dual feasibility analysis. We introduce a new framework that uses spectral analysis for determining the approximation factor of our algorithm.

Figures

Figures reproduced from arXiv: 2607.14654 by the authors.

Figure 1
Figure 1. Barrier example for the previous dual-feasibility analysis. The facility [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

296 extracted references · 63 canonical work pages

  1. [1]

    Salavatipour , editor =

    Zachary Friggstad and Mohsen Rezapour and Mohammad R. Salavatipour , editor =. Local Search Yields a. 2016 , url =. doi:10.1109/FOCS.2016.47 , timestamp =

    work page doi:10.1109/focs.2016.47 2016

  2. [2]

    Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics , booktitle =

    Vincent Cohen. Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics , booktitle =. 2016 , url =. doi:10.1109/FOCS.2016.46 , timestamp =

    work page doi:10.1109/focs.2016.46 2016

  3. [3]

    A Fast Approximation Scheme for Low-Dimensional

    Vincent Cohen. A Fast Approximation Scheme for Low-Dimensional. Proceedings of the Twenty-Ninth Annual. 2018 , url =. doi:10.1137/1.9781611975031.29 , timestamp =

    work page doi:10.1137/1.9781611975031.29 2018

  4. [4]

    Proceedings of the 67th

    Jaroslaw Byrka and Yuhao Guo and Yang Hu and Shi Li and Chengzhang Wan and Zaixuan Wang , title =. Proceedings of the 67th. 2026 , note =

    2026

  5. [5]

    arXiv preprint arXiv:0809.2554 , year=

    Simpler analyses of local search algorithms for facility location , author=. arXiv preprint arXiv:0809.2554 , year=

    arXiv

  6. [6]

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

    Breaching the 2 LMP approximation barrier for facility location with applications to k-median , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  7. [7]

    2000 , publisher=

    Matrix Analysis and Applied Linear Algebra , author=. 2000 , publisher=

    2000

  8. [8]

    Journal of the ACM (JACM) , volume=

    Near-linear time approximation schemes for clustering in doubling metrics , author=. Journal of the ACM (JACM) , volume=. 2021 , publisher=

    2021

Show all 296 references
  1. [9]

    Proceedings of the twenty-third annual symposium on Computational geometry , pages=

    A PTAS for k-means clustering based on weak coresets , author=. Proceedings of the twenty-third annual symposium on Computational geometry , pages=

  2. [10]

    Proceedings of the tenth annual symposium on Computational geometry , pages=

    Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering , author=. Proceedings of the tenth annual symposium on Computational geometry , pages=

  3. [11]

    16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , pages=

    Facility Location on High-Dimensional Euclidean Spaces , author=. 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , pages=. 2025 , organization=

    2025

  4. [12]

    The hardness of k-means clustering , author=

  5. [13]

    arXiv preprint arXiv:1502.03316 , year=

    The hardness of approximation of euclidean k-means , author=. arXiv preprint arXiv:1502.03316 , year=

    arXiv

  6. [14]

    Information Processing Letters , volume=

    Improved and simplified inapproximability for k-means , author=. Information Processing Letters , volume=. 2017 , publisher=

    2017

  7. [15]

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

    Johnson coverage hypothesis: Inapproximability of k-means and k-median in lp-metrics , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

    2022

  8. [16]

    MacQueen, J. B. , title =. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1 , editor =. 1967 , pages =

    1967

  9. [17]

    Bulletin de l’Académie Polonaise des Sciences, Classe III , volume =

    Steinhaus, Hugo , title =. Bulletin de l’Académie Polonaise des Sciences, Classe III , volume =. 1957 , note =

    1957

  10. [18]

    Lloyd, S. P. , title =. Bell Telephone Laboratories Memo , year =

  11. [19]

    An Improved Greedy Approximation for (Metric) k-Means , booktitle =

    Charikar, Moses and Cohen. An Improved Greedy Approximation for (Metric) k-Means , booktitle =. 2025 , pages =

    2025

  12. [20]

    A (4+ )-Approximation for Euclidean k-Means via Non-Monotone Dual-Fitting , booktitle =

    Charikar, Moses and Cohen. A (4+ )-Approximation for Euclidean k-Means via Non-Monotone Dual-Fitting , booktitle =. 2026 , note =

    2026

  13. [21]

    Vincent Cohen. A (2+. Proceedings of the 57th Annual. 2025 , url =. doi:10.1145/3717823.3718299 , timestamp =

    2025

  14. [22]

    Discrete & Computational Geometry , volume=

    On approximate geometric k-clustering , author=. Discrete & Computational Geometry , volume=. 2000 , publisher=

    2000

  15. [23]

    Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages=

    Approximation schemes for clustering problems , author=. Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages=

  16. [24]

    Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets , booktitle =

    Cohen. Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets , booktitle =

  17. [25]

    and Shmoys, David B

    Williamson, David P. and Shmoys, David B. , isbn =

  18. [26]

    Maximizing a Monotone Submodular Function Subject to a Matroid Constraint , journal =

    Gruia C. Maximizing a Monotone Submodular Function Subject to a Matroid Constraint , journal =. 2011 , url =. doi:10.1137/080733991 , timestamp =

    2011 doi

  19. [27]

    CoRR , volume =

    Niv Buchbinder and Moran Feldman , title =. CoRR , volume =. 2024 , url =. doi:10.48550/ARXIV.2408.03583 , eprinttype =. 2408.03583 , timestamp =

    2024 doi

  20. [28]

    2014 , url =

    Yuval Filmus and Justin Ward , title =. 2014 , url =. doi:10.1137/130920277 , timestamp =

    2014 doi

  21. [29]

    International Conference on Integer Programming and Combinatorial Optimization , pages=

    Improved approximation algorithms for capacitated facility location problems , author=. International Conference on Integer Programming and Combinatorial Optimization , pages=. 1999 , organization=

    1999

  22. [30]

    Journal of algorithms , volume=

    Analysis of a local search heuristic for facility location problems , author=. Journal of algorithms , volume=. 2000 , publisher=

    2000

  23. [31]

    Proceedings 42nd IEEE symposium on foundations of computer science , pages=

    Facility location with nonuniform hard capacities , author=. Proceedings 42nd IEEE symposium on foundations of computer science , pages=. 2001 , organization=

    2001

  24. [32]

    Mathematical Programming , volume=

    A 3-approximation algorithm for the facility location problem with uniform capacities , author=. Mathematical Programming , volume=. 2013 , publisher=

    2013

  25. [33]

    European Symposium on Algorithms , pages=

    A 5-approximation for capacitated facility location , author=. European Symposium on Algorithms , pages=. 2012 , organization=

    2012

  26. [34]

    SIAM Journal on Computing , volume=

    LP-based algorithms for capacitated facility location , author=. SIAM Journal on Computing , volume=. 2017 , publisher=

    2017

  27. [35]

    A Dependent LP-Rounding Approach for the k-Median Problem , booktitle =

    Moses Charikar and Shi Li , editor =. A Dependent LP-Rounding Approach for the k-Median Problem , booktitle =

  28. [36]

    Shmoys , title =

    Aaron Archer and Ranjithkumar Rajagopalan and David B. Shmoys , title =. Algorithms -

  29. [37]

    A Constant-Factor Approximation Algorithm for the k-Median Problem , journal =

    Moses Charikar and Sudipto Guha and. A Constant-Factor Approximation Algorithm for the k-Median Problem , journal =

  30. [38]

    Management science , volume=

    A heuristic program for locating warehouses , author=. Management science , volume=. 1963 , publisher=

    1963

  31. [39]

    Journal of Farm Economics , volume=

    A working model for plant numbers and locations , author=. Journal of Farm Economics , volume=. 1963 , publisher=

    1963

  32. [40]

    and Welzl, E

    Haussler, D. and Welzl, E. , title =. Proceedings of the second annual symposium on Computational geometry , series =. 1986 , isbn =. doi:10.1145/10515.10522 , acmid =

    1986

  33. [41]

    CoRR , volume =

    Anupam Gupta and Kanat Tangwongsan , title =. CoRR , volume =. 2008 , url =

    2008

  34. [43]

    k-means++: few more steps yield constant approximation , booktitle =

    Davin Choo and Christoph Grunau and Julian Portmann and V. k-means++: few more steps yield constant approximation , booktitle =. 2020 , url =

    2020

  35. [44]

    Clustering under Local Stability: Bridging the Gap between Worst-Case and Beyond Worst-Case Analysis , journal =

    Maria. Clustering under Local Stability: Bridging the Gap between Worst-Case and Beyond Worst-Case Analysis , journal =. 2017 , url =

    2017

  36. [45]

    On the Local Structure of Stable Clustering Instances , booktitle =

    Vincent Cohen. On the Local Structure of Stable Clustering Instances , booktitle =. 2017 , url =. doi:10.1109/FOCS.2017.14 , timestamp =

    2017 doi

  37. [46]

    A Bi-Criteria Approximation Algorithm for k-Means , booktitle =

    Konstantin Makarychev and Yury Makarychev and Maxim Sviridenko and Justin Ward , editor =. A Bi-Criteria Approximation Algorithm for k-Means , booktitle =. 2016 , url =. doi:10.4230/LIPIcs.APPROX-RANDOM.2016.14 , timestamp =

    2016 doi

  38. [47]

    A Better k-means++ Algorithm via Local Search , booktitle =

    Silvio Lattanzi and Christian Sohler , editor =. A Better k-means++ Algorithm via Local Search , booktitle =. 2019 , url =

    2019

  39. [48]

    Proceedings of the 43rd

    Dan Feldman and Michael Langberg , title =. Proceedings of the 43rd

  40. [49]

    Vishnoi , editor =

    Lingxiao Huang and Nisheeth K. Vishnoi , editor =. Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal , booktitle =. 2020 , url =. doi:10.1145/3357713.3384296 , timestamp =

    2020

  41. [50]

    Amit Kumar and Yogish Sabharwal and Sandeep Sen , title =. J. 2010 , url =. doi:10.1145/1667053.1667054 , timestamp =

    2010

  42. [51]

    Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics , booktitle =

    Vincent Cohen. Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00041 , timestamp =

    2019

  43. [52]

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

    On Approximability of Clustering Problems Without Candidate Centers , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

    2021

  44. [53]

    Inapproximability of Clustering in Lp Metrics , booktitle =

    Vincent Cohen. Inapproximability of Clustering in Lp Metrics , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00040 , timestamp =

    2019

  45. [54]

    2003 , url =

    Sudipto Guha and Adam Meyerson and Nina Mishra and Rajeev Motwani and Liadan O'Callaghan , title =. 2003 , url =. doi:10.1109/TKDE.2003.1198387 , timestamp =

    2003 arXiv

  46. [55]

    Mount and Nathan S

    Tapas Kanungo and David M. Mount and Nathan S. Netanyahu and Christine D. Piatko and Ruth Silverman and Angela Y. Wu , title =. Comput. Geom. , volume =. 2004 , url =. doi:10.1016/j.comgeo.2004.03.003 , timestamp =

    2004 doi

  47. [56]

    Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics , journal =

    Vincent Cohen. Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics , journal =. 2019 , url =. doi:10.1137/17M112717X , timestamp =

    2019 doi

  48. [57]

    Salavatipour , title =

    Zachary Friggstad and Mohsen Rezapour and Mohammad R. Salavatipour , title =. 2019 , url =. doi:10.1137/17M1127181 , timestamp =

    2019 doi

  49. [58]

    2004 , url =

    Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit , title =. 2004 , url =. doi:10.1137/S0097539702416402 , timestamp =

    2004 doi

  50. [59]

    Pensyl and Bartosz Rybicki and Aravind Srinivasan and Khoa Trinh , title =

    Jaroslaw Byrka and Thomas W. Pensyl and Bartosz Rybicki and Aravind Srinivasan and Khoa Trinh , title =. 2017 , url =. doi:10.1145/2981561 , timestamp =

    2017 doi

  51. [60]

    Pensyl and Bartosz Rybicki and Aravind Srinivasan and Khoa Trinh , editor =

    Jaroslaw Byrka and Thomas W. Pensyl and Bartosz Rybicki and Aravind Srinivasan and Khoa Trinh , editor =. An Improved Approximation for. Proceedings of the Twenty-Sixth Annual. 2015 , url =. doi:10.1137/1.9781611973730.50 , timestamp =

    2015 doi

  52. [61]

    2016 , url =

    Shi Li and Ola Svensson , title =. 2016 , url =. doi:10.1137/130938645 , timestamp =

    2016 doi

  53. [62]

    Variational shape approximation , journal =

    David Cohen. Variational shape approximation , journal =. 2004 , url =. doi:10.1145/1015706.1015817 , timestamp =

    2004

  54. [63]

    43rd International Colloquium on Automata, Languages, and Programming,

    Zachary Friggstad and Yifeng Zhang , title =. 43rd International Colloquium on Automata, Languages, and Programming,. 2016 , crossref =. doi:10.4230/LIPIcs.ICALP.2016.75 , timestamp =

    2016 doi

  55. [64]

    Finding Meaningful Cluster Structure Amidst Background Noise , booktitle =

    Shrinu Kushagra and Samira Samadi and Shai Ben. Finding Meaningful Cluster Structure Amidst Background Noise , booktitle =. 2016 , crossref =. doi:10.1007/978-3-319-46379-7_23 , timestamp =

    2016 doi

  56. [65]

    CoRR , volume =

    Ainesh Bakshi and Nadiia Chepurko , title =. CoRR , volume =. 2016 , url =

    2016

  57. [66]

    k-Center Clustering Under Perturbation Resilience , booktitle =

    Maria. k-Center Clustering Under Perturbation Resilience , booktitle =. 2016 , crossref =. doi:10.4230/LIPIcs.ICALP.2016.68 , timestamp =

    2016 doi

  58. [67]

    Proceedings of the First

    Yi Yang and Min Shao and Sencun Zhu and Bhuvan Urgaonkar and Guohong Cao , title =. Proceedings of the First. 2008 , crossref =. doi:10.1145/1352533.1352547 , timestamp =

    2008

  59. [68]

    Dhillon and Yuqiang Guan and Jacob Kogan , title =

    Inderjit S. Dhillon and Yuqiang Guan and Jacob Kogan , title =. Proceedings of the 2002. 2002 , crossref =. doi:10.1109/ICDM.2002.1183895 , timestamp =

    2002 arXiv

  60. [69]

    Pattern Recognition , volume =

    Pierre Hansen and Nenad Mladenovic , title =. Pattern Recognition , volume =. 2001 , url =. doi:10.1016/S0031-3203(99)00216-2 , timestamp =

    2001 doi

  61. [70]

    Proceedings of the 27th Canadian Conference on Computational Geometry,

    Michael Kerber and Sharath Raghvendra , title =. Proceedings of the 27th Canadian Conference on Computational Geometry,. 2015 , crossref =

    2015

  62. [71]

    32nd International Symposium on Computational Geometry (SoCG 2016) , year=

    On Variants of k-means Clustering , author=. 32nd International Symposium on Computational Geometry (SoCG 2016) , year=

    2016

  63. [72]

    Salavatipour , title =

    Zachary Friggstad and Mohsen Rezapour and Mohammad R. Salavatipour , title =. CoRR , volume =. 2016 , url =

    2016

  64. [73]

    The power of

    Vincent Cohen. The power of. CoRR , volume =. 2016 , url =

    2016

  65. [74]

    Effectiveness of Local Search for Geometric Optimization , booktitle =

    Vincent Cohen. Effectiveness of Local Search for Geometric Optimization , booktitle =. 2015 , crossref =. doi:10.4230/LIPIcs.SOCG.2015.329 , timestamp =

    2015 doi

  66. [75]

    Mirrokni , title =

    MohammadHossein Bateni and Aditya Bhaskara and Silvio Lattanzi and Vahab S. Mirrokni , title =. Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada , pages =. 2014 ,...

    2014

  67. [76]

    Blelloch and Kanat Tangwongsan , title =

    Guy E. Blelloch and Kanat Tangwongsan , title =. 2010 , crossref =. doi:10.1145/1810479.1810535 , timestamp =

    2010

  68. [77]

    Local Search in Combinatorial Optimization , year =

  69. [78]

    Korupolu and C

    Madhukar R. Korupolu and C. Greg Plaxton and Rajmohan Rajaraman , title =. J. Algorithms , volume =. 2000 , url =. doi:10.1006/jagm.2000.1100 , timestamp =

    2000

  70. [79]

    The volume of convex bodies and Banach space geometry

    Pisier, Gilles. The volume of convex bodies and Banach space geometry. 1999

    1999

  71. [80]

    Johnson, W. B. and Lindenstrauss, J. , booktitle =

  72. [82]

    Approximation, Randomization, and Combinatorial Optimization

    Pranjal Awasthi and Or Sheffet , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop,. 2012 , crossref =. doi:10.1007/978-3-642-32512-0_4 , timestamp =

    2012 doi

  73. [83]

    Machine Learning , volume =

    Daniel Aloise and Amit Deshpande and Pierre Hansen and Preyas Popat , title =. Machine Learning , volume =. 2009 , url =. doi:10.1007/s10994-009-5103-0 , timestamp =

    2009 doi

  74. [84]

    Proceedings of the Thirtieth Annual

    Sanjeev Arora and Prabhakar Raghavan and Satish Rao , title =. Proceedings of the Thirtieth Annual. 1998 , url =. doi:10.1145/276698.276718 , timestamp =

    1998

  75. [85]

    Smaller Coresets for k-Median and k-Means Clustering , journal =

    Sariel Har. Smaller Coresets for k-Median and k-Means Clustering , journal =. 2007 , url =. doi:10.1007/s00454-006-1271-x , timestamp =

    2007 doi

  76. [86]

    On coresets for k-means and k-median clustering , booktitle =

    Sariel Har. On coresets for k-means and k-median clustering , booktitle =. 2004 , crossref =. doi:10.1145/1007352.1007400 , timestamp =

    2004

  77. [87]

    Mettu and C

    Ramgopal R. Mettu and C. Greg Plaxton , title =. 2003 , url =. doi:10.1137/S0097539701383443 , timestamp =

    2003 doi

  78. [88]

    Schulman , title =

    Leonard J. Schulman , title =. Proceedings of the Thirty-Second Annual. 2000 , crossref =. doi:10.1145/335305.335373 , timestamp =

    2000

  79. [89]

    Schulman and Chaitanya Swamy , title =

    Rafail Ostrovsky and Yuval Rabani and Leonard J. Schulman and Chaitanya Swamy , title =. J. 2012 , url =. doi:10.1145/2395116.2395117 , timestamp =

    2012

  80. [90]

    Proceedings of the 43rd

    Dan Feldman and Michael Langberg , title =. Proceedings of the 43rd. 2011 , crossref =. doi:10.1145/1993636.1993712 , timestamp =

    2011

  81. [92]

    A Constant-Factor Approximation Algorithm for the

    Moses Charikar and Sudipto Guha and. A Constant-Factor Approximation Algorithm for the. Proceedings of the Thirty-First Annual. 1999 , url =. doi:10.1145/301250.301257 , timestamp =

    1999

  82. [93]

    Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013 , pages =

    Shi Li and Ola Svensson , title =. Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013 , pages =. 2013 , url =. doi:10.1145/2488608.2488723 , timestamp =

    2013

  83. [95]

    Supowit , title =

    Nimrod Megiddo and Kenneth J. Supowit , title =. 1984 , url =. doi:10.1137/0213014 , timestamp =

    1984 doi

  84. [96]

    Varadarajan , title =

    Meena Mahajan and Prajakta Nimbhorkar and Kasturi R. Varadarajan , title =. Theor. Comput. Sci. , volume =. 2012 , url =. doi:10.1016/j.tcs.2010.05.034 , timestamp =

    2012 doi

  85. [97]

    Proceedings on 34th Annual

    Kamal Jain and Mohammad Mahdian and Amin Saberi , title =. Proceedings on 34th Annual. 2002 , url =. doi:10.1145/509907.510012 , timestamp =

    2002

  86. [98]

    Sudipto Guha and Samir Khuller , title =. J. Algorithms , volume =. 1999 , url =. doi:10.1006/jagm.1998.0993 , timestamp =

    1999

  87. [99]

    51th Annual

    Amit Kumar and Ravindran Kannan , title =. 51th Annual. 2010 , crossref =. doi:10.1109/FOCS.2010.35 , timestamp =

    2010 doi

  88. [100]

    Cohen and Sam Elder and Cameron Musco and Christopher Musco and Madalina Persu , title =

    Michael B. Cohen and Sam Elder and Cameron Musco and Christopher Musco and Madalina Persu , title =. Proceedings of the Forty-Seventh Annual. 2015 , crossref =. doi:10.1145/2746539.2746569 , timestamp =

    2015

  89. [101]

    Feldman and M

    D. Feldman and M. Schmidt and C. Sohler , title =. SODA , year =

  90. [102]

    Achlioptas , title =

    D. Achlioptas , title =. J. Comput. Syst. Sci. , volume =. 2003 , url =. doi:10.1016/S0022-0000(03)00025-4 , timestamp =

    2003 doi

  91. [103]

    Vladimir Braverman and Harry Lang and Keith Levin and Morteza Monemizadeh , title =. 35th. 2015 , crossref =. doi:10.4230/LIPIcs.FSTTCS.2015.350 , timestamp =

    2015 doi

  92. [104]

    Proceedings of the Twenty-Seventh Annual

    Vladimir Braverman and Harry Lang and Keith Levin and Morteza Monemizadeh , title =. Proceedings of the Twenty-Seventh Annual. 2016 , crossref =. doi:10.1137/1.9781611974331.ch95 , timestamp =

    2016 doi

  93. [105]

    Shannon , journal=

    Claude E. Shannon , journal=. A mathematical theory of communication , year=. doi:10.1002/j.1538-7305.1948.tb01338.x , ISSN=

    1948

  94. [106]

    Kane and J

    D. Kane and J. Nelson , title =. J. 2014 , url =. doi:10.1145/2559902 , timestamp =

    2014 doi

  95. [107]

    Mahoney and S

    Petros Drineas and Michael W. Mahoney and S. Muthukrishnan , title =. SODA , year =

  96. [108]

    Varadarajan , title =

    Ashish Goel and Piotr Indyk and Kasturi R. Varadarajan , title =. Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC,. 2001 , url =

    2001

  97. [109]

    Electronic Colloquium on Computational Complexity (ECCC) , volume =

    Amit Deshpande and Santosh Vempala , title =. Electronic Colloquium on Computational Complexity (ECCC) , volume =

  98. [110]

    Mahoney and S

    Petros Drineas and Michael W. Mahoney and S. Muthukrishnan , title =. ESA , year =

  99. [111]

    Mahoney and S

    Petros Drineas and Michael W. Mahoney and S. Muthukrishnan , title =. APPROX-RANDOM , year =

  100. [112]

    FOCS , year =

    Amit Deshpande and Luis Rademacher , title =. FOCS , year =

  101. [113]

    Mahoney , title =

    Petros Drineas and Ravi Kannan and Michael W. Mahoney , title =. SIAM J. Comput. , volume =. 2006 , pages =

    2006

  102. [114]

    Frank Rosenblatt , title =

  103. [115]

    and Kwok, J

    Tsang, I. and Kwok, J. and Cheung, P. , title =. J. Mach. Learn. Res. , issue_date =. 2005 , issn =

    2005

  104. [116]

    and Daum

    Rai, P. and Daum. Streamed learning: one-pass SVMs , booktitle =. 2009 , location =

    2009

  105. [117]

    and Chan, T

    Zarrabi-Zadeh, H. and Chan, T. , title =. CCCG , year =

  106. [118]

    and Pathak, V

    Chan, T. and Pathak, V. , title =. Proceedings of the 12th international conference on Algorithms and data structures , series =. 2011 , isbn =

    2011

  107. [119]

    and Warmuth, M

    Auer, P. and Warmuth, M. , pages=. Machine Learning , volume=. 1998 , issn=. doi:10.1023/A:1007472513967 , title=

    1998 doi

  108. [120]

    , title =

    Valiant, L. , title =. Commun. ACM , issue_date =. 1984 , issn =. doi:10.1145/1968.1972 , acmid =

    1984

  109. [121]

    and Schapire, R

    Freund, Y. and Schapire, R. , title =. Mach. Learn. , issue_date =. 1999 , issn =. doi:10.1023/A:1007662407062 , acmid =

    1999 doi

  110. [122]

    and Ehrenfeucht, A

    Blumer, A. and Ehrenfeucht, A. and Haussler, D. and Warmuth, M. , title =. Proceedings of the eighteenth annual ACM symposium on Theory of computing , series =. 1986 , isbn =. doi:10.1145/12130.12158 , acmid =

    1986

  111. [123]

    and Ehrenfeucht, A

    Blumer, A. and Ehrenfeucht, A. and Haussler, D. and Warmuth, M. , title =. J. ACM , issue_date =. 1989 , issn =. doi:10.1145/76359.76371 , acmid =

    1989

  112. [124]

    and Kann, V

    Amaldi, E. and Kann, V. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science. 1998. doi:10.1016/S0304-3975(97)00115-1

    1998 doi

  113. [125]

    and Har-Peled, S

    Agarwal, P. and Har-Peled, S. and Varadarajan, K. , title =. J. ACM , volume =. 2004 , pages =

    2004

  114. [126]

    and Chervonenkis, A

    Vapnik, V. and Chervonenkis, A. , biburl =. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities , url =. Theory of Probability and its Applications , keywords =. doi:10.1137/1116025 , interhash =

    doi

  115. [127]

    and Spencer, J

    Alon, N. and Spencer, J. , title =. 1992 , isbn =

    1992

  116. [128]

    and Hazan, E

    Clarkson, K. and Hazan, E. and Woodruff, D. , title =. J. ACM , volume =. 2012 , pages =

    2012

  117. [129]

    , title =

    Nisan, N. , title =. STOC , year =

  118. [130]

    , title =

    Chan, T. , title =. Comput. Geom. Theory Appl , year =

  119. [131]

    and Sharathkumar, R

    Agarwal, P. and Sharathkumar, R. , title =. in SODA ’10: Proc. Twenty-First ACM-SIAM Symposium on Discrete Algorithms , year =

  120. [132]

    , title =

    Muthukrishnan, S. , title =. Foundations and Trends in Theoretical Computer Science , volume =. 2005 , ee =

    2005

  121. [133]

    , title =

    Muthukrishnan, S. , title =. SODA , year =

  122. [134]

    and Nguyen, H

    Andoni, A. and Nguyen, H. , title =. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms , series =. 2012 , location =

    2012

  123. [135]

    Clarkson and D

    K. Clarkson and D. Woodruff , title =. STOC , year =

  124. [136]

    and Frieze, A

    Drineas, P. and Frieze, A. and Kannan, R. and Vempala, S. and Vinay, V. , title =. Mach. Learn. , volume =. 2004 , issn =

    2004

  125. [137]

    M. B. Approximate clustering via core-sets , booktitle =. 2002 , pages =

    2002

  126. [138]

    2001 , isbn =

    Bernard Chazelle , title =. 2001 , isbn =

    2001

  127. [139]

    and Hazan, E

    Clarkson, K. and Hazan, E. and Woodruff, D. , booktitle=. Sublinear Optimization for Machine Learning , year=. doi:10.1109/FOCS.2010.50 , ISSN=

    2010 doi

  128. [140]

    , title =

    Zinkevich, M. , title =. ICML , year =

  129. [141]

    and Kale, S

    Hazan, E. and Kale, S. , title =. Journal of Machine Learning Research - Proceedings Track , volume =. 2011 , pages =

    2011

  130. [142]

    T. Sarl. Improved Approximation Algorithms for Large Matrices via Random Projections , booktitle =. 2006 , pages =

    2006

  131. [143]

    Chan , title =

    Timothy M. Chan , title =. Comput. Geom. , volume =. 2006 , pages =

    2006

  132. [144]

    Gereon Frahling and Piotr Indyk and Christian Sohler , title =. Int. J. Comput. Geometry Appl. , volume =. 2008 , pages =

    2008

  133. [145]

    , title =

    Bagchi, Amitabha and Chaudhary, Amitabh and Eppstein, David and Goodrich, Michael T. , title =. ACM Trans. Algorithms , issue_date =. 2007 , issn =. doi:10.1145/1240233.1240239 , acmid =

    2007

  134. [146]

    IJCAI , year =

    Sariel Har-Peled and Dan Roth and Dav Zimak , title =. IJCAI , year =

  135. [147]

    Agarwal and Sariel Har-peled and Kasturi and R

    Pankaj K. Agarwal and Sariel Har-peled and Kasturi and R. Varadarajan , title =. Combinatorial and Computational Geometry, MSRI , year =

  136. [148]

    CoRR , volume =

    Ravindran Kannan and Santosh Vempala , title =. CoRR , volume =. 2013 , ee =

    2013

  137. [149]

    Spielman and Shang-Hua Teng , title =

    Daniel A. Spielman and Shang-Hua Teng , title =. J. ACM , volume =. 2004 , pages =

    2004

  138. [150]

    STOC , year =

    Gereon Frahling and Christian Sohler , title =. STOC , year =

  139. [151]

    STOC , year =

    Piotr Indyk and Eric Price , title =. STOC , year =

  140. [152]

    On the combinatorial and algebraic complexity of quantifier elimination , journal =

    Basu, Saugata and Pollack, Richard and Roy, Marie-Fran. On the combinatorial and algebraic complexity of quantifier elimination , journal =. 1996 , issn =. doi:10.1145/235809.235813 , acmid =

    1996

  141. [153]

    Kalyanasundaram, Bala and Schintger, Georg , title =. SIAM J. Discret. Math. , issue_date =. 1992 , issn =. doi:10.1137/0405044 , acmid =

    1992 doi

  142. [154]

    Razborov , title =

    Alexander A. Razborov , title =. Theor. Comput. Sci. , volume =. 1992 , pages =

    1992

  143. [155]

    Lower bounds for one-way probabilistic communication complexity and their application to space complexity

    Farid Ablayev. Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science. 1996. doi:http://dx.doi.org/10.1016/0304-3975(95)00157-3

    1996 doi

  144. [156]

    M. R. Ackermann and M. M. StreamKM++: A clustering algorithm for data streams , journal =

  145. [157]

    P. K. Agarwal and J. Erickson , journal =. 1999 , title =

    1999

  146. [158]

    P. K. Agarwal and S. Har-Peled and K. R. Varadarajan , title =. Journal of the ACM , volume =. 2004 , pages =

    2004

  147. [159]

    J. L. Bentley and J. B. Saxe , title =. J. Algorithms , volume =. 1980 , pages =

    1980

  148. [160]

    O'Callaghan and A

    L. O'Callaghan and A. Meyerson and R. Motwani and N. Mishra and S. Guha , title =. 18th ICDE , year =

  149. [161]

    Guha and A

    S. Guha and A. Meyerson and N. Mishra and R. Motwani and L. O'Callaghan , title =. IEEE TKDE , volume =. 2003 , pages =

    2003

  150. [162]

    Guha and N

    S. Guha and N. Mishra and R. Motwani and L. O'Callaghan , title =. FOCS , year =

  151. [163]

    Chen , title =

    K. Chen , title =. SIAM Journal on Computing , volume =. 2009 , pages =

    2009

  152. [164]

    IEEE, Special Issue on Computational Geometry , volume =

    Dynamic Algorithms in Computational Geometry , author =. IEEE, Special Issue on Computational Geometry , volume =

  153. [165]

    Lawrence Carter and M

    J. Lawrence Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences. 1979. doi:10.1016/0022-0000(79)90044-8

    1979 doi

  154. [166]

    G. A. Fink and T. Pl\"otz , title =

  155. [167]

    Feldman and M

    D. Feldman and M. Langberg , title =. STOC , year =

  156. [168]

    Feldman and M

    D. Feldman and M. Monemizadeh and C. Sohler , title =. SoCG , year =

  157. [169]

    Frahling and C

    G. Frahling and C. Sohler , title =. STOC , year =

  158. [170]

    Har-Peled and S

    S. Har-Peled and S. Mazumdar , title =. STOC , year =

  159. [171]

    D. G. Lowe , title =. International Journal of Computer Vision , year =

  160. [172]

    Langberg and L

    M. Langberg and L. J. Schulman , title =. SODA , year =

  161. [173]

    Mehlhorn , title =

    K. Mehlhorn , title =. 1984 , isbn =

    1984

  162. [174]

    Mehlhorn and S

    K. Mehlhorn and S. N. Dynamic Fractional Cascading , journal =. 1990 , pages =

    1990

  163. [175]

    M. H. Overmars , title =. 1983 , isbn =

    1983

  164. [176]

    Sander and M

    J. Sander and M. Ester and H.-P. Kriegel and X. Xu , title =. Data Min. Knowl. Discov. , volume =. 1998 , pages =

    1998

  165. [177]

    Ester and H.-P

    M. Ester and H.-P. Kriegel and J. Sander and X. Xu , title =. KDD , year =

  166. [178]

    Xu and D

    R. Xu and D. C. Wunsch II , title =. IEEE Trans. on Neural Networks , volume =. 2005 , pages =

    2005

  167. [179]

    Har-Peled and A

    S. Har-Peled and A. Kushal , title =. Discrete. 2007 , pages =

    2007

  168. [180]

    IEEE Trans

    Stuart Lloyd , title =. IEEE Trans. on Inform. Theory , year=

  169. [181]

    Graph Partitioning via Adaptive Spectral Techniques , journal =

    Amin Coja. Graph Partitioning via Adaptive Spectral Techniques , journal =. 2010 , url =. doi:10.1017/S0963548309990514 , timestamp =

    2010 doi

  170. [182]

    Arthur and S

    D. Arthur and S. Vassilvitskii , title =. SoCG , year =

  171. [183]

    J. B. MacQueen , biburl =. 5th Berkeley Symp. on Math., Stat., and Prob. , keywords =

  172. [184]

    Approximation, Randomization, and Combinatorial Optimization

    Ragesh Jaiswal and Nitin Garg , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop,. 2012 , crossref =. doi:10.1007/978-3-642-32512-0_50 , timestamp =

    2012 doi

  173. [185]

    Data stability in clustering:

    Shalev Ben. Data stability in clustering:. Theor. Comput. Sci. , volume =. 2014 , url =. doi:10.1016/j.tcs.2014.09.025 , timestamp =

    2014 doi

  174. [186]

    Pranjal Awasthi and Avrim Blum and Or Sheffet , title =. Inf. Process. Lett. , volume =. 2012 , url =. doi:10.1016/j.ipl.2011.10.006 , timestamp =

    2012 doi

  175. [187]

    Clustering under Perturbation Resilience , journal =

    Maria. Clustering under Perturbation Resilience , journal =. 2016 , url =. doi:10.1137/140981575 , timestamp =

    2016 doi

  176. [188]

    Clustering under Perturbation Resilience , booktitle =

    Maria. Clustering under Perturbation Resilience , booktitle =. 2012 , crossref =. doi:10.1007/978-3-642-31594-7_6 , timestamp =

    2012 doi

  177. [189]

    2009 , url =

    David Arthur and Sergei Vassilvitskii , title =. 2009 , url =. doi:10.1137/070683921 , timestamp =

    2009 doi

  178. [190]

    Smoothed Analysis of the k-Means Method , journal =

    David Arthur and Bodo Manthey and Heiko R. Smoothed Analysis of the k-Means Method , journal =. 2011 , url =. doi:10.1145/2027216.2027217 , timestamp =

    2011

  179. [191]

    Saks , title =

    Yonatan Bilu and Amit Daniely and Nati Linial and Michael E. Saks , title =. 30th International Symposium on Theoretical Aspects of Computer Science,. 2013 , crossref =. doi:10.4230/LIPIcs.STACS.2013.526 , timestamp =

    2013 doi

  180. [192]

    Combinatorics, Probability

    Yonatan Bilu and Nathan Linial , title =. Combinatorics, Probability. 2012 , url =. doi:10.1017/S0963548312000193 , timestamp =

    2012 doi

  181. [193]

    Approximate clustering without the approximation , booktitle =

    Maria. Approximate clustering without the approximation , booktitle =. 2009 , crossref =

    2009

  182. [194]

    Agnostic Clustering , booktitle =

    Maria. Agnostic Clustering , booktitle =. 2009 , crossref =. doi:10.1007/978-3-642-04414-4_31 , timestamp =

    2009 doi

  183. [195]

    Manu Agarwal and Ragesh Jaiswal and Arindam Pal , title =. Theor. Comput. Sci. , volume =. 2015 , url =. doi:10.1016/j.tcs.2015.04.030 , timestamp =

    2015 doi

  184. [196]

    Frans Schalekamp and Michael Yu and Anke van Zuylen , title =. J. Comb. Optim. , volume =. 2013 , url =. doi:10.1007/s10878-011-9382-6 , timestamp =

    2013 doi

  185. [197]

    Finding Low Error Clusterings , booktitle =

    Maria. Finding Low Error Clusterings , booktitle =. 2009 , crossref =

    2009

  186. [198]

    Clustering under approximation stability , journal =

    Maria. Clustering under approximation stability , journal =. 2013 , url =. doi:10.1145/2450142.2450144 , timestamp =

    2013

  187. [199]

    51th Annual

    Mikhail Belkin and Kaushik Sinha , title =. 51th Annual. 2010 , crossref =. doi:10.1109/FOCS.2010.16 , timestamp =

    2010 doi

  188. [200]

    42nd Annual Symposium on Foundations of Computer Science,

    Frank McSherry , title =. 42nd Annual Symposium on Foundations of Computer Science,. 2001 , crossref =. doi:10.1109/SFCS.2001.959929 , timestamp =

    2001

  189. [201]

    Learning Theory, 18th Annual Conference on Learning Theory,

    Dimitris Achlioptas and Frank McSherry , title =. Learning Theory, 18th Annual Conference on Learning Theory,. 2005 , crossref =. doi:10.1007/11503415_31 , timestamp =

    2005 doi

  190. [202]

    Hopcroft and Ravi Kannan and Pradipta Prometheus Mitra , title =

    Anirban Dasgupta and John E. Hopcroft and Ravi Kannan and Pradipta Prometheus Mitra , title =. Proceedings of the Eighteenth Annual. 2007 , crossref =

    2007

  191. [203]

    Charles Brubaker and Santosh Vempala , title =

    S. Charles Brubaker and Santosh Vempala , title =. 49th Annual. 2008 , crossref =. doi:10.1109/FOCS.2008.48 , timestamp =

    2008 doi

  192. [204]

    2008 , url =

    Ravindran Kannan and Hadi Salmasian and Santosh Vempala , title =. 2008 , url =. doi:10.1137/S0097539704445925 , timestamp =

    2008 doi

  193. [205]

    Santosh Vempala and Grant Wang , title =. J. Comput. Syst. Sci. , volume =. 2004 , url =. doi:10.1016/j.jcss.2003.11.008 , timestamp =

    2004 doi

  194. [206]

    Proceedings on 33rd Annual

    Sanjeev Arora and Ravi Kannan , title =. Proceedings on 33rd Annual. 2001 , crossref =. doi:10.1145/380752.380808 , timestamp =

    2001

  195. [207]

    Schulman , title =

    Sanjoy Dasgupta and Leonard J. Schulman , title =. Journal of Machine Learning Research , volume =. 2007 , url =

    2007

  196. [208]

    40th Annual Symposium on Foundations of Computer Science,

    Sanjoy Dasgupta , title =. 40th Annual Symposium on Foundations of Computer Science,. 1999 , crossref =. doi:10.1109/SFFCS.1999.814639 , timestamp =

    1999

  197. [209]

    2009 , url =

    Sanjoy Dasgupta and Yoav Freund , title =. 2009 , url =. doi:10.1109/TIT.2009.2021326 , timestamp =

    2009

  198. [210]

    Proceedings of the Twenty-Second Annual

    Vladimir Braverman and Adam Meyerson and Rafail Ostrovsky and Alan Roytman and Michael Shindler and Brian Tagiku , title =. Proceedings of the Twenty-Second Annual. 2011 , crossref =. doi:10.1137/1.9781611973082.3 , timestamp =

    2011 doi

  199. [211]

    51th Annual

    Pranjal Awasthi and Avrim Blum and Or Sheffet , title =. 51th Annual. 2010 , url =. doi:10.1109/FOCS.2010.36 , timestamp =

    2010 doi

  200. [212]

    Shmoys , editor =

    Aaron Archer and Ranjithkumar Rajagopalan and David B. Shmoys , editor =. Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties , booktitle =. 2003 , url =. doi:10.1007/978-3-540-39658-1\_6 , timestamp =

    2003 doi

  201. [213]

    Proceedings of the Eighteenth Annual

    David Arthur and Sergei Vassilvitskii , title =. Proceedings of the Eighteenth Annual. 2007 , url =

    2007

  202. [214]

    Guha and R

    S. Guha and R. Rastogi and K. Shim , title =. Inform. Systems , volume =. 2001 , pages =

    2001

  203. [215]

    Guha and R

    S. Guha and R. Rastogi and K. Shim , title =. Inform. Systems , volume =. 2000 , pages =

    2000

  204. [216]

    Boutsidis and A

    C. Boutsidis and A. Zouzias and M. W. Mahoney and P. Drineas , title =. 2015 , url =. doi:10.1109/TIT.2014.2375327 , timestamp =

    2015

  205. [217]

    Boutsidis and M

    C. Boutsidis and M. Magdon. Deterministic Feature Selection for k-Means Clustering , journal =. 2013 , url =. doi:10.1109/TIT.2013.2255021 , timestamp =

    2013

  206. [218]

    Drineas and A

    P. Drineas and A. Frieze and R. Kannan and S. Vempala and V. Vinay , title =. Machine Learning , volume =. 2004 , url =. doi:10.1023/B:MACH.0000033113.59016.96 , timestamp =

    2004

  207. [219]

    Dasgupta and R

    A. Dasgupta and R. Kumar and T. Sarl. A sparse. 2010 , crossref =. doi:10.1145/1806689.1806734 , timestamp =

    2010

  208. [220]

    Braverman and R

    V. Braverman and R. Ostrovsky and Y. Rabani , title =. CoRR , volume =. 2010 , url =

    2010

  209. [221]

    Razenshteyn , editor =

    Konstantin Makarychev and Yury Makarychev and Ilya P. Razenshteyn , editor =. Performance of Johnson-Lindenstrauss transform for. Proceedings of the 51st Annual. 2019 , url =. doi:10.1145/3313276.3316350 , timestamp =

    2019

  210. [222]

    On Approximate Geometric k-Clustering , journal =

    Jir. On Approximate Geometric k-Clustering , journal =. 2000 , url =. doi:10.1007/S004540010019 , timestamp =

    2000 doi

  211. [223]

    D. H. Fisher , title =. Machine Learning , volume =. 1987 , pages =

    1987

  212. [224]

    R. T. Ng and J. Han , title =. IEEE TKDE , volume =. 2002 , pages =

    2002

  213. [225]

    Euiwoong Lee and Melanie Schmidt and John Wright , title =. Inf. Process. Lett. , volume =. 2017 , url =. doi:10.1016/J.IPL.2016.11.009 , timestamp =

    2017 doi

  214. [226]

    Fichtenberger and M

    H. Fichtenberger and M. Gill. ESA , pages =. 2013 , crossref =. doi:10.1007/978-3-642-40450-4_41 , timestamp =

    2013 doi

  215. [227]

    Shindler and A

    M. Shindler and A. Wong and A. Meyerson , title =. NIPS , pages =. 2011 , crossref =

    2011

  216. [228]

    Ailon and R

    N. Ailon and R. Jaiswal and C. Monteleoni , title =. NIPS , pages =. 2009 , crossref =

    2009

  217. [229]

    Samet , title =

    H. Samet , title =. 2005 , publisher =

    2005

  218. [230]

    Zhang and R

    T. Zhang and R. Ramakrishnan and M. Livny , title =. Data Mining and Knowledge Discovery , volume =. 1997 , pages =

    1997

  219. [231]

    Clarkson and D

    K. Clarkson and D. Woodruff , title =. STOC , pages =. 2013 , crossref =. doi:10.1145/2488608.2488620 , timestamp =

    2013

  220. [232]

    Schulman and Rakesh Venkat , title =

    Fabrizio Grandoni and Rafail Ostrovsky and Yuval Rabani and Leonard J. Schulman and Rakesh Venkat , title =. Inf. Process. Lett. , volume =. 2022 , url =. doi:10.1016/J.IPL.2022.106251 , timestamp =

    2022

  221. [233]

    Liberty and R

    E. Liberty and R. Sriharsha and M. Sviridenko , title =. CoRR , volume =. 2014 , url =

    2014

  222. [234]

    Indyk , title =

    P. Indyk , title =. STOC , pages =. 1999 , crossref =. doi:10.1145/301250.301366 , timestamp =

    1999

  223. [235]

    Jain and V

    K. Jain and V. Vazirani , title =. J. 2001 , url =. doi:10.1145/375827.375845 , biburl =

    2001

  224. [236]

    Incremental Clustering and Dynamic Information Retrieval , booktitle =

    Moses Charikar and Chandra Chekuri and Tom. Incremental Clustering and Dynamic Information Retrieval , booktitle =. 1997 , crossref =. doi:10.1145/258533.258657 , timestamp =

    1997

  225. [237]

    Chan and Bashir S

    Timothy M. Chan and Bashir S. Sadjad , title =. Int. J. Comput. Geometry Appl. , volume =. 2006 , url =. doi:10.1142/S0218195906001975 , timestamp =

    2006 doi

  226. [238]

    Algorithmica , volume =

    Joan Feigenbaum and Sampath Kannan and Jian Zhang , title =. Algorithmica , volume =. 2004 , url =. doi:10.1007/s00453-004-1105-2 , timestamp =

    2004 doi

  227. [239]

    Proceedings of the Fourteenth Annual

    Piotr Indyk , title =. Proceedings of the Fourteenth Annual. 2003 , crossref =

    2003

  228. [240]

    Agarwal and Jir

    Pankaj K. Agarwal and Jir. Farthest Neighbors, Maximum Spanning Trees and Related Problems in Higher Dimensions , journal =. 1991 , url =. doi:10.1016/0925-7721(92)90001-9 , timestamp =

    1991 doi

  229. [241]

    Database Theory -

    Sudipto Guha , title =. Database Theory -. 2009 , crossref =. doi:10.1145/1514894.1514926 , timestamp =

    2009

  230. [242]

    Guha and N

    S. Guha and N. Mishra and R. Motwani and L. O'Callaghan , title =. FOCS , pages =. 2000 , crossref =. doi:10.1109/SFCS.2000.892124 , timestamp =

    2000

  231. [243]

    Fei-Fei and R

    L. Fei-Fei and R. Fergus and P. Perona , title =. Computer Vision and Image Understanding , volume =. 2007 , issn =

    2007

  232. [244]

    Asuncion, D

    A. Asuncion, D. J. Newman. UCI Machine Learning Repository. 2007

    2007

  233. [245]

    Halkidi and Y

    M. Halkidi and Y. Batistakis and M. Vazirgiannis , title =. Journal of Intelligent Inform. Systems , issue_date =. 2001 , issn =

    2001

  234. [246]

    Hochbaum and David B

    Dorit S. Hochbaum and David B. Shmoys , title =. J. 1986 , url =. doi:10.1145/5925.5933 , timestamp =

    1986

  235. [247]

    2002 , url =

    Mayur Datar and Aristides Gionis and Piotr Indyk and Rajeev Motwani , title =. 2002 , url =. doi:10.1137/S0097539701398363 , timestamp =

    2002 doi

  236. [248]

    2010 , url =

    Vladimir Braverman and Rafail Ostrovsky , title =. 2010 , url =. doi:10.1137/090749281 , timestamp =

    2010 doi

  237. [249]

    48th Annual

    Vladimir Braverman and Rafail Ostrovsky , title =. 48th Annual. 2007 , crossref =. doi:10.1109/FOCS.2007.63 , timestamp =

    2007 doi

  238. [250]

    Gonzalez , title =

    Teofilo F. Gonzalez , title =. Theor. Comput. Sci. , volume =. 1985 , url =. doi:10.1016/0304-3975(85)90224-5 , timestamp =

    1985 doi

  239. [251]

    CoRR , volume =

    Sepehr Assadi and Sanjeev Khanna and Yang Li and Grigory Yaroslavtsev , title =. CoRR , volume =. 2015 , url =

    2015

  240. [252]

    Algorithms -

    Christian Konrad , title =. Algorithms -. 2015 , crossref =. doi:10.1007/978-3-662-48350-3_70 , timestamp =

    2015 doi

  241. [253]

    Proceedings of the Twenty-Second

    Brian Babcock and Mayur Datar and Rajeev Motwani and Liadan O'Callaghan , title =. Proceedings of the Twenty-Second. 2003 , crossref =. doi:10.1145/773153.773176 , timestamp =

    2003

  242. [254]

    Crouch and Andrew McGregor and Daniel Stubbs , title =

    Michael S. Crouch and Andrew McGregor and Daniel Stubbs , title =. Algorithms -. 2013 , crossref =. doi:10.1007/978-3-642-40450-4_29 , timestamp =

    2013 doi

  243. [255]

    Proceedings of the 35th Annual

    Moses Charikar and Liadan O'Callaghan and Rina Panigrahy , title =. Proceedings of the 35th Annual. 2003 , crossref =. doi:10.1145/780542.780548 , timestamp =

    2003

  244. [256]

    Agarwal and R

    Pankaj K. Agarwal and R. Sharathkumar , title =. Algorithmica , volume =. 2015 , url =. doi:10.1007/s00453-013-9846-4 , timestamp =

    2015 doi

  245. [257]

    Chan and Vinayak Pathak , title =

    Timothy M. Chan and Vinayak Pathak , title =. Comput. Geom. , volume =. 2014 , url =. doi:10.1016/j.comgeo.2013.05.007 , timestamp =

    2014 doi

  246. [258]

    An improved data stream algorithm for clustering , journal =

    Sang. An improved data stream algorithm for clustering , journal =. 2015 , url =. doi:10.1016/j.comgeo.2015.06.003 , timestamp =

    2015 doi

  247. [259]

    Core-Preserving Algorithms , booktitle =

    Hamid Zarrabi. Core-Preserving Algorithms , booktitle =. 2008 , crossref =

    2008

  248. [260]

    The Hardness of Approximation of

    Pranjal Awasthi and Moses Charikar and Ravishankar Krishnaswamy and Ali Kemal Sinop , editor =. The Hardness of Approximation of. 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands , series =. 2015 , url =. doi:10.42...

    2015 doi

  249. [261]

    Vincent Cohen. Tight. 46th International Colloquium on Automata, Languages, and Programming,. 2019 , url =. doi:10.4230/LIPICS.ICALP.2019.42 , timestamp =

    2019 doi

  250. [262]

    An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions , journal =

    Hamid Zarrabi. An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions , journal =. 2011 , url =. doi:10.1007/s00453-010-9392-2 , timestamp =

    2011 doi

  251. [263]

    Approximation, Randomization and Combinatorial Optimization

    Richard Matthew McCutchen and Samir Khuller , title =. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop,. 2008 , crossref =. doi:10.1007/978-3-540-85363-3_14 , timestamp =

    2008 doi

  252. [264]

    Cohen and S

    M. Cohen and S. Elder and C. Musco and C. Musco and M. Persu , title =. CoRR , volume =. 2014 , url =

    2014

  253. [265]

    Kanungo and D

    T. Kanungo and D. M. Mount and N. S. Netanyahu and C. D. Piatko and R. Silverman and A. Y. Wu , title =. IEEE TPAMI , year =

  254. [266]

    Vazirani , title =

    Kamal Jain and Mohammad Mahdian and Evangelos Markakis and Amin Saberi and Vijay V. Vazirani , title =. J. 2003 , url =. doi:10.1145/950620.950621 , timestamp =

    2003

  255. [267]

    Shi Li , title =. Inf. Comput. , volume =. 2013 , url =. doi:10.1016/j.ic.2012.01.007 , timestamp =

    2013 doi

  256. [268]

    Shmoys and

    David B. Shmoys and. Approximation Algorithms for Facility Location Problems (Extended Abstract) , booktitle =. 1997 , url =. doi:10.1145/258533.258600 , timestamp =

    1997

  257. [269]

    2006 , url =

    Mohammad Mahdian and Yinyu Ye and Jiawei Zhang , title =. 2006 , url =. doi:10.1137/S0097539703435716 , timestamp =

    2006 doi

  258. [270]

    Improved Approximation Algorithms for the Uncapacitated Facility Location Problem , journal =

    Fabi. Improved Approximation Algorithms for the Uncapacitated Facility Location Problem , journal =. 2003 , url =. doi:10.1137/S0097539703405754 , timestamp =

    2003 doi

  259. [271]

    2005 , url =

    Moses Charikar and Sudipto Guha , title =. 2005 , url =. doi:10.1137/S0097539701398594 , timestamp =

    2005 doi

  260. [272]

    2010 , url =

    Jaroslaw Byrka and Karen Aardal , title =. 2010 , url =. doi:10.1137/070708901 , timestamp =

    2010 doi

  261. [273]

    and Rao, Satish , title =

    Kolliopoulos, Stavros G. and Rao, Satish , title =. SIAM J. Comput. , issue_date =. 2007 , issn =. doi:10.1137/S0097539702404055 , acmid =

    2007 doi

  262. [274]

    Proceedings of the Fourteenth Annual

    Venkatesan Guruswami and Piotr Indyk , title =. Proceedings of the Fourteenth Annual. 2003 , url =

    2003

  263. [275]

    European journal of operational research , volume=

    A two-phase tabu search approach to the location routing problem , author=. European journal of operational research , volume=. 1999 , publisher=

    1999

  264. [276]

    Neighborhood search heuristics for the uncapacitated facility location problem

    Diptesh Ghosh. Neighborhood search heuristics for the uncapacitated facility location problem. European Journal of Operational Research. 2003. doi:http://dx.doi.org/10.1016/S0377-2217(02)00504-0

    2003 doi

  265. [277]

    The discrete Unconscious search and its application to uncapacitated facility location problem

    Ehsan Ardjmand and Namkyu Park and Gary Weckman and Mohammad Reza Amin-Naseri. The discrete Unconscious search and its application to uncapacitated facility location problem. Computers & Industrial Engineering. 2014. doi:http://dx.doi.org/10.1016/j.cie.2014.04.010

    2014 doi

  266. [278]

    Better Guarantees for k-Means and

    Sara Ahmadian and Ashkan Norouzi. Better Guarantees for k-Means and. 2020 , url =. doi:10.1137/18M1171321 , timestamp =

    2020 doi

  267. [279]

    European journal of operational research , volume=

    Variable neighborhood search: Principles and applications , author=. European journal of operational research , volume=. 2001 , publisher=

    2001

  268. [280]

    Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics , booktitle =

    Vincent Cohen. Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics , booktitle =

  269. [281]

    Salavatipour , title =

    Zachary Friggstad and Mohsen Rezapour and Mohammad R. Salavatipour , title =

  270. [282]

    A two-phase tabu search approach to the location routing problem , journal =

    Dilek T. A two-phase tabu search approach to the location routing problem , journal =

  271. [283]

    European Journal of Operational Research , volume =

    Diptesh Ghosh , title =. European Journal of Operational Research , volume =

  272. [284]

    Weckman and Mohammad Reza Amin

    Ehsan Ardjmand and Namkyu Park and Gary R. Weckman and Mohammad Reza Amin. The discrete Unconscious search and its application to uncapacitated facility location problem , journal =

  273. [285]

    Computers

    Minghe Sun , title =. Computers

  274. [286]

    Mount and Nathan S

    Tapas Kanungo and David M. Mount and Nathan S. Netanyahu and Christine D. Piatko and Ruth Silverman and Angela Y. Wu , title =

  275. [287]

    Gereon Frahling and Christian Sohler , title =. Int. J. Comput. Geometry Appl. , volume =

  276. [288]

    Journal of Computer and system Sciences , volume=

    On the theory of average case complexity , author=. Journal of Computer and system Sciences , volume=. 1992 , publisher=

    1992

  277. [289]

    Neural Networks, 2009

    Hand movement recognition for brazilian sign language: a study using distance-based neural networks , author=. Neural Networks, 2009. IJCNN 2009. International Joint Conference on , pages=. 2009 , organization=

    2009

  278. [290]

    1973 , publisher=

    Pattern classification and scene analysis , author=. 1973 , publisher=

    1973

  279. [291]

    Advances in Neural Information Processing Systems , pages=

    Automatic derivation of statistical algorithms: The EM family and beyond , author=. Advances in Neural Information Processing Systems , pages=

  280. [292]

    Annals of eugenics , volume=

    The use of multiple measurements in taxonomic problems , author=. Annals of eugenics , volume=. 1936 , publisher=

    1936

  281. [293]

    Advances in neural information processing systems , volume=

    Warped gaussian processes , author=. Advances in neural information processing systems , volume=. 2004 , publisher=

    2004

  282. [294]

    UCI Machine Learning Repository

    Moshe Lichman. UCI Machine Learning Repository. 2013

    2013

  283. [295]

    Scikit-learn: Machine Learning in Python , journal =

    Pedregosa, Fabian and Varoquaux, Ga\". Scikit-learn: Machine Learning in Python , journal =. 2011 , issn =

    2011

  284. [296]

    Constant approximation for k-median and k-means with outliers via iterative rounding , booktitle =

    Ravishankar Krishnaswamy and Shi Li and Sai Sandeep , editor =. Constant approximation for k-median and k-means with outliers via iterative rounding , booktitle =. 2018 , url =. doi:10.1145/3188745.3188882 , timestamp =

    2018

  285. [297]

    A constant factor approximation algorithm for

    Ke Chen , editor =. A constant factor approximation algorithm for. Proceedings of the Nineteenth Annual. 2008 , url =

    2008

  286. [298]

    An Improved Local Search Algorithm for k-Median , booktitle =

    Vincent Cohen. An Improved Local Search Algorithm for k-Median , booktitle =. 2022 , url =. doi:10.1137/1.9781611977073.65 , timestamp =

    2022 doi

  287. [299]

    Breaching the 2

    Vincent Cohen. Breaching the 2. Proceedings of the 2023. 2023 , url =

    2023

  288. [300]

    Gowda and Thomas W

    Kishen N. Gowda and Thomas W. Pensyl and Aravind Srinivasan and Khoa Trinh , editor =. Improved Bi-point Rounding Algorithms and a Golden Barrier for. Proceedings of the 2023. 2023 , url =. doi:10.1137/1.9781611977554.CH38 , timestamp =

    2023 doi

Pith tools

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