Schedule
August 5 update: Due to a time-zone mix-up, a previous version of the schedule had the incorrect times listed for CET. The program should start at 8am PDT and 5pm CET, and the pdf at the link below should reflect this. We are very sorry for the confusion!
How to attend?
APPROX/RANDOM will be held on VirtualChair. See https://www.virtualchair.net/events/approx-random-2021 for information for how to join the conference. See https://www.virtualchair.net/guide for a guide from virtual chair about how to use the platform.
Social Event
Will be held on Tuesday 8/17. See details here.
Discussions
There is time after each session set aside for “Discussion.” During this time, the presenters of the previous session will be hanging out in our GatherTown venue to answer questions. Please visit them there after the talks to continue the discussion!
Pre-Recorded Talks
The authors will give short live talks during the talk sessions. Longer pre-recorded talks will be available, both from the GatherTown venue and also posted online. You can find links to all of the talks here.
Invited Talks
Jelani Nelson (UC Berkeley)
Title: A survey on random projections
Abstract: The Johnson-Lindenstrauss lemma popularized the so-called
“random projection method” almost 40 years ago, showing that random
linear embeddings into low dimension multiplicatively preserve
Euclidean distances for finite point sets. We survey some recent
advances related to this method and also state some open problems.
Vera Traub (ETH Zurich)
Title: Better-Than-2 Approximations for Weighted Tree Augmentation
Abstract: The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edge-connectivity of a given graph from 1 to 2 in the cheapest possible way by adding some additional edges from a given set. There are many standard techniques that lead to a 2-approximation for WTAP, but despite much progress on special cases, the factor 2 remained unbeaten for several decades.
In this talk we present two algorithms for WTAP that improve on the longstanding approximation ratio of 2. The first algorithm is a relative greedy algorithm, which starts with a simple, though weak, solution and iteratively replaces parts of this starting solution by stronger components. This algorithm achieves an approximation ratio of (1 + ln 2 + epsilon) < 1.7. Second, we present a local search algorithm that achieves an approximation ratio of 1.5 + epsilon (for any constant epsilon > 0).
This is joint work with Rico Zenklusen.
RANDOM: THE CONFERENCE 