pith. sign in

arxiv: 2402.13227 · v3 · submitted 2024-02-20 · 💻 cs.DS · math.OC

Online Matching on 3-Uniform Hypergraphs

Sander Borst , Danish Kashaev , Zhuan Khye Koh This is my paper

Pith reviewed 2026-05-24 03:17 UTC · model grok-4.3

classification 💻 cs.DS math.OC
keywords online matchinghypergraphscompetitive ratioprimal-dual algorithmadversarial instancevertex arrival3-uniform
0
0 comments X

The pith

A primal-dual algorithm achieves the optimal competitive ratio of (e-1)/(e+1) for fractional online matching on 3-uniform hypergraphs.

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

The paper determines the best possible competitive ratio for the fractional online matching problem on 3-uniform hypergraphs in the vertex-arrival model. It gives a primal-dual algorithm that reaches (e-1)/(e+1) approximately 0.4621 and proves this bound tight via a new adversarial instance that merges ideas from earlier graph hard cases. A sympathetic reader cares because the classic 1-1/e bound for bipartite graphs does not directly carry over, and hypergraph versions model richer allocation settings such as set packing. The work also supplies an integral algorithm that beats greedy under bounded online degree and recovers the known 1/2 ratio when online degree is at most 2.

Core claim

For online matching on 3-uniform hypergraphs with vertex arrivals, a primal-dual fractional algorithm attains competitive ratio (e-1)/(e+1) and a specially built adversarial instance shows that no higher ratio is possible. The instance blends edge-arrival and vertex-arrival lower-bound constructions from the graph setting. Separately, a simple integral algorithm improves on greedy whenever online vertices have bounded degree; as a corollary it matches the optimal ratio 1/2 on 3-uniform hypergraphs when every online vertex has degree at most 2, since the degree-1 case reduces to the edge-arrival model on ordinary graphs.

What carries the argument

The primal-dual fractional algorithm together with the adversarial instance that combines edge-arrival and vertex-arrival hard instances from graphs.

If this is right

  • The ratio (e-1)/(e+1) is tight for fractional online 3-uniform hypergraph matching.
  • When every online vertex has degree at most 2 the optimal competitive ratio is exactly 1/2.
  • A simple integral algorithm already exceeds the greedy ratio whenever online vertices have bounded degree.
  • The degree-1 special case is equivalent to the edge-arrival model on ordinary graphs, inheriting its 1/2 upper bound.

Where Pith is reading between the lines

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

  • The same combination of arrival-model hard instances may yield tight bounds for k-uniform hypergraphs with k greater than 3.
  • The gap between the fractional ratio (e-1)/(e+1) and the integral ratio 1/2 suggests that integrality gaps remain an open question for higher uniformity.
  • The primal-dual construction could be adapted to weighted versions or to online set packing problems with larger set sizes.

Load-bearing premise

The model is the standard vertex-arrival setting on 3-uniform hypergraphs, where each arriving vertex reveals all its incident edges.

What would settle it

Either an explicit fractional online algorithm whose competitive ratio on every 3-uniform hypergraph instance exceeds (e-1)/(e+1), or a demonstration that the given adversarial instance fails to be valid under the vertex-arrival rule.

Figures

Figures reproduced from arXiv: 2402.13227 by Danish Kashaev, Sander Borst, Zhuan Khye Koh.

Figure 1
Figure 1. Figure 1: An illustration of the region R = {(a, b) ∈ [0, 1]2 : f(a) + f(b) ≤ 1}. The symmetric point at the boundary of the region has both coordinates ln((e + 1)/2) ≈ 0.62. When an online node w arrives, a threshold respecting algorithm ensures that the fractional matching x satisfies (x(δ(u)), x(δ(v))) ∈ R for every hyperedge h = {u, v, w} ∈ δ(w) with xh > 0 at the end of that iteration. 4.3 Constructing the matc… view at source ↗
Figure 2
Figure 2. Figure 2: The partial matchings M(t) i if the fractional algorithm ensures that every edge reaches the threshold at the end of every phase, meaning that f(ℓ (t) u ) + f(ℓ (t) v ) ≥ 1 for every (u, v) ∈ M(t) i . The maximum matching at the end of phase 5 has size five and consists of M(5) i . M(1) i M(2) i M(3) i M(4) i M(5) i [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: In this example, the algorithm does not increase the edge (1 [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Plot of the ℓ(t, i) process for two different values of t if the algorithm exactly matches the threshold at every phase. Observe that, since t is odd, (σt(qt), σt(qt)) ∈ M(t) i with the load of node σt(qt) staying at ln((e + 1)/2) ≈ 0.62. we will thus lower bound the fractional degree of the active nodes σt(i) for i ∈ {1, . . . , ⌈qt⌉}. For this reason, we define: ℓ(t, i) := x (t)  δ(σt(i)) = X e∈δ(σt(i)… view at source ↗
Figure 5
Figure 5. Figure 5: Plot of ψ(t, y) for two different values of t, the horizontal axis represents y ∈ Z/2. where B(t, 1 2 ) is the binomial distribution with parameters t and 1 2 (see [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: An illustration of the instance constructed in Lemma 4.3 [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
read the original abstract

The online matching problem was introduced by Karp, Vazirani and Vazirani (STOC 1990) on bipartite graphs with vertex arrivals. It is well-known that the optimal competitive ratio is $1-1/e$ for both integral and fractional versions of the problem. Since then, there has been considerable effort to find optimal competitive ratios for other related settings. In this work, we go beyond the graph case and study the online matching problem on $k$-uniform hypergraphs. For $k=3$, we provide an optimal primal-dual fractional algorithm, which achieves a competitive ratio of $(e-1)/(e+1)\approx 0.4621$. As our main technical contribution, we present a carefully constructed adversarial instance, which shows that this ratio is in fact optimal. It combines ideas from known hard instances for bipartite graphs under the edge-arrival and vertex-arrival models. For $k\geq 3$, we give a simple integral algorithm which performs better than greedy when the online nodes have bounded degree. As a corollary, it achieves the optimal competitive ratio of 1/2 on 3-uniform hypergraphs when every online node has degree at most 2. This is because the special case where every online node has degree 1 is equivalent to the edge-arrival model on graphs, for which an upper bound of 1/2 is known.

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

2 major / 2 minor

Summary. The paper studies the online matching problem on k-uniform hypergraphs under the vertex-arrival model. For k=3 it presents a primal-dual fractional algorithm achieving competitive ratio (e-1)/(e+1)≈0.4621 and claims optimality via an adversarial instance that combines known hard instances from the edge-arrival and vertex-arrival models on ordinary graphs. For general k≥3 it gives a simple integral algorithm that outperforms greedy when online nodes have bounded degree, and as a corollary obtains the optimal ratio 1/2 on 3-uniform hypergraphs when every online node has degree at most 2 (reducing to the edge-arrival graph case when degree=1).

Significance. If the lower-bound construction is valid, the result supplies the first tight competitive ratio for fractional online matching on 3-uniform hypergraphs, extending the classic 1-1/e graph result. The bounded-degree integral algorithm and its 1/2 corollary are also of independent interest. The work uses standard primal-dual techniques and an explicit adversarial construction rather than fitted parameters.

major comments (2)
  1. [adversarial instance construction] Lower-bound construction (abstract and the section presenting the adversarial instance): the optimality claim rests on an instance obtained by combining the edge-arrival hard instance (ratio 1/2) and vertex-arrival hard instance (ratio 1-1/e) from graphs. The manuscript must explicitly verify that the resulting structure is 3-uniform, that the arrival sequence is a legal vertex-arrival order, and that no extra hyperedges or matching opportunities are created that would allow the primal-dual algorithm to exceed (e-1)/(e+1). Without this verification the lower bound does not yet establish tightness.
  2. [primal-dual algorithm and analysis] Primal-dual analysis (the section deriving the competitive ratio (e-1)/(e+1)): the algorithm is stated to be optimal only after the lower bound is established. If the adversarial instance requires adjustment to remain 3-uniform and vertex-arrival, the analysis of the primal-dual scheme must be re-checked to confirm the ratio remains tight rather than merely an upper bound on the algorithm's performance.
minor comments (2)
  1. [abstract] The abstract states the ratio as (e-1)/(e+1) but does not include the explicit primal-dual LP or the differential-equation formulation used to obtain it; adding a short reference to the relevant equations would improve readability.
  2. [preliminaries] Notation for hyperedges and online/offline vertices should be introduced once and used consistently; a small table or diagram summarizing the arrival model versus the graph models would help readers unfamiliar with the hypergraph setting.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on the lower-bound construction and its implications for the analysis. We address the two major comments point by point below.

read point-by-point responses

  1. Referee: [adversarial instance construction] Lower-bound construction (abstract and the section presenting the adversarial instance): the optimality claim rests on an instance obtained by combining the edge-arrival hard instance (ratio 1/2) and vertex-arrival hard instance (ratio 1-1/e) from graphs. The manuscript must explicitly verify that the resulting structure is 3-uniform, that the arrival sequence is a legal vertex-arrival order, and that no extra hyperedges or matching opportunities are created that would allow the primal-dual algorithm to exceed (e-1)/(e+1). Without this verification the lower bound does not yet establish tightness.

    Authors: We agree that the verification should be stated more explicitly to strengthen the presentation. The construction in the manuscript is already designed so that the two graph instances are embedded on disjoint vertex sets with hyperedges formed only within each part (ensuring exact 3-uniformity and no cross-hyperedges), and the arrival order interleaves the two instances while respecting the vertex-arrival model. In the revised manuscript we will insert a short dedicated paragraph immediately after the instance description that explicitly confirms these three properties and argues that no additional matching opportunities arise. revision: yes

  2. Referee: [primal-dual algorithm and analysis] Primal-dual analysis (the section deriving the competitive ratio (e-1)/(e+1)): the algorithm is stated to be optimal only after the lower bound is established. If the adversarial instance requires adjustment to remain 3-uniform and vertex-arrival, the analysis of the primal-dual scheme must be re-checked to confirm the ratio remains tight rather than merely an upper bound on the algorithm's performance.

    Authors: No structural adjustment to the adversarial instance is required; it already satisfies 3-uniformity and the vertex-arrival constraint by construction. Consequently the existing primal-dual analysis (which upper-bounds the algorithm's performance by (e-1)/(e+1) on every instance) paired with the lower bound on this instance continues to establish tightness. In the revision we will add one clarifying sentence in the analysis section that references the verified properties of the instance, but the mathematical derivation itself remains unchanged. revision: partial

Circularity Check

0 steps flagged

No significant circularity; new algorithm and adversarial construction are independent

full rationale

The paper derives its (e-1)/(e+1) ratio from an explicit primal-dual algorithm and a new adversarial instance constructed by combining prior graph-model ideas into a 3-uniform hypergraph setting. No equation or claim reduces by definition to its own inputs, no fitted parameter is relabeled as a prediction, and no load-bearing step relies on self-citation or an imported uniqueness theorem. The degree-1 corollary simply invokes a known external upper bound of 1/2 rather than a self-referential result. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters or invented entities; the work rests on the standard domain assumption of adversarial vertex arrivals in the online model.

axioms (1)
  • domain assumption The online arrival model is adversarial vertex arrivals on the hypergraph.
    Invoked throughout the problem definition and lower-bound construction in the abstract.

pith-pipeline@v0.9.0 · 5781 in / 1126 out tokens · 67563 ms · 2026-05-24T03:17:22.131368+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

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

  1. Submodular Maximization over Many Matroids via Ordered Local Search

    cs.DS 2026-07 unverdicted novelty 6.0

    A new ordered local search algorithm achieves k/2 + o(k) approximation for monotone submodular maximization over k matroids and (ln 4 k)/3 + o(k) for weighted k-set packing.

Reference graph

Works this paper leans on

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

  1. [1]

    Online vertex-weighted bipartite matching and single-bid budgeted allocations

    Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms , pages 1253–1264. SIAM, 2011

    work page 2011

  2. [2]

    Edge-weighted online windowed matching

    Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, and Chris Sholley. Edge-weighted online windowed matching. Math. Oper. Res., 48(2):999–1016, 2023

    work page 2023

  3. [3]

    On-line bipartite matching made simple

    Benjamin Birnbaum and Claire Mathieu. On-line bipartite matching made simple. Acm Sigact News, 39(1):80–87, 2008

    work page 2008

  4. [4]

    Online primal-dual algorithms for maximizing ad-auctions revenue

    Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms, pages 253–264. Springer, 2007

    work page 2007

  5. [5]

    Online primal-dual algorithms for covering and packing

    Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34(2):270–286, 2009

    work page 2009

  6. [6]

    Online algorithms for maximum cardinality matching with edge arrivals

    Niv Buchbinder, Danny Segev, and Yevgeny Tkach. Online algorithms for maximum cardinality matching with edge arrivals. Algorithmica, 81(5):1781–1799, 2019

    work page 2019

  7. [7]

    On linear and semidefinite programming relaxations for hypergraph matching

    Yuk Hei Chan and Lap Chi Lau. On linear and semidefinite programming relaxations for hypergraph matching. Mathematical programming, 135(1-2):123–148, 2012

    work page 2012

  8. [8]

    Improved approximation for 3-dimensional matching via bounded pathwidth local search

    Marek Cygan. Improved approximation for 3-dimensional matching via bounded pathwidth local search. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 509–518. IEEE Computer Society, 2013. 21

    work page 2013

  9. [9]

    Online matching with concave returns

    Nikhil R Devanur and Kamal Jain. Online matching with concave returns. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages 137–144, 2012

    work page 2012

  10. [10]

    Randomized primal-dual analysis of ranking for online bipartite matching

    Nikhil R Devanur, Kamal Jain, and Robert D Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages 101–107. SIAM, 2013

    work page 2013

  11. [11]

    Analyzing randomized search heuristics: Tools from probability theory

    Benjamin Doerr. Analyzing randomized search heuristics: Tools from probability theory. In Theory of Randomized Search Heuristics: Foundations and Recent Developments , pages 1–20. World Scientific, 2011

    work page 2011

  12. [12]

    An economics-based analysis of ranking for online bipartite matching

    Alon Eden, Michal Feldman, Amos Fiat, and Kineret Segal. An economics-based analysis of ranking for online bipartite matching. In Symposium on Simplicity in Algorithms (SOSA) , pages 107–110. SIAM, 2021

    work page 2021

  13. [13]

    The b-matching problem in hypergraphs: Hardness and approximability

    Mourad El Ouali and Gerold J¨ ager. The b-matching problem in hypergraphs: Hardness and approximability. In International Conference on Combinatorial Optimization and Applications, pages 200–211. Springer, 2012

    work page 2012

  14. [14]

    Edge-weighted online bipartite matching

    Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam. Edge-weighted online bipartite matching. Journal of the ACM , 69(6):1–35, 2022

    work page 2022

  15. [15]

    Online matching with general arrivals

    Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. Online matching with general arrivals. In 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 26–37. IEEE, 2019

    work page 2019

  16. [16]

    Online budgeted matching in random input models with applications to adwords

    Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, volume 8, pages 982–991, 2008

    work page 2008

  17. [17]

    On the complexity of approximating k-set packing

    Elad Hazan, Shmuel Safra, and Oded Schwartz. On the complexity of approximating k-set packing. Computational complexity, 15:20–39, 2006

    work page 2006

  18. [18]

    Fully online matching

    Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. Fully online matching. J. ACM, 67(3):17:1–17:25, 2020

    work page 2020

  19. [19]

    Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals

    Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals. ACM Transactions on Algorithms (TALG), 15(3):1–15, 2019

    work page 2019

  20. [20]

    Fully online matching II: beating ranking and water-filling

    Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Fully online matching II: beating ranking and water-filling. In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1380–1391. IEEE, 2020

    work page 2020

  21. [21]

    Adwords in a panorama

    Zhiyi Huang, Qiankun Zhang, and Yuhao Zhang. Adwords in a panorama. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 1416–1426. IEEE, 2020

    work page 2020

  22. [22]

    An optimal deterministic algorithm for online b-matching

    Bala Kalyanasundaram and Kirk R Pruhs. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1-2):319–325, 2000. 22

    work page 2000

  23. [23]

    Online bipartite matching with unknown distributions

    Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 587–596, 2011

    work page 2011

  24. [24]

    An optimal algorithm for on-line bipartite matching

    Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352–358, 1990

    work page 1990

  25. [25]

    An optimal on- line algorithm for weighted bipartite matching and extensions to combinatorial auctions

    Thomas Kesselheim, Klaus Radke, Andreas T¨ onnis, and Berthold V¨ ocking. An optimal on- line algorithm for weighted bipartite matching and extensions to combinatorial auctions. In European symposium on algorithms, pages 589–600. Springer, 2013

    work page 2013

  26. [26]

    Algorithms for secretary problems on graphs and hypergraphs

    Nitish Korula and Martin P´ al. Algorithms for secretary problems on graphs and hypergraphs. In Automata, Languages and Programming, 36th Internatilonal Colloquium (ICALP), Pro- ceedings, Part II, volume 5556 of Lecture Notes in Computer Science, pages 508–520. Springer, 2009

    work page 2009

  27. [27]

    An approxima- tion algorithm for network revenue management under nonstationary arrivals

    Yuhang Ma, Paat Rusmevichientong, Mika Sumida, and Huseyin Topaloglu. An approxima- tion algorithm for network revenue management under nonstationary arrivals. Oper. Res., 68(3):834–855, 2020

    work page 2020

  28. [28]

    Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps

    Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 597–606, 2011

    work page 2011

  29. [29]

    Soto, and Victor Verdugo

    Javier Marinkovic, Jos´ e A. Soto, and Victor Verdugo. Online combinatorial assignment in independence systems. In Integer Programming and Combinatorial Optimization - 25th In- ternational Conference (IPCO) , volume 14679 of Lecture Notes in Computer Science , pages 294–308. Springer, 2024

    work page 2024

  30. [30]

    Online matching and ad allocation

    Aranyak Mehta. Online matching and ad allocation. Found. Trends Theor. Comput. Sci. , 8(4):265–368, 2013

    work page 2013

  31. [31]

    Adwords and generalized online matching

    Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM) , 54(5):22–es, 2007

    work page 2007

  32. [32]

    Technical note - online hypergraph matching with delays

    Marco Pavone, Amin Saberi, Maximilian Schiffer, and Matt Wu Tsao. Technical note - online hypergraph matching with delays. Oper. Res., 70(4):2194–2212, 2022

    work page 2022

  33. [33]

    Randomized rounding: a technique for provably good algorithms and algorithmic proofs

    Prabhakar Raghavan and Clark D Tompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365–374, 1987

    work page 1987

  34. [34]

    Weighted fractional and integral k-matching in hyper- graphs

    Anand Srivastav and Peter Stangier. Weighted fractional and integral k-matching in hyper- graphs. Discrete applied mathematics, 57(2-3):255–269, 1995

    work page 1995

  35. [35]

    Almost tight bounds for online hypergraph matching

    Thorben Tr¨ obst and Rajan Udwani. Almost tight bounds for online hypergraph matching. Oper. Res. Lett., 55:107143, 2024

    work page 2024

  36. [36]

    Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm

    Yajun Wang and Sam Chiu-wai Wong. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In Automata, Languages, and Programming - 42nd International Colloquium (ICALP), Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 1070–1081. Springer, 2015. 23

    work page 2015

  37. [37]

    Probabilistic computations: Toward a unified measure of complexity

    Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977) , pages 222–227. IEEE Computer Society, 1977. A Proof of Lemma 4.3 Proof. Let us fix a fractional algorithm A and let us fix a matching M = (V, E) of size n, meaning that |E| = n. The adversarial ...

    work page 1977

  38. [38]

    E(w1) = E

    The first online node w1 connects to every edge of the matching, i.e. E(w1) = E. The algorithm A now assigns fractional value x(e) to every edge e ∈ E, and we denote by e1 ∈ E the edge with the lowest fractional value x(e1). Observe that x(e1) ≤ 1/n

    work page

  39. [39]

    The algorithm A can thus increase the fractional values x(e) for every e ∈ E(w2)

    The second online node w2 connects to E(w2) = E \ {e1}. The algorithm A can thus increase the fractional values x(e) for every e ∈ E(w2). We then denote by e2 the edge in E(w2) with the lowest fractional value after this iteration, and it is easy to check that x(e1) + x(e2) ≤ 2/n + 1/(n − 1)

    work page

  40. [40]

    , n}, the online node wk connects to n − k + 1 edges E(wk) = E \ {e1,

    More generally, for every k ∈ { 1, . . . , n}, the online node wk connects to n − k + 1 edges E(wk) = E \ {e1, . . . , ek−1}, and ek is defined as the edge having the lowest fractional value at the end of the iteration of wk. We thus get a bound of ℓX k=1 x(ek) ≤ ℓX k=1 kX i=1 1 n − i + 1 ∀ℓ ∈ {1, . . . , n}. (12) The inner sum in (12) reaches ∆ approxima...

    work page

  41. [41]

    For any pair of algorithms A, A′, we have H1(A) = H1(A′)

    work page

  42. [42]

    Note that the set of strong automorphisms forms a group

    For any pair of algorithms A, A′ and indices i, j ≥ 1, we have V (Hi(A)) = V (Hj(A′)). Note that the set of strong automorphisms forms a group. Definition B.3. Let Σ be a subgroup of permutations of V such that H(A) is Σ-symmetric for every Σ-symmetric algorithm A. For an algorithm A on H, let the Σ- symmetrized algorithm symΣ(A) be the algorithm which se...

    work page