Euiwoong Lee

most citedAn FPT Algorithm Beating 2-Approximation for

k

-Cut

2 citations · 2 across the 3 of their papers we have counts for

collaborators

6 papers

cs.DS2017★ 2 cited

An FPT Algorithm Beating 2-Approximation for $k$ -Cut

Anupam Gupta, Euiwoong Lee, Jason Li

In the $k$ -Cut problem, we are given an edge-weighted graph $G$ and an integer $k$ , and have to remove a set of edges with minimum total weight so that $G$ has at least $k$ connect…

cs.DS2017

Understanding the Correlation Gap for Matchings

Guru Guruganesh, Euiwoong Lee

Given a set of vertices $V$ with $∣ V ∣ = n$ , a weight vector $w \in (R^{+} \cup {0})^{(2 V)}$ , and a probability vector $x \in [0, 1]^{(2 V)}$ in the matchi…

cs.AI2017

Why You Should Charge Your Friends for Borrowing Your Stuff

Kijung Shin, Euiwoong Lee, Dhivya Eswaran +1

We consider goods that can be shared with k-hop neighbors (i.e., the set of nodes within k hops from an owner) on a social network. We examine incentives to buy such a good by devi…

cs.CC2015

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…

cs.DS2015

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. $2$ -colorability is a fundamental property (called Pr…

cs.CC2015

Inapproximability of $H$ -Transversal/Packing

Venkatesan Guruswami, Euiwoong Lee

Given an undirected graph $G = (V_{G}, E_{G})$ and a fixed "pattern" graph $H = (V_{H}, E_{H})$ with $k$ vertices, we consider the $H$ -Transversal and $H$ -Packing problems. The former asks…

An FPT Algorithm Beating 2-Approximation for k-Cut