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

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.