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
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 20 April 2010
13:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
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.
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.
Contact
Rob van Stee
--email hidden
passcode not visible
logged in users only
Christina Fries, 03/24/2010 15:38 -- Created document.