Campus Event Calendar

Event Entry

New for: D3

What and Who

Approximation Schemes for Dense Variants of Feedback Arc Set, Correlation Clustering, and Other Fragile Min Constraint Satisfaction Problems

Warren Schudy
Brown University
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
AG Audience

Date, Time and Location

Tuesday, 20 April 2010
45 Minutes
E1 4


We study approximation schemes for various minimum (or maximum) constraint satisfaction
problems (CSPs). We give the first polynomial time approximation schemes (PTASs) for the
minimization problems of feedback arc set on tournament graphs, fully dense betweenness, and
correlation clustering with noisy input. We give a PTAS for dense MAX CSPs which is simpler than
previous PTASs for these problems. We give a more time-efficient PTAS for correlation clustering
with a fixed number of clusters. We generalize and unify the above results using a new concept of
fragile constraints.

Bio: Warren Schudy is a PhD candidate at Brown University. The research area that most excites him
is the theoretical foundations of artificial intelligence, including approximation algorithms,
machine learning, and combinatorial optimization.


Rob van Stee
--email hidden
passcode not visible
logged in users only

Christina Fries, 03/24/2010 15:38 -- Created document.