On the power of random greedy algorithms

DOI10.1016/J.EJC.2022.103551MaRDI QIDQ2145759zbMATHOpenAlexFDO

Authors He Guo, Lutz Warnke

Publication date 20 June 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.07854

zbMATH Keywords

probabilistic methodalgorithmic approach

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: In this paper we solve two problems of Esperet, Kang and Thomasse as well as Li concerning (i) induced bipartite subgraphs in triangle-free graphs and (ii) van der Waerden numbers. Each time random greedy algorithms allow us to go beyond the Lovasz Local Lemma or alteration method used in previous work, illustrating the power of the algorithmic approach to the probabilistic method.

Recommendations

• On the greedy algorithm with random costs
• On randomizing two derandomized greedy algorithms
• Randomized greedy: new variants of some classic approximation algorithms
• On the power of randomization in on-line algorithms
• A note on the random greedy independent set algorithm
• scientific article; zbMATH DE number 1875441
• On the Power of the Randomized Iterate
• On the Power of the Randomized Iterate
• scientific article; zbMATH DE number 3970528
• Some remarks on greedy algorithms

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A lower bound for off-diagonal van der Waerden numbers
• A new proof of Szemerédi's theorem
• A note on Elkin's improvement of Behrend's construction
• A note on the random greedy independent set algorithm
• A subexponential upper bound for van der Waerden numbers \(W(3,k)\)
• Arithmetic progressions in sumsets
• Asymptotic packing via a branching process
• Asymptotically good list-colorings
• Bipartite induced density in triangle-free graphs
• Dense induced bipartite subgraphs in triangle-free graphs
• Differential equations for random processes and random graphs
• Dynamic concentration of the triangle‐free process
• How to make a graph bipartite
• Large girth approximate Steiner triple systems
• On a conjecture of Erdős on locally sparse Steiner triple systems
• On a packing and covering problem
• On the growth of a van der Waerden-like function
• On the missing log in upper tail estimates
• Packing nearly optimal Ramsey \(R(3,t)\) graphs
• Separation choosability and dense bipartite induced subgraphs
• The C_ℓ‐free process
• The Final Size of the $C_{\ell}$-free Process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The early evolution of the \(H\)-free process
• The triangle-free process
• The triangle-free process and the Ramsey number \(R(3,k)\)
• When does the \(K_{4}\)-free process stop?

Cited in

(7)

• Stochastic analysis of greedy algorithms for the subset sum problem
• On randomized sketching algorithms and the Tracy-Widom law
• On the Power of the Randomized Iterate
• On randomizing two derandomized greedy algorithms
• On the random greedy linear uniform hypergraph packing
• Bounds on Ramsey games via alterations
• An almost-greedy search on random binary vectors and random graphs

This page was built for publication: On the power of random greedy algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2145759)