pith. sign in

arxiv: 2606.17991 · v1 · pith:VBKZVLX2new · submitted 2026-06-16 · 💻 cs.CG

Greedy Vector Balancing

Wojciech Czerwi\'nski , Daniel Dadush , Ekin Ergen , Arka Ghosh , S{\l}awomir Lasota , {\L}ukasz Orlikowski This is my paper

Pith reviewed 2026-06-26 21:48 UTC · model grok-4.3

classification 💻 cs.CG
keywords vector balancinggreedy algorithmonline discrepancyconvex absorbing setssubspace chainsscheduling application
0
0 comments X

The pith

The greedy algorithm for online vector balancing keeps Euclidean prefix-sum norms at most (2/δ_T)^{d-1} for any finite set T of unit vectors in R^d.

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

The paper proves that the greedy algorithm for online vector balancing achieves a performance bound independent of the number of input vectors when those vectors come from a finite set. Specifically, for unit vectors in d-dimensional space, the maximum Euclidean norm of any signed prefix sum is at most (2/δ_T)^{d-1}, where δ_T is the minimum nonzero distance between a vector and the subspaces spanned by other vectors in the set. This result follows from the construction of a T-absorbing convex body that remains bounded and contains all the greedy partial sums. The bound also applies to scaled versions of the vectors and extends to an online partitioning problem, yielding a polynomial-time algorithm for a fixed-scenario scheduling task.

Core claim

When T ⊂ R^d is finite and consists of unit vectors, the greedy algorithm—which at each step picks the sign so that the new vector has non-positive inner product with the current sum—ensures that every prefix sum has Euclidean norm at most (2/δ_T)^{d-1}. This holds because there exists a bounded convex set K_T that is T-absorbing: whenever a point x in K_T has non-positive inner product with a vector t from ±T, then x + t remains in K_T. The set K_T is constructed explicitly using chains of subspaces spanned by vectors from T and is contained in a ball of the stated radius.

What carries the argument

The T-absorbing convex body K_T, defined so that for x in K_T and t in ±T, if the inner product is non-positive then x + t stays in K_T; built from subspace chains to lie inside a ball of radius (2/δ_T)^{d-1}.

If this is right

  • The same bound holds when every vector in the sequence is a positive scalar multiple of some vector from T.
  • The greedy method extends to online partitioning of the sequence into p subsequences while preserving an analogous n-independent guarantee.
  • A lexicographic version of total completion time scheduling under a fixed number of scenarios is polynomial-time solvable.
  • There exist sets T for which Ω(√d / δ_T) is a matching lower bound on the worst-case norm produced by greedy.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The explicit subspace-chain construction of the absorbing body supplies a potential-function template that could be reused for other online linear-decision problems.
  • When the input set is known in advance, the bound gives a concrete guarantee even against adversarial arrival order without solving an offline optimization.
  • If δ_T shrinks only polynomially with d the exponential dependence on d limits practical use to well-separated vector collections.
  • The result cleanly separates the finite-support case from the general infinite-T regime where n-dependent growth may still be required.

Load-bearing premise

T must be finite with δ_T positive, so the subspace-chain construction of the absorbing body stays bounded rather than extending indefinitely in degenerate directions.

What would settle it

A finite T with δ_T > 0 together with an explicit sequence from T on which greedy produces some prefix sum whose Euclidean norm exceeds (2/δ_T)^{d-1}.

read the original abstract

In online vector balancing, vectors $t_1,\dots,t_n$ arrive one by one from a given set $T$ and the goal is to assign signs $s_1,\dots,s_n\in\{\pm1\}$ in an online manner so as to minimize the largest norm of any signed prefix sum $\sum_{i=1}^ks_i t_i$, $k \in [n]$. In this paper, we analyze the natural Euclidean greedy vector balancing algorithm for this problem: at each step $k$, the sign $s_k\in\{\pm1\}$ is chosen so that $s_k t_k$ has non-positive inner product with $\sum_{i=1}^{k-1} s_i\cdot t_i$. Our main result is the first finite bound, independent of the sequence length $n$, on the performance of greedy whenever $T$ is finite. When $T \subset \mathbb{R}^d$ consists of unit vectors, we prove that the signed sums produced by greedy have Euclidean norm at most $(2/\delta_T)^{d-1}$, where $\delta_T$ is the minimum non-zero distance between vectors in $T$ and subspaces spanned by vectors in $T$. The same upper bound holds when the sequences are composed of scaled down vectors in $T$. We also provide a simple set $T$ for which $\Omega(\sqrt{d}/\delta_T)$ is a lower bound. We analyze the greedy algorithm by proving the existence of a bounded convex $K_T$ that is $T$-absorbing: $\forall x\in K_T$ and $t \in\pm T$, $\langle x,t\rangle\leq0\Rightarrow x+t\in K_T$. We give an explicit construction of a set $K_T$ contained in a ball of radius $(2/\delta_T)^{d-1}$, based on chains of subspaces spanned by vectors in $T$, which may be of independent interest. We generalize our greedy vector balancing bound to online vector partitioning, where the sequence $t_1,\dots,t_n$ must be partitioned in an online manner into $p$ subsequences. As an application, we prove a special case of a conjecture of Bosman et al. (arxiv:2402.19259), showing that a lexicographic version of total completion time scheduling under scenarios is polynomial time solvable when the number of scenarios is fixed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript analyzes the Euclidean greedy algorithm for the online vector balancing problem where vectors arrive from a finite set T ⊂ R^d of unit vectors. It proves that signed prefix sums have Euclidean norm at most (2/δ_T)^{d-1}, with δ_T the minimum non-zero distance from any vector in T to a subspace spanned by other vectors in T. The proof proceeds by explicitly constructing a bounded T-absorbing convex body K_T contained in a ball of the stated radius, using chains of subspaces spanned by subsets of T; the absorbing property ensures all greedy prefix sums remain inside K_T independently of n. The same bound holds for scaled vectors from T. A matching Ω(√d / δ_T) lower bound example is given for some T, the result is extended to online vector partitioning into p parts, and an application shows a special case of the Bosman et al. conjecture on lexicographic total completion time scheduling is polynomial-time solvable for fixed number of scenarios.

Significance. If the construction is correct, the result is significant: it supplies the first n-independent guarantee for the natural greedy algorithm in this online discrepancy setting when T is finite, resolving an open question about whether greedy can diverge. The explicit geometric construction of K_T via finite subspace chains is a clean, parameter-free approach that may be reusable in other discrepancy or online-algorithm contexts. The lower-bound example and the scheduling application (a partial resolution of an existing conjecture) strengthen the contribution.

minor comments (3)
  1. [Abstract] Abstract and §1: the precise definition of δ_T (including the metric used for distance to a subspace and the exact quantification over all proper subspaces) should be stated formally before the main theorem, as the exponent d-1 depends directly on it.
  2. The lower-bound construction (mentioned after the main theorem) would benefit from an explicit small example in low dimension (e.g., d=2 or d=3) showing how the Ω(√d / δ_T) dependence is realized.
  3. Notation: the paper introduces K_T as a T-absorbing body but does not always distinguish between the specific constructed body and any absorbing body; a short remark clarifying that the radius bound applies to the explicit construction would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and for recommending minor revision. The referee's summary accurately reflects the manuscript's contributions, including the bound on the greedy algorithm, the geometric construction of K_T, the lower bound, the extension to partitioning, and the scheduling application. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation relies on an explicit, self-contained geometric construction of the T-absorbing convex body K_T from chains of subspaces spanned by the finite set T. The radius bound (2/δ_T)^{d-1} is obtained directly from the maximum chain length d and the definition of δ_T as the minimum positive distance to subspaces; no parameters are fitted, no equations are defined in terms of their own outputs, and no load-bearing self-citations are invoked for the core bound. The absorbing property then implies the greedy invariant without circular reduction. This is a standard first-principles proof whose central claim has independent mathematical content.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the existence of a bounded T-absorbing convex body K_T constructed from chains of subspaces spanned by T; δ_T is taken as given from the input set and is not a fitted parameter. No new physical entities are postulated.

axioms (2)
  • domain assumption Existence of a bounded convex T-absorbing set K_T whose radius is controlled by subspace chains
    Invoked in the proof sketch to obtain the n-independent bound; location: main result paragraph.
  • standard math Standard facts about convex bodies and inner-product sign conditions in Euclidean space
    Used to define the absorbing property; no section citation given in abstract.
invented entities (1)
  • K_T (T-absorbing convex body) no independent evidence
    purpose: Witness set that remains bounded under the greedy sign rule
    Constructed explicitly from subspace chains; independent_evidence false because no external verification is supplied in the abstract.

pith-pipeline@v0.9.1-grok · 6001 in / 1528 out tokens · 18661 ms · 2026-06-26T21:48:29.121278+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

166 extracted references · 57 canonical work pages

  1. [1]

    Discrete balancing games , author=. Bull. Inst. Math. Acad. Sinica , volume=

  2. [2]

    Journal of Combinatorial Theory, Series B , volume=

    Balancing games , author=. Journal of Combinatorial Theory, Series B , volume=. 1977 , publisher=

    1977

  3. [3]

    Journal of Combinatorial Theory, Series A , volume=

    On a class of balancing games , author=. Journal of Combinatorial Theory, Series A , volume=. 1979 , publisher=

    1979

  4. [4]

    Combinatorica , volume=

    Balancing vectors in the max norm , author=. Combinatorica , volume=. 1986 , publisher=

    1986

  5. [5]

    Journal of Combinatorial Theory, Series A , volume=

    Vector balancing games with aging , author=. Journal of Combinatorial Theory, Series A , volume=. 2001 , publisher=

    2001

  6. [6]

    arXiv preprint arXiv:2512.03273 , year=

    Balancing games on unbounded sets , author=. arXiv preprint arXiv:2512.03273 , year=

    arXiv

  7. [7]

    Discrete Analysis , volume=

    Balancing sums of random vectors , author=. Discrete Analysis , volume=. 2018 , publisher=

    2018

  8. [8]

    Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Online vector balancing and geometric discrepancy , author=. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

  9. [9]

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

    Online discrepancy minimization for stochastic arrivals , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

    2021

  10. [10]

    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Discrepancy minimization via a self-balancing walk , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

  11. [11]

    13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , volume=

    A Gaussian Fixed Point Random Walk , author=. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , volume=. 2022 , organization=

    2022

  12. [12]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    Optimal online discrepancy minimization , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

  13. [13]

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

    Quasi-Monte Carlo Beyond Hardy-Krause , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    2025

  14. [14]

    Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , volume=

    A deterministic-control-based approach motion by curvature , author=. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , volume=. 2006 , publisher=

    2006

  15. [15]

    Proceedings of the 2018 ACM Conference on Economics and Computation , pages=

    How to make envy vanish over time , author=. Proceedings of the 2018 ACM Conference on Economics and Computation , pages=

    2018

  16. [16]

    Advances in Neural Information Processing Systems , volume=

    Grab: Finding provably better data permutations than random reshuffling , author=. Advances in Neural Information Processing Systems , volume=

  17. [17]

    Journal of Machine Learning Research , volume=

    Kernel thinning , author=. Journal of Machine Learning Research , volume=

  18. [18]

    Theory of Computing Systems , volume=

    Total completion time scheduling under scenarios , author=. Theory of Computing Systems , volume=. 2025 , publisher=

    2025

  19. [19]

    1997 , issn =

    Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs , journal =. 1997 , issn =. doi:https://doi.org/10.1006/jcta.1997.2780 , url =

    work page doi:10.1006/jcta.1997.2780 1997

  20. [20]

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

    On sub-determinants and the diameter of polyhedra , author=. Proceedings of the twenty-eighth annual symposium on Computational geometry , pages=

  21. [21]

    International Colloquium on Automata, Languages, and Programming , pages=

    Finding short paths on polytopes by the shadow vertex algorithm , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2013 , organization=

    2013

  22. [22]

    arXiv preprint arXiv:1412.5381 , year=

    Solving totally unimodular LPs with the shadow vertex algorithm , author=. arXiv preprint arXiv:1412.5381 , year=

    Pith/arXiv arXiv

  23. [23]

    Discrete & Computational Geometry , volume=

    On the shadow simplex method for curved polyhedra , author=. Discrete & Computational Geometry , volume=. 2016 , publisher=

    2016

  24. [24]

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

    On finding exact solutions of linear programs in the oracle model , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

    2022

  25. [25]

    Surveys in combinatorics , pages=

    Circuit imbalance measures and linear programming , author=. Surveys in combinatorics , pages=

  26. [26]

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

    Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

    2026

  27. [27]

    Approximate solution of some problems of scheduling theory , JOURNAL =

    Sevast. Approximate solution of some problems of scheduling theory , JOURNAL =. 1978 , PAGES =

    1978

  28. [28]

    and Fiala, T

    Beck, J. and Fiala, T. , Date-Added =. Integer-making theorems , Volume =. Discrete Applied Mathematics , Number =

  29. [29]

    Linear Algebra and its Applications , volume=

    On some combinatorial questions in finite-dimensional spaces , author=. Linear Algebra and its Applications , volume=. 1981 , publisher=

    1981

  30. [30]

    Six standard deviations suffice , Volume =

    Joel Spencer , Date-Added =. Six standard deviations suffice , Volume =. Trans. Amer. Math. Soc. , Pages =

  31. [31]

    Discrepancy of set-systems and matrices , Volume =

    Lov. Discrepancy of set-systems and matrices , Volume =. European Journal of Combinatorics , Number =

  32. [32]

    Mathematics of the USSR-Sbornik , volume=

    Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces , author=. Mathematics of the USSR-Sbornik , volume=. 1989 , publisher=

    1989

  33. [33]

    Studia Math

    Banaszczyk, Wojciech , TITLE =. Studia Math. , FJOURNAL =. 1993 , NUMBER =

    1993

  34. [34]

    Probability in

    Chobanyan, Sergej , TITLE =. Probability in. 1994 , MRCLASS =

    1994

  35. [35]

    The Discrepancy Method , Year =

    Bernard Chazelle , Date-Added =. The Discrepancy Method , Year =

  36. [36]

    Beck, J. and S. Discrepancy theory , Year =. Handbook of combinatorics (vol. 2) , Date-Added =

  37. [37]

    Studia Mathematica , volume=

    On some vector balancing problems , author=. Studia Mathematica , volume=. 1997 , publisher=

    1997

  38. [38]

    , Date-Added =

    Banaszczyk, W. , Date-Added =. Balancing vectors and Gaussian measures of n-dimensional convex bodies , Volume =. Random Structures & Algorithms , Number =

  39. [39]

    Geometric Discrepancy (An Illustrated Guide) , Year =

    Ji. Geometric Discrepancy (An Illustrated Guide) , Year =

  40. [40]

    Linear algebra and its applications , volume=

    Balanced partitions of vector sequences , author=. Linear algebra and its applications , volume=. 2006 , publisher=

    2006

  41. [41]

    Building Bridges: Between Mathematics and Computer Science , pages=

    On the power of linear dependencies , author=. Building Bridges: Between Mathematics and Computer Science , pages=. 2008 , publisher=

    2008

  42. [42]

    Constructive algorithms for discrepancy minimization , Year =

    Bansal, Nikhil , Booktitle =. Constructive algorithms for discrepancy minimization , Year =

  43. [43]

    Newman, Alantha and Neiman, Ofer and Nikolov, Aleksandar , TITLE =. 2012. 2012 , MRCLASS =

    2012

  44. [44]

    and Meka, R

    Lovett, S. and Meka, R. , Date-Added =. Arxiv preprint arXiv:1203.5747 , Title =

    Pith/arXiv arXiv

  45. [45]

    Proceedings of the American Mathematical Society , volume=

    The determinant bound for discrepancy is almost tight , author=. Proceedings of the American Mathematical Society , volume=

  46. [46]

    Algorithmica , volume =

    Nikhil Bansal and Joel Spencer , title =. Algorithmica , volume =. 2013 , pages =

    2013

  47. [47]

    Random Structures Algorithms , FJOURNAL =

    Banaszczyk, Wojciech , TITLE =. Random Structures Algorithms , FJOURNAL =. 2012 , NUMBER =. doi:10.1002/rsa.20373 , URL =

    work page doi:10.1002/rsa.20373 2012

  48. [48]

    Constructive Discrepancy Minimization for Convex Sets , booktitle =

    Thomas Rothvo. Constructive Discrepancy Minimization for Convex Sets , booktitle =. 2014 , url =. doi:10.1109/FOCS.2014.23 , timestamp =

    work page doi:10.1109/focs.2014.23 2014

  49. [49]

    Proceedings of the 20th International Workshop on Randomization and Computation ---

    Dadush, Daniel and Garg, Shashwat and Lovett, Shachar and Nikolov, Aleksandar , TITLE =. Proceedings of the 20th International Workshop on Randomization and Computation ---. 2016 , MRCLASS =

    2016

  50. [50]

    An algorithm for

    Bansal, Nikhil and Dadush, Daniel and Garg, Shashwat , booktitle=. An algorithm for. 2016 , organization=

    2016

  51. [51]

    SIAM Journal on Computing , volume=

    Constructive discrepancy minimization for convex sets , author=. SIAM Journal on Computing , volume=. 2017 , publisher=

    2017

  52. [52]

    Random Structures & Algorithms , volume=

    Efficient algorithms for discrepancy minimization in convex sets , author=. Random Structures & Algorithms , volume=. 2018 , publisher=

    2018

  53. [53]

    Theory OF Computing , volume=

    The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues , author=. Theory OF Computing , volume=

  54. [54]

    Journal of the American Statistical Association , volume=

    Balancing covariates in randomized experiments with the gram--schmidt walk design , author=. Journal of the American Statistical Association , volume=. 2024 , publisher=

    2024

  55. [55]

    arXiv preprint arXiv:2508.03961 , year=

    Decoupling via Affine Spectral-Independence: Beck-Fiala and Koml 'os Bounds Beyond Banaszczyk , author=. arXiv preprint arXiv:2508.03961 , year=

    arXiv

  56. [56]

    SODA , pages =

    Moses Charikar and Alantha Newman and Aleksandar Nikolov , title =. SODA , pages =

  57. [57]

    , Date-Added =

    Guruswami, V. , Date-Added =. Inapproximability results for set splitting and satisfiability problems with no mixed clauses , Year =. Approximation Algorithms for Combinatorial Optimization , Pages =

  58. [58]

    CoRR , Title =

    Karthekeyan Chandrasekaran and Santosh Vempala , Bibsource =. CoRR , Title =

  59. [59]

    The entropy rounding method in approximation algorithms , Url =

    Rothvo , Thomas , Booktitle =. The entropy rounding method in approximation algorithms , Url =. 2012 , Bdsk-Url-1 =

    2012

  60. [60]

    Bin Packing via Discrepancy of Permutations , journal =

    Friedrich Eisenbrand and D. Bin Packing via Discrepancy of Permutations , journal =. 2013 , volume =. doi:10.1145/2483699.2483704 , timestamp =

    work page doi:10.1145/2483699.2483704 2013

  61. [61]

    2014 , volume =

    Kasper Green Larsen , title =. 2014 , volume =. doi:10.1137/120865240 , timestamp =

    work page doi:10.1137/120865240 2014

  62. [62]

    Approximating Bin Packing within O(log

    Thomas Rothvo. Approximating Bin Packing within O(log. 54th Annual. 2013 , pages =. doi:10.1109/FOCS.2013.11 , timestamp =

    work page doi:10.1109/focs.2013.11 2013

  63. [63]

    Conference on Learning Theory , pages=

    Near-optimal herding , author=. Conference on Learning Theory , pages=. 2014 , organization=

    2014

  64. [64]

    Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach , Year =

    Nikhil Bansal and Moses Charikar and Ravishankar Krishnaswamy and Shi Li , Bibsource =. Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach , Year =. SODA , Date-Added =

  65. [65]

    IPCO , pages =

    Nikhil Bansal and Viswanath Nagarajan , title =. IPCO , pages =

  66. [66]

    SIAM Journal on Computing , volume=

    Better bin packing approximations via discrepancy theory , author=. SIAM Journal on Computing , volume=. 2016 , publisher=

    2016

  67. [67]

    Proceedings of the

    Hoberg, Rebecca and Rothvoss, Thomas , TITLE =. Proceedings of the. 2017 , MRCLASS =. doi:10.1137/1.9781611974782.172 , URL =

    work page doi:10.1137/1.9781611974782.172 2017

  68. [68]

    ACM Transactions on Algorithms (TALG) , volume=

    Proximity results and faster algorithms for integer programming using the Steinitz lemma , author=. ACM Transactions on Algorithms (TALG) , volume=. 2019 , publisher=

    2019

  69. [69]

    Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Linear size sparsifier and the geometry of the operator norm ball , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    2020

  70. [70]

    Mathematics of Operations Research , volume=

    On integer programming, discrepancy, and convolution , author=. Mathematics of Operations Research , volume=. 2023 , publisher=

    2023

  71. [71]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Flow time scheduling and prefix beck-fiala , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  72. [72]

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

    Linear-sized sparsifiers via near-linear time discrepancy theory , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  73. [73]

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

    Eulerian Graph Sparsification by Effective Resistance Decomposition , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    2025

  74. [74]

    Geometric Algorithms and Combinatorial Optimization , publisher =

    Gr. Geometric Algorithms and Combinatorial Optimization , publisher =

  75. [75]

    and Lvov, A

    Chazelle, B. and Lvov, A. The discrepancy of boxes in higher dimension. Discrete Comput. Geom. 2001

    2001

  76. [76]

    The ellipsoid method and its consequences in combinatorial optimization , JOURNAL =

    Gr. The ellipsoid method and its consequences in combinatorial optimization , JOURNAL =. 1981 , NUMBER =. doi:10.1007/BF02579273 , URL =

    work page doi:10.1007/bf02579273 1981

  77. [77]

    Approximation algorithms and semidefinite programming , PUBLISHER =

    G. Approximation algorithms and semidefinite programming , PUBLISHER =. 2012 , PAGES =. doi:10.1007/978-3-642-22015-9 , URL =

    work page doi:10.1007/978-3-642-22015-9 2012

  78. [78]

    2004 , PAGES =

    Boyd, Stephen and Vandenberghe, Lieven , TITLE =. 2004 , PAGES =. doi:10.1017/CBO9780511804441 , URL =

    work page doi:10.1017/cbo9780511804441 2004

  79. [79]

    Per Austrin and Venkatesan Guruswami and Johan H. (2+ ) -. 2013 , booktitle=

    2013

  80. [80]

    Seymour, P. D. , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1980 , NUMBER =. doi:10.1016/0095-8956(80)90075-1 , URL =

    work page doi:10.1016/0095-8956(80)90075-1 1980

Showing first 80 references.