From the 1 of 6 linked papers with an AI index.
7 papers
Sharp Analysis of Gaussian Rounding for Boolean Max k-CSP
Yury Makarychev
In this note, we show that the approximation algorithm for Boolean Max -CSP presented in [Makarychev and Makarychev 2014] yields a approximation, as conjecture…
Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP
Suprovat Ghoshal, Neng Huang, Euiwoong Lee +2
The paper presents improved approximation algorithms for Boolean MAX 2-CSP problems on instances where each variable participates in at most d constraints, achieving a ̅Ω(1/d^4) im…
On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
Suprovat Ghoshal, Neng Huang, Euiwoong Lee +2
Max-Cut is a classical graph-partitioning problem where given a graph , the objective is to find a cut which maximizes the number of edges crossing the cut. In…
Hardness of Approximation for Shortest Path with Vector Costs
Charlie Carlson, Yury Makarychev, Ron Mosenzon
We obtain hardness of approximation results for the -Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer $p \in [2,\i…
Max-Cut with Multiple Cardinality Constraints
Yury Makarychev, Madhusudhan Reddy Pittu, Ali Vakilian
We study the classic Max-Cut problem under multiple cardinality constraints, which we refer to as the Constrained Max-Cut problem. Given a graph , a partition of the vert…
A Polynomial-Time Approximation for Pairwise Fair -Median Clustering
Sayan Bandyapadhyay, Eden ChlamtáÄ, Zachary Friggstad +3
In this work, we study pairwise fair clustering with groups, where for every cluster and every group , the number of points in from group mus…