Seminars
View all Seminars | Download ICal for this eventRound-or-Cut Technique for designing Approximation Algorithms for Clustering Problems
Series: Bangalore Theory Seminars
Speaker: Deeparnab Chakrabarty Dartmouth
Date/Time: Jul 03 11:30:00
Location: CSA Seminar Hall (Room No. 254, First Floor)
Abstract:
Many clustering problems are NP-hard and therefore extensive research has gone into designing approximation algorithms for these problems. Indeed, many techniques in approximation algorithms have been honed in the study of many of these fundamental problems. In this talk, I will talk about a technique called the ??round-or-cut technique? (also called the ??cutting plane technique? in integer programming parlance) which is probably not as well-known as many other techniques in approximation algorithms. In the last five years, however, this technique has led to tractable approximation algorithms for many clustering problems. I would like to present this general technique and illustrate it on one such clustering problem.
This talk plans to be self-contained and no assumption of rounding or cutting will be assumed.
Microsoft Teams link:
Link
We are grateful to the Kirani family for generously supporting the theory seminar series
Hosts: Rachana Gusain, Rahul Madhavan, Rameesh Paul, KVN Sreenivas