On the power of random greedy algorithms

DOI10.1016/J.EJC.2022.103551zbMATH Open1491.05111OpenAlexW3153696349MaRDI QIDQ2145759FDOQ2145759

Authors: He Guo, Lutz Warnke 

Publication date: 20 June 2022

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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)

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

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)