EL
Euiwoong Lee
cs.DScs.CCcs.LGcs.CGcs.GTcs.SImath.COcs.AIcs.DBcs.DC
On Valency
published · living versionsW_6g6f433w·v1 · currentpublished
Local Important Separators with Applications to Unbreakable Decomposition and Multicut
with Aditya Anand, Yaowei Long, Thatchaphol Saranurak
1 version
W_khaw5tnq·v1published
Preprints & journals
65 papers in the corpus · 2014–2026An Improved Greedy Approximation for (Metric) -Means2605.29165v1 · Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao et al.2026 · 2 citationsarXiv
Combinatorial Optimization using Comparison Oracles2511.15142v2 · Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta et al.2025 · 0 citationsarXiv
1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP2507.15417v1 · Dahoon Lee, Chenglin Fan, Euiwoong Lee2025 · 0 citationsarXiv
Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering2505.21939v2 · Chenglin Fan, Dahoon Lee, Euiwoong Lee2025 · 1 citationarXiv
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs2504.20027v1 · Aditya Anand, Euiwoong Lee, Jason Li et al.2025 · 0 citationsarXiv
Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT2504.19051v1 · Aditya Anand, Euiwoong Lee, Davide Mazzali et al.2025 · 0 citationsarXiv
Static to Dynamic Correlation Clustering2504.12060v3 · Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee et al.2025 · 0 citationsarXiv
Solving the Correlation Cluster LP in Sublinear Time2503.20883v5 · Nairen Cao, Vincent Cohen-Addad, Shi Li et al.2025 · 1 citationarXiv
A -Approximation Algorithm for Metric -Median2503.10972v2 · Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee et al.2025 · 0 citationsarXiv
Facility Location on High-dimensional Euclidean Spaces2501.18105v1 · Euiwoong Lee, Kijun Shin2025 · 0 citationsarXiv
On Approximability of Min-Sum Clustering2412.03332v2 · Karthik C. S., Euiwoong Lee, Yuval Rabani et al.2024 · 0 citationsarXiv
Min-CSPs on Complete Instances2410.19066v1 · Aditya Anand, Euiwoong Lee, Amatya Sharma2024 · 0 citationsarXiv
Asymptotically Optimal Hardness for -Set Packing and -Matroid Intersection2409.17831v1 · Euiwoong Lee, Ola Svensson, Theophile Thiery2024 · 0 citationsarXiv
Clustering with Non-adaptive Subset Queries2409.10908v3 · Hadley Black, Euiwoong Lee, Arya Mazumdar et al.2024 · 0 citationsarXiv
Unbreakable Decomposition in Close-to-Linear Time2408.09368v1 · Aditya Anand, Euiwoong Lee, Jason Li et al.2024 · 1 citationarXiv
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP2407.08917v1 · Karthik C. S., Euiwoong Lee, Pasin Manurangsi2024 · 2 citationsarXiv
Understanding the Cluster LP for Correlation Clustering2404.17509v3 · Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee et al.2024 · 10 citationsarXiv
Approximating Small Sparse Cuts2403.08983v1 · Aditya Anand, Euiwoong Lee, Jason Li et al.2024 · 3 citationsarXiv
Max-Cut with -Accurate Predictions2402.18263v1 · Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta et al.2024 · 0 citationsarXiv
A PTAS for -Low Rank Approximation: Solving Dense CSPs over Reals2311.00892v1 · Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal et al.2023 · 0 citationsarXiv
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering2309.17243v1 · Vincent Cohen-Addad, Euiwoong Lee, Shi Li et al.2023 · 8 citationsarXiv
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs2309.04099v1 · Euiwoong Lee, Pasin Manurangsi2023 · 1 citationarXiv
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs2308.09667v1 · Suprovat Ghoshal, Euiwoong Lee2023 · 1 citationarXiv
A Local Search-Based Approach for Set Covering2211.04444v1 · Anupam Gupta, Euiwoong Lee, Jason Li2022 · 6 citationsarXiv
Fitting Metrics and Ultrametrics with Minimum Disagreements2208.13920v1 · Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee et al.2022 · 3 citationsarXiv
Correlation Clustering with Sherali-Adams2207.10889v2 · Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman2022 · 17 citationsarXiv
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median2207.05150v2 · Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee et al.2022 · 19 citationsarXiv
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems2203.01857v1 · Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee et al.2022 · 1 citationarXiv
A Characterization of Approximability for Biased CSPs2201.04617v1 · Suprovat Ghoshal, Euiwoong Lee2022 · 5 citationsarXiv
On Some Variants of Euclidean K-Supplier2112.01700v1 · Euiwoong Lee, Viswanath Nagarajan, Lily Wang2021 · 4 citationsarXiv
Strong Hardness of Approximation for Tree Transversals2112.01710v1 · Euiwoong Lee, Pengxiang Wang2021 · 0 citationsarXiv
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics2111.10912v1 · Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee2021 · 1 citationarXiv
Matroid-Based TSP Rounding for Half-Integral Solutions2111.09290v2 · Anupam Gupta, Euiwoong Lee, Jason Li et al.2021 · 6 citationsarXiv
A Constant-factor Approximation for Weighted Bond Cover2105.00857v2 · Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos2021 · 0 citationsarXiv
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering2010.01459v1 · Vaggos Chatziafratis, Neha Gupta, Euiwoong Lee2020 · 5 citationsarXiv
On Approximability of Clustering Problems Without Candidate Centers2010.00087v2 · Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee2020 · 26 citationsarXiv
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion2009.00809v1 · Jungho Ahn, Eun Jung Kim, Euiwoong Lee2020 · 3 citationsarXiv
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms2006.04411v1 · Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee et al.2020 · 0 citationsarXiv
Optimal Bounds for the -cut Problem2005.08301v3 · Anupam Gupta, David G. Harris, Euiwoong Lee et al.2020 · 8 citationsJournal of the ACM 69(1), Article #2 (2022)
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection1912.06983v1 · Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto et al.2019 · 14 citationsarXiv
The Karger-Stein Algorithm is Optimal for -cut1911.09165v1 · Anupam Gupta, Euiwoong Lee, Jason Li2019 · 13 citationsarXiv
The Number of Minimum -Cuts: Improving the Karger-Stein Bound1906.00417v1 · Anupam Gupta, Euiwoong Lee, Jason Li2019 · 11 citationsarXiv
Tight FPT Approximations for -Median and -Means1904.12334v1 · Vincent Cohen-Addad, Anupam Gupta, Amit Kumar et al.2019 · 32 citationsarXiv
Faster Exact and Approximate Algorithms for -Cut1807.08144v2 · Anupam Gupta, Euiwoong Lee, Jason Li2018 · 41 citationsarXiv
A PTAS for -Low Rank Approximation1807.06101v3 · Frank Ban, Vijay Bhattiprolu, Karl Bringmann et al.2018 · 0 citationsarXiv
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities1806.09251v1 · Euiwoong Lee, Sahil Singla2018 · 36 citationsarXiv
Approximating Operator Norms via Generalized Krivine Rounding1804.03644v2 · Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami et al.2018 · 3 citationsarXiv
Losing Treewidth by Separating Subsets1804.01366v2 · Anupam Gupta, Euiwoong Lee, Jason Li et al.2018 · 24 citationsarXiv
Inapproximability of Matrix Norms1802.07425v2 · Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami et al.2018 · 2 citationsarXiv
CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams1802.04249v5 · Kijung Shin, Euiwoong Lee, Jinoh Oh et al.2018 · 13 citationsarXiv
Career total: 115 works. 65 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.