
A Constantfactor Approximation for Weighted Bond Cover
The Weighted ℱVertex Deletion for a class F of graphs asks, weighted gr...
read it

Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering
We present hardness of approximation results for Correlation Clustering ...
read it

On Approximability of Clustering Problems Without Candidate Centers
The kmeans objective is arguably the most widelyused cost function for...
read it

Towards constantfactor approximation for chordal / distancehereditary vertex deletion
For a family of graphs ℱ, Weighted ℱDeletion is the problem for which t...
read it

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Parameterization and approximation are two popular ways of coping with N...
read it

Optimal Bounds for the kcut Problem
In the kcut problem, we want to find the smallest set of edges whose de...
read it

Bisect and Conquer: Hierarchical Clustering via MaxUncut Bisection
Hierarchical Clustering is an unsupervised data analysis method which ha...
read it

The KargerStein Algorithm is Optimal for kcut
In the kcut problem, we are given an edgeweighted graph and want to fi...
read it

The Number of Minimum kCuts: Improving the KargerStein Bound
Given an edgeweighted graph, how many minimum kcuts can it have? This ...
read it

Tight FPT Approximations for kMedian and kMeans
We investigate the finegrained complexity of approximating the classica...
read it

Faster Exact and Approximate Algorithms for kCut
In the kcut problem, we are given an edgeweighted graph G and an integ...
read it

A PTAS for ℓ_pLow Rank Approximation
A number of recent works have studied algorithms for entrywise ℓ_plow r...
read it

Optimal Online Contention Resolution Schemes via ExAnte Prophet Inequalities
Online contention resolution schemes (OCRSs) were proposed by Feldman, S...
read it

Approximating Operator Norms via Generalized Krivine Rounding
We consider the (ℓ_p,ℓ_r)Grothendieck problem, which seeks to maximize ...
read it

Losing Treewidth by Separating Subsets
We study the problem of deleting the smallest set S of vertices (resp.ed...
read it

Inapproximability of Matrix p→ q Norms
We study the problem of computing the p→ q norm of a matrix A ∈ R^m × n,...
read it

DiSLR: Distributed Sampling with Limited Redundancy For Triangle Counting in Graph Streams
Given a webscale graph that grows over time, how should its edges be st...
read it

Why You Should Charge Your Friends for Borrowing Your Stuff
We consider goods that can be shared with khop neighbors (i.e., the set...
read it
Euiwoong Lee
is this you? claim profile