14 citations · 51 across the 29 of their papers we have counts for
4 papers · 1 filter
Improved and Simplified Inapproximability for k-means
Euiwoong Lee, Melanie Schmidt, John Wright
The k-means problem consists of finding k centers in the d-dimensional Euclidean space that minimize the sum of the squared distances of all points in an input set P to their close…
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…
Approximate Hypergraph Coloring under Low-discrepancy and Related Promises
Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee
A hypergraph is said to be -colorable if its vertices can be colored with colors so that no hyperedge is monochromatic. -colorability is a fundamental property (called 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…