4 citations · 6 across the 8 of their papers we have counts for
4 papers · 1 filter
On Approximability of Clustering Problems Without Candidate Centers
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
The k-means objective is arguably the most widely-used cost function for modeling clustering tasks in a metric space. In practice and historically, k-means is thought of in a conti…
Inapproximability of Matrix Norms
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2
We study the problem of computing the norm of a matrix , defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac…
APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items
Euiwoong Lee
We study the problem of allocating a set of indivisible items to agents with additive utilities to maximize the Nash social welfare. Cole and Gkatzelis recently proved that this pr…
Inapproximability of -Transversal/Packing
Venkatesan Guruswami, Euiwoong Lee
Given an undirected graph and a fixed "pattern" graph with vertices, we consider the -Transversal and -Packing problems. The former asks…