Ioana-Oriana Bercea

Instance-Specific Approximation Ratios for Correlation Clustering and Max-Cut

For many NP-hard optimization problems, strong theoretical inapproximability results exist. However, in practice, heuristics regularly outperform these pessimistic worst-case results on real-world datasets. Assessing the quality of these algorithms' outputs is often difficult since we lack good lowe…