Seminars
View all Seminars | Download ICal for this eventFPT-Approximation via Random Walks
Series: Bangalore Theory Seminars
Speaker: Madhumita Kundu, University of Bergen
Date/Time: Mar 16 16:00:00
Location: Online Talk-teams link follows
Abstract:
We present a simple viewpoint for designing time??ratio trade-offs for classical fixed-parameter tractable (FPT) optimization problems. At the heart of this approach is a randomized version of a natural -exact branching- algorithm, where each branch is explored with a carefully tuned probability. The approximation guarantee and its corresponding success probability of the resulting randomized branching algorithm can be analyzed by modeling the behavior as a random walk on a suitably defined state space. We illustrate the approach on Vertex Cover, using both the standard branching framework and a surrogate given by the Vertex Cover LP relaxation, and show how the random-walk interpretation leads to tunable success probabilities and corresponding running-time/approximation guarantees.
Microsoft Teams link:
Link
We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series
Hosts: Rameesh Paul, Debajyoti Kar, KVN Sreenivas, Nirjhar Das, Rahul Madhavan