Source author record

Euiwoong Lee

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Computational Geometry Computer Science and Game Theory Databases Discrete Mathematics Distributed, Parallel, and Cluster Computing Information Theory Machine Learning math.CO math.IT Social and Information Networks

Catalog footprint

Research overview

16works

12topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Characterization of Approximability for Biased CSPs

A $μ$ -biased Max-CSP instance with predicate $ψ:\{0,1\}^r \to \{0,1\}$ is an instance of Constraint Satisfaction Problem (CSP) where the objective is to find a labeling of relative weight at most $μ$ which satisfies the maximum fraction of constraints. Biased CSPs are versatile and express several well studied problems such as Densest- $k$ -Sub(Hyper)graph and SmallSetExpansion. In this work, we explore the role played by the bias parameter $μ$ on the approximability of biased CSPs. We show that the approximability of such CSPs can be characterized (up to loss of factors of arity $r$ ) using the bias-approximation curve of Densest- $k$ -SubHypergraph (DkSH). In particular, this gives a tight characterization of predicates which admit approximation guarantees that are independent of the bias parameter $μ$ . Motivated by the above, we give new approximation and hardness results for DkSH. In particular, assuming the Small Set Expansion Hypothesis (SSEH), we show that DkSH with arity $r$ and $k = μn$ is NP-hard to approximate to a factor of $Ω(r^3μ^{r-1}\log(1/μ))$ for every $r \geq 2$ and $μ< 2^{-r}$ . We also give a $O(μ^{r-1}\log(1/μ))$ -approximation algorithm for the same setting. Our upper and lower bounds are tight up to constant factors, when the arity $r$ is a constant, and in particular, imply the first tight approximation bounds for the Densest- $k$ -Subgraph problem in the linear bias regime. Furthermore, using the above characterization, our results also imply matching algorithms and hardness for every biased CSP of constant arity.

preprint2022arXiv

Fitting Metrics and Ultrametrics with Minimum Disagreements

Given $x \in (\mathbb{R}_{\geq 0})^{\binom{[n]}{2}}$ recording pairwise distances, the METRIC VIOLATION DISTANCE (MVD) problem asks to compute the $\ell_0$ distance between $x$ and the metric cone; i.e., modify the minimum number of entries of $x$ to make it a metric. Due to its large number of applications in various data analysis and optimization tasks, this problem has been actively studied recently. We present an $O(\log n)$ -approximation algorithm for MVD, exponentially improving the previous best approximation ratio of $O(OPT^{1/3})$ of Fan et al. [ SODA, 2018]. Furthermore, a major strength of our algorithm is its simplicity and running time. We also study the related problem of ULTRAMETRIC VIOLATION DISTANCE (UMVD), where the goal is to compute the $\ell_0$ distance to the cone of ultrametrics, and achieve a constant factor approximation algorithm. The UMVD can be regarded as an extension of the problem of fitting ultrametrics studied by Ailon and Charikar [SIAM J. Computing, 2011] and by Cohen-Addad et al. [FOCS, 2021] from $\ell_1$ norm to $\ell_0$ norm. We show that this problem can be favorably interpreted as an instance of Correlation Clustering with an additional hierarchical structure, which we solve using a new $O(1)$ -approximation algorithm for correlation clustering that has the structural property that it outputs a refinement of the optimum clusters. An algorithm satisfying such a property can be considered of independent interest. We also provide an $O(\log n \log \log n)$ approximation algorithm for weighted instances. Finally, we investigate the complementary version of these problems where one aims at choosing a maximum number of entries of $x$ forming an (ultra-)metric. In stark contrast with the minimization versions, we prove that these maximization versions are hard to approximate within any constant factor assuming the Unique Games Conjecture.

preprint2022arXiv

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems

We study several questions related to diversifying search results. We give improved approximation algorithms in each of the following problems, together with some lower bounds. - We give a polynomial-time approximation scheme (PTAS) for a diversified search ranking problem [Bansal et al., ICALP 2010] whose objective is to minimizes the discounted cumulative gain. Our PTAS runs in time $n^{2^{O(\log(1/ε)/ε)}} \cdot m^{O(1)}$ where $n$ denotes the number of elements in the databases. Complementing this, we show that no PTAS can run in time $f(ε) \cdot (nm)^{2^{o(1/ε)}}$ assuming Gap-ETH; therefore our running time is nearly tight. Both of our bounds answer open questions of Bansal et al. - We next consider the Max-Sum Dispersion problem, whose objective is to select $k$ out of $n$ elements that maximizes the dispersion, which is defined as the sum of the pairwise distances under a given metric. We give a quasipolynomial-time approximation scheme for the problem which runs in time $n^{O_ε(\log n)}$ . This improves upon previously known polynomial-time algorithms with approximate ratios 0.5 [Hassin et al., Oper. Res. Lett. 1997; Borodin et al., ACM Trans. Algorithms 2017]. Furthermore, we observe that known reductions rule out approximation schemes that run in $n^{\tilde{o}_ε(\log n)}$ time assuming ETH. - We consider a generalization of Max-Sum Dispersion called Max-Sum Diversification. In addition to the sum of pairwise distance, the objective includes another function $f$ . For monotone submodular $f$ , we give a quasipolynomial-time algorithm with approximation ratio arbitrarily close to $(1 - 1/e)$ . This improves upon the best polynomial-time algorithm which has approximation ratio $0.5$ by Borodin et al. Furthermore, the $(1 - 1/e)$ factor is tight as achieving better-than- $(1 - 1/e)$ approximation is NP-hard [Feige, J. ACM 1998].

preprint2021arXiv

A PTAS for $\ell_p$ -Low Rank Approximation

A number of recent works have studied algorithms for entrywise $\ell_p$ -low rank approximation, namely, algorithms which given an $n \times d$ matrix $A$ (with $n \geq d$ ), output a rank- $k$ matrix $B$ minimizing $\|A-B\|_p^p=\sum_{i,j}|A_{i,j}-B_{i,j}|^p$ when $p > 0$ ; and $\|A-B\|_0=\sum_{i,j}[A_{i,j}\neq B_{i,j}]$ for $p=0$ . On the algorithmic side, for $p \in (0,2)$ , we give the first $(1+ε)$ -approximation algorithm running in time $n^{\text{poly}(k/ε)}$ . Further, for $p = 0$ , we give the first almost-linear time approximation scheme for what we call the Generalized Binary $\ell_0$ -Rank- $k$ problem. Our algorithm computes $(1+ε)$ -approximation in time $(1/ε)^{2^{O(k)}/ε^{2}} \cdot nd^{1+o(1)}$ . On the hardness of approximation side, for $p \in (1,2)$ , assuming the Small Set Expansion Hypothesis and the Exponential Time Hypothesis (ETH), we show that there exists $δ:= δ(α) > 0$ such that the entrywise $\ell_p$ -Rank- $k$ problem has no $α$ -approximation algorithm running in time $2^{k^δ}$ .

preprint2021arXiv

CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams

Given a graph stream, how can we estimate the number of triangles in it using multiple machines with limited storage? Specifically, how should edges be processed and sampled across the machines for rapid and accurate estimation? The count of triangles (i.e., cliques of size three) has proven useful in numerous applications, including anomaly detection, community detection, and link recommendation. For triangle counting in large and dynamic graphs, recent work has focused largely on streaming algorithms and distributed algorithms but little on their combinations for "the best of both worlds". In this work, we propose CoCoS, a fast and accurate distributed streaming algorithm for estimating the counts of global triangles (i.e., all triangles) and local triangles incident to each node. Making one pass over the input stream, COCOS carefully processes and stores the edges across multiple machines so that the redundant use of computational and storage resources is minimized. Compared to baselines, CoCoS is (a) Accurate: giving up to 39X smaller estimation error, (b) Fast: up to 10.4X faster, scaling linearly with the size of the input stream, and (c) Theoretically sound: yielding unbiased estimates.

preprint2020arXiv

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

preprint2020arXiv

LP-branching algorithms based on biased graphs

We give a combinatorial condition for the existence of efficient, LP-based FPT algorithms for a broad class of graph-theoretical optimisation problems. Our condition is based on the notion of biased graphs known from matroid theory. Specifically, we show that given a biased graph $Ψ=(G,\mathcal{B})$ , where $\mathcal{B}$ is a class of balanced cycles in $G$ , the problem of finding a set $X$ of at most $k$ vertices in $G$ which intersects every unbalanced cycle in $G$ admits an FPT algorithm using an LP-branching approach, similar to those previously seen for VCSP problems (Wahlström, SODA 2014). This framework captures many of the problems previously solved via the VCSP approach to LP-branching, as well as new generalisations, such as Group Feedback Vertex Set for infinite groups (e.g., for graphs whose edges are labelled by matrices). A major advantage compared to previous work is that it is immediate to check the applicability of the result for a given problem, whereas testing applicability of the VCSP approach for a specific VCSP requires determining the existence of an embedding language with certain algebraically defined properties, which is not known to be decidable in general. Additionally, we study the approximation question, and show that every problem of this category admits an $O(\log \text{OPT})$ -approximation.

preprint2020arXiv

Towards constant-factor approximation for chordal / distance-hereditary vertex deletion

For a family of graphs $\mathcal{F}$ , Weighted $\mathcal{F}$ -Deletion is the problem for which the input is a vertex weighted graph $G=(V,E)$ and the goal is to delete $S\subseteq V$ with minimum weight such that $G\setminus S\in\mathcal{F}$ . Designing a constant-factor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3-leaf power graphs, and interval graphs are known to admit constant-factor approximation algorithms, but the question is open for chordal graphs and distance-hereditary graphs. In this paper, we add one more class to this list by presenting a constant-factor approximation algorithm when $F$ is the intersection of chordal graphs and distance-hereditary graphs. They are known as ptolemaic graphs and form a superset of both block graphs and 3-leaf power graphs above. Our proof presents new properties and algorithmic results on inter-clique digraphs as well as an approximation algorithm for a variant of Feedback Vertex Set that exploits this relationship (named Feedback Vertex Set with Precedence Constraints), each of which may be of independent interest.

preprint2016arXiv

Improved Hardness for Cut, Interdiction, and Firefighter Problems

We study variants of the classic $s$ - $t$ cut problem and prove the following improved hardness results assuming the Unique Games Conjecture (UGC). - For any constant $k \geq 2$ and $ε> 0$ , we show that Directed Multicut with $k$ source-sink pairs is hard to approximate within a factor $k - ε$ . This matches the trivial $k$ -approximation algorithm. By a simple reduction, our result for $k = 2$ implies that Directed Multiway Cut with two terminals (also known as $s$ - $t$ Bicut) is hard to approximate within a factor $2 - ε$ , matching the trivial $2$ -approximation algorithm. Previously, the best hardness factor for these problems (for constant $k$ ) was $1.5 - ε$ under the UGC. - For Length-Bounded Cut and Shortest Path Interdiction, we show that both problems are hard to approximate within any constant factor, even if we allow bicriteria approximation. If we want to cut vertices or the graph is directed, our hardness factor for Length-Bounded Cut matches the best approximation ratio up to a constant. Previously, the best hardness factor was $1.1377$ for Length-Bounded Cut and $2$ for Shortest Path Interdiction. - Assuming a variant of the UGC (implied by another variant of Bansal and Khot), we prove that it is hard to approximate Resource Minimization Fire Containment within any constant factor. Previously, the best hardness factor was $2$ . Our results are based on a general method of converting an integrality gap instance to a length-control dictatorship test for variants of the $s$ - $t$ cut problem, which may be useful for other problems.

preprint2016arXiv

Partitioning a Graph into Small Pieces with Applications to Path Transversal

Given a graph $G = (V, E)$ and an integer $k$ , we study $k$ -Vertex Seperator (resp. $k$ -Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) such that each connected component in the resulting graph has at most $k$ vertices. Our primary focus is on the case where $k$ is either a constant or a slowly growing function of $n$ (e.g. $O(\log n)$ or $n^{o(1)}$ ). Our problems can be interpreted as a special case of three general classes of problems that have been studied separately (balanced graph partitioning, Hypergraph Vertex Cover (HVC), and fixed parameter tractability (FPT)). Our main result is an $O(\log k)$ -approximation algorithm for $k$ -Vertex Seperator that runs in time $2^{O(k)} n^{O(1)}$ , and an $O(\log k)$ -approximation algorithm for $k$ -Edge Separator that runs in time $n^{O(1)}$ . Our result on $k$ -Edge Seperator improves the best previous graph partitioning algorithm for small $k$ . Our result on $k$ -Vertex Seperator improves the simple $(k+1)$ -approximation from HVC. When $OPT > k$ , the running time $2^{O(k)} n^{O(1)}$ is faster than the lower bound $k^{Ω(OPT)} n^{Ω(1)}$ for exact algorithms assuming the Exponential Time Hypothesis. While the running time of $2^{O(k)} n^{O(1)}$ for $k$ -Vertex Separator seems unsatisfactory, we show that the superpolynomial dependence on $k$ may be needed to achieve a polylogarithmic approximation ratio, based on hardness of Densest $k$ -Subgraph. We also study $k$ -Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length $k$ . With additional ideas from FPT algorithms and graph theory, we present an $O(\log k)$ -approximation algorithm for $k$ -Path Transversal that runs in time $2^{O(k^3 \log k)} n^{O(1)}$ . Previously, the existence of even $(1 - δ)k$ -approximation algorithm for fixed $δ> 0$ was open.

preprint2015arXiv

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises

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 Property B) of hypergraphs and is extensively studied in combinatorics. Algorithmically, however, given a $2$ -colorable $k$ -uniform hypergraph, it is NP-hard to find a $2$ -coloring miscoloring fewer than a fraction $2^{-k+1}$ of hyperedges (which is achieved by a random $2$ -coloring), and the best algorithms to color the hypergraph properly require $\approx n^{1-1/k}$ colors, approaching the trivial bound of $n$ as $k$ increases. In this work, we study the complexity of approximate hypergraph coloring, for both the maximization (finding a $2$ -coloring with fewest miscolored edges) and minimization (finding a proper coloring using fewest number of colors) versions, when the input hypergraph is promised to have the following stronger properties than $2$ -colorability: (A) Low-discrepancy: If the hypergraph has discrepancy $\ell \ll \sqrt{k}$ , we give an algorithm to color the it with $\approx n^{O(\ell^2/k)}$ colors. However, for the maximization version, we prove NP-hardness of finding a $2$ -coloring miscoloring a smaller than $2^{-O(k)}$ (resp. $k^{-O(k)}$ ) fraction of the hyperedges when $\ell = O(\log k)$ (resp. $\ell=2$ ). Assuming the UGC, we improve the latter hardness factor to $2^{-O(k)}$ for almost discrepancy- $1$ hypergraphs. (B) Rainbow colorability: If the hypergraph has a $(k-\ell)$ -coloring such that each hyperedge is polychromatic with all these colors, we give a $2$ -coloring algorithm that miscolors at most $k^{-Ω(k)}$ of the hyperedges when $\ell \ll \sqrt{k}$ , and complement this with a matching UG hardness result showing that when $\ell =\sqrt{k}$ , it is hard to even beat the $2^{-k+1}$ bound achieved by a random coloring.

preprint2015arXiv

APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items

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 problem admits a constant factor approximation. We complement their result by showing that this problem is APX-hard.

preprint2015arXiv

Improved and Simplified Inapproximability for k-means

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 closest respective center. Awasthi et. al. recently showed that there exists a constant c > 1 such that it is NP-hard to approximate the k-means objective within a factor of c. We establish that the constant c is at least 1.0013.

preprint2015arXiv

Inapproximability of $H$ -Transversal/Packing

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 to find the smallest $S \subseteq V_G$ such that the subgraph induced by $V_G \setminus S$ does not have $H$ as a subgraph, and the latter asks to find the maximum number of pairwise disjoint $k$ -subsets $S_1, ..., S_m \subseteq V_G$ such that the subgraph induced by each $S_i$ has $H$ as a subgraph. We prove that if $H$ is 2-connected, $H$ -Transversal and $H$ -Packing are almost as hard to approximate as general $k$ -Hypergraph Vertex Cover and $k$ -Set Packing, so it is NP-hard to approximate them within a factor of $Ω(k)$ and $\widetilde Ω(k)$ respectively. We also show that there is a 1-connected $H$ where $H$ -Transversal admits an $O(\log k)$ -approximation algorithm, so that the connectivity requirement cannot be relaxed from 2 to 1. For a special case of $H$ -Transversal where $H$ is a (family of) cycles, we mention the implication of our result to the related Feedback Vertex Set problem, and give a different hardness proof for directed graphs.

preprint2014arXiv

Hardness of Graph Pricing through Generalized Max-Dicut

The Graph Pricing problem is among the fundamental problems whose approximability is not well-understood. While there is a simple combinatorial 1/4-approximation algorithm, the best hardness result remains at 1/2 assuming the Unique Games Conjecture (UGC). We show that it is NP-hard to approximate within a factor better than 1/4 under the UGC, so that the simple combinatorial algorithm might be the best possible. We also prove that for any $ε> 0$ , there exists $δ> 0$ such that the integrality gap of $n^δ$ -rounds of the Sherali-Adams hierarchy of linear programming for Graph Pricing is at most 1/2 + $ε$ . This work is based on the effort to view the Graph Pricing problem as a Constraint Satisfaction Problem (CSP) simpler than the standard and complicated formulation. We propose the problem called Generalized Max-Dicut( $T$ ), which has a domain size $T + 1$ for every $T \geq 1$ . Generalized Max-Dicut(1) is well-known Max-Dicut. There is an approximation-preserving reduction from Generalized Max-Dicut on directed acyclic graphs (DAGs) to Graph Pricing, and both our results are achieved through this reduction. Besides its connection to Graph Pricing, the hardness of Generalized Max-Dicut is interesting in its own right since in most arity two CSPs studied in the literature, SDP-based algorithms perform better than LP-based or combinatorial algorithms --- for this arity two CSP, a simple combinatorial algorithm does the best.

preprint2014arXiv

LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes

Random (dv,dc)-regular LDPC codes are well-known to achieve the Shannon capacity of the binary symmetric channel (for sufficiently large dv and dc) under exponential time decoding. However, polynomial time algorithms are only known to correct a much smaller fraction of errors. One of the most powerful polynomial-time algorithms with a formal analysis is the LP decoding algorithm of Feldman et al. which is known to correct an Omega(1/dc) fraction of errors. In this work, we show that fairly powerful extensions of LP decoding, based on the Sherali-Adams and Lasserre hierarchies, fail to correct much more errors than the basic LP-decoder. In particular, we show that: 1) For any values of dv and dc, a linear number of rounds of the Sherali-Adams LP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv,dc)-regular LDPC code. 2) For any value of dv and infinitely many values of dc, a linear number of rounds of the Lasserre SDP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv,dc)-regular LDPC code. Our proofs use a new stretching and collapsing technique that allows us to leverage recent progress in the study of the limitations of LP/SDP hierarchies for Maximum Constraint Satisfaction Problems (Max-CSPs). The problem then reduces to the construction of special balanced pairwise independent distributions for Sherali-Adams and special cosets of balanced pairwise independent subgroups for Lasserre. Some of our techniques are more generally applicable to a large class of Boolean CSPs called Min-Ones. In particular, for k-Hypergraph Vertex Cover, we obtain an improved integrality gap of $k-1-ε$ that holds after a \emph{linear} number of rounds of the Lasserre hierarchy, for any k = q+1 with q an arbitrary prime power. The best previous gap for a linear number of rounds was equal to $2-ε$ and due to Schoenebeck.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Euiwoong Lee

Research overview

Is this your work?

16 publications

A Characterization of Approximability for Biased CSPs

Fitting Metrics and Ultrametrics with Minimum Disagreements

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems

A PTAS for $\ell_p$ -Low Rank Approximation

CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

LP-branching algorithms based on biased graphs

Towards constant-factor approximation for chordal / distance-hereditary vertex deletion

Improved Hardness for Cut, Interdiction, and Firefighter Problems

Partitioning a Graph into Small Pieces with Applications to Path Transversal

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises

APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items

Improved and Simplified Inapproximability for k-means

Inapproximability of $H$ -Transversal/Packing

Hardness of Graph Pricing through Generalized Max-Dicut

LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes

See the researcher in context

Building this map preview

Euiwoong Lee

Research overview

Is this your work?

16 publications

A Characterization of Approximability for Biased CSPs

Fitting Metrics and Ultrametrics with Minimum Disagreements

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems

A PTAS for ℓp\ell_pℓp​-Low Rank Approximation

CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

LP-branching algorithms based on biased graphs

Towards constant-factor approximation for chordal / distance-hereditary vertex deletion

Improved Hardness for Cut, Interdiction, and Firefighter Problems

Partitioning a Graph into Small Pieces with Applications to Path Transversal

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises

APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items

Improved and Simplified Inapproximability for k-means

Inapproximability of HHH-Transversal/Packing

Hardness of Graph Pricing through Generalized Max-Dicut

LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes

See the researcher in context

Building this map preview

A PTAS for $\ell_p$ -Low Rank Approximation

Inapproximability of $H$ -Transversal/Packing