research
∙
09/08/2023
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs
We consider the question of approximating Max 2-CSP where each variable ...
share
research
∙
08/18/2023
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs
A μ-constrained Boolean Max-CSP(ψ) instance is a Boolean Max-CSP instanc...
research
∙
11/08/2022
A Local Search-Based Approach for Set Covering
In the Set Cover problem, we are given a set system with each set having...
research
∙
08/29/2022
Fitting Metrics and Ultrametrics with Minimum Disagreements
Given x ∈ (ℝ_≥ 0)^[n]2 recording pairwise distances, the METRIC VIOLATIO...
research
∙
07/22/2022
Correlation Clustering with Sherali-Adams
Given a complete graph G = (V, E) where each edge is labeled + or -, the...
research
∙
07/11/2022
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
The Uncapacitated Facility Location (UFL) problem is one of the most fun...
research
∙
03/03/2022
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
We study several questions related to diversifying search results. We gi...
research
∙
01/12/2022
A Characterization of Approximability for Biased CSPs
A μ-biased Max-CSP instance with predicate ψ:{0,1}^r →{0,1} is an instan...
research
∙
12/03/2021
Strong Hardness of Approximation for Tree Transversals
Let H be a fixed graph. The H-Transversal problem, given a graph G, asks...
research
∙
12/03/2021
On Some Variants of Euclidean K-Supplier
The k-Supplier problem is an important location problem that has been ac...
research
∙
11/21/2021
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics
K-median and k-means are the two most popular objectives for clustering ...
research
∙
11/17/2021
Matroid-Based TSP Rounding for Half-Integral Solutions
We show how to round any half-integral solution to the subtour-eliminati...
research
∙
05/03/2021
A Constant-factor Approximation for Weighted Bond Cover
The Weighted ℱ-Vertex Deletion for a class F of graphs asks, weighted gr...
research
∙
10/04/2020
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering
We present hardness of approximation results for Correlation Clustering ...
research
∙
09/30/2020
On Approximability of Clustering Problems Without Candidate Centers
The k-means objective is arguably the most widely-used cost function for...
research
∙
09/02/2020
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
For a family of graphs ℱ, Weighted ℱ-Deletion is the problem for which t...
research
∙
06/08/2020
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Parameterization and approximation are two popular ways of coping with N...
research
∙
05/17/2020
Optimal Bounds for the k-cut Problem
In the k-cut problem, we want to find the smallest set of edges whose de...
research
∙
12/15/2019
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Hierarchical Clustering is an unsupervised data analysis method which ha...
research
∙
11/20/2019
The Karger-Stein Algorithm is Optimal for k-cut
In the k-cut problem, we are given an edge-weighted graph and want to fi...
research
∙
06/02/2019
The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
Given an edge-weighted graph, how many minimum k-cuts can it have? This ...
research
∙
04/28/2019
Tight FPT Approximations for k-Median and k-Means
We investigate the fine-grained complexity of approximating the classica...
research
∙
07/21/2018
Faster Exact and Approximate Algorithms for k-Cut
In the k-cut problem, we are given an edge-weighted graph G and an integ...
research
∙
07/16/2018
A PTAS for ℓ_p-Low Rank Approximation
A number of recent works have studied algorithms for entrywise ℓ_p-low r...
research
∙
06/25/2018
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities
Online contention resolution schemes (OCRSs) were proposed by Feldman, S...
research
∙
04/10/2018
Approximating Operator Norms via Generalized Krivine Rounding
We consider the (ℓ_p,ℓ_r)-Grothendieck problem, which seeks to maximize ...
research
∙
04/04/2018
Losing Treewidth by Separating Subsets
We study the problem of deleting the smallest set S of vertices (resp.ed...
research
∙
02/21/2018
Inapproximability of Matrix p→ q Norms
We study the problem of computing the p→ q norm of a matrix A ∈ R^m × n,...
research
∙
02/12/2018
DiSLR: Distributed Sampling with Limited Redundancy For Triangle Counting in Graph Streams
Given a web-scale graph that grows over time, how should its edges be st...
research
∙
05/20/2017