Euiwoong Lee

ORCID

Publication Activity (10 Years)

Years Active: 2013-2024
Publications (10 Years): 114

Top Venues

CoRR

SODA

Electron. Colloquium Comput. Complex.

APPROX-RANDOM

Publications

Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
Understanding the Cluster Linear Program for Correlation Clustering. STOC (2024)
Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar
Matroid-based TSP rounding for half-integral solutions. Math. Program. 206 (1) (2024)
Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak
Approximating Small Sparse Cuts. CoRR (2024)
Euiwoong Lee, Pasin Manurangsi
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. ITCS (2024)
Aditya Anand, Euiwoong Lee
Separating k-Median from the Supplier Version. CoRR (2024)
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi
Max-Cut with ε-Accurate Predictions. CoRR (2024)
Aditya Anand, Euiwoong Lee
Separating k -sc Median from the Supplier Version. IPCO (2024)
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
-Low Rank Approximation: Solving Dense CSPs over Reals. SODA (2024)
Karthik C. S., Euiwoong Lee, Pasin Manurangsi
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP. CoRR (2024)
Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak
Approximating Small Sparse Cuts. STOC (2024)
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
Understanding the Cluster LP for Correlation Clustering. CoRR (2024)
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn
-Median. SODA (2023)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
-Center in Sparse Graphs. SOSA (2023)
Suprovat Ghoshal, Euiwoong Lee
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs. CoRR (2023)
Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Inapproximability of Matrix p → q Norms. SIAM J. Comput. 52 (1) (2023)
Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. FOCS (2023)
Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. CoRR (2023)
Anupam Gupta, Euiwoong Lee, Jason Li
A Local Search-Based Approach for Set Covering. SOSA (2023)
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
-Low Rank Approximation: Solving Dense CSPs over Reals. CoRR (2023)
Euiwoong Lee, Pasin Manurangsi
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. CoRR (2023)
Suprovat Ghoshal, Euiwoong Lee
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs. FOCS (2023)
Euiwoong Lee, Pengxiang Wang
Strong hardness of approximation for tree transversals. Inf. Process. Lett. 181 (2023)
Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li
-cut Problem. J. ACM 69 (1) (2022)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. ICALP (2022)
Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay
Fitting Metrics and Ultrametrics with Minimum Disagreements. FOCS (2022)
Anupam Gupta, Euiwoong Lee, Jason Li
A Local Search-Based Approach for Set Covering. CoRR (2022)
Euiwoong Lee, Viswanath Nagarajan, Lily Wang
On some variants of Euclidean k-supplier. Oper. Res. Lett. 50 (2) (2022)
Suprovat Ghoshal, Euiwoong Lee
A Characterization of Approximability for Biased CSPs. CoRR (2022)
Euiwoong Lee, Suprovat Ghoshal
A characterization of approximability for biased CSPs. STOC (2022)
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median. CoRR (2022)
Vijay Bhattiprolu, Euiwoong Lee, Madhur Tulsiani
Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem. ITCS (2022)
Jungho Ahn, Eun Jung Kim, Euiwoong Lee
Towards Constant-Factor Approximation for Chordal/Distance-Hereditary Vertex Deletion. Algorithmica 84 (7) (2022)
Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
Correlation Clustering with Sherali-Adams. CoRR (2022)
Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar
Matroid-Based TSP Rounding for Half-Integral Solutions. IPCO (2022)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. CoRR (2022)
Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
Correlation Clustering with Sherali-Adams. FOCS (2022)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
-metrics. SODA (2022)
Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay
Fitting Metrics and Ultrametrics with Minimum Disagreements. CoRR (2022)
Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar
Matroid-Based TSP Rounding for Half-Integral Solutions. CoRR (2021)
Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos
A Constant-Factor Approximation for Weighted Bond Cover. APPROX-RANDOM (2021)
Euiwoong Lee, Pengxiang Wang
Strong Hardness of Approximation for Tree Transversals. CoRR (2021)
Kijung Shin, Euiwoong Lee, Jinoh Oh, Mohammad Hammoud, Christos Faloutsos
CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams. ACM Trans. Knowl. Discov. Data 15 (3) (2021)
Euiwoong Lee, Viswanath Nagarajan, Lily Wang
On Some Variants of Euclidean K-Supplier. CoRR (2021)
Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos
A Constant-factor Approximation for Weighted Bond Cover. CoRR (2021)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics. CoRR (2021)
Anupam Gupta, Euiwoong Lee, Jason Li
The Connectivity Threshold for Dense Graphs. SODA (2021)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
On Approximability of Clustering Problems Without Candidate Centers. SODA (2021)
Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor
A framework for quadratic form maximization over convex sets through nonconvex relaxations. STOC (2021)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics. Electron. Colloquium Comput. Complex. 28 (2021)
Euiwoong Lee, Sahil Singla
Maximum Matching in the Online Batch-arrival Model. ACM Trans. Algorithms 16 (4) (2020)
Jungho Ahn, Eun Jung Kim, Euiwoong Lee
Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion. ISAAC (2020)
Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto, Mohammad Mahdian
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. AISTATS (2020)
Jungho Ahn, Eun Jung Kim, Euiwoong Lee
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion. CoRR (2020)
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms 13 (6) (2020)
Anupam Gupta, Euiwoong Lee, Jason Li
The Karger-Stein algorithm is optimal for k-cut. STOC (2020)
Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li
Optimal Bounds for the k-cut Problem. CoRR (2020)
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Electron. Colloquium Comput. Complex. 27 (2020)
Vaggos Chatziafratis, Neha Gupta, Euiwoong Lee
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering. CoRR (2020)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
On Approximability of Clustering Problems Without Candidate Centers. CoRR (2020)
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. CoRR (2020)
Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari
Improved 3LIN Hardness via Linear Label Cover. APPROX-RANDOM (2019)
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li
Tight FPT Approximations for $k$-Median and k-Means. CoRR (2019)
Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff
A PTAS for ℓp-Low Rank Approximation. SODA (2019)
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto, Euiwoong Lee, Mohammad Mahdian, Konstantin Makarychev, Grigory Yaroslavtsev
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. CoRR (2019)
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, Chao Xu
Beating the 2-approximation factor for global bicut. Math. Program. 177 (1-2) (2019)
Anupam Gupta, Euiwoong Lee, Jason Li
The Number of Minimum k-Cuts: Improving the Karger-Stein Bound. CoRR (2019)
Anupam Gupta, Euiwoong Lee, Jason Li
-cuts: improving the Karger-Stein bound. STOC (2019)
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li
Tight FPT Approximations for k-Median and k-Means. ICALP (2019)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. SODA (2019)
Anupam Gupta, Euiwoong Lee, Jason Li
The Karger-Stein Algorithm is Optimal for k-cut. CoRR (2019)
Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari
Improved 3LIN Hardness via Linear Label Cover. Electron. Colloquium Comput. Complex. 26 (2019)
Euiwoong Lee
Partitioning a graph into small pieces with applications to path transversal. Math. Program. 177 (1-2) (2019)
Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk
Losing Treewidth by Separating Subsets. SODA (2019)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Approximating Operator Norms via Generalized Krivine Rounding. CoRR (2018)
Euiwoong Lee, Sahil Singla
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. ESA (2018)
Badih Ghazi, Euiwoong Lee
LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes. IEEE Trans. Inf. Theory 64 (6) (2018)
Kijung Shin, Mohammad Hammoud, Euiwoong Lee, Jinoh Oh, Christos Faloutsos
Tri-Fly: Distributed Estimation of Global and Local Triangle Counts in Graph Streams. PAKDD (3) (2018)
Kijung Shin, Euiwoong Lee, Jinoh Oh, Mohammad Hammoud, Christos Faloutsos
DiSLR: Distributed Sampling with Limited Redundancy For Triangle Counting in Graph Streams. CoRR (2018)
Anupam Gupta, Euiwoong Lee, Jason Li
-Cut. SODA (2018)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Inapproximability of Matrix p→q Norms. Electron. Colloquium Comput. Complex. 25 (2018)
Euiwoong Lee, Sahil Singla
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. CoRR (2018)
Anupam Gupta, Euiwoong Lee, Jason Li
Faster Exact and Approximate Algorithms for k-Cut. CoRR (2018)
Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk
Losing Treewidth by Separating Subsets. CoRR (2018)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Approximating Operator Norms via Generalized Krivine Rounding. Electron. Colloquium Comput. Complex. 25 (2018)
Anupam Gupta, Euiwoong Lee, Jason Li
Faster Exact and Approximate Algorithms for k-Cut. FOCS (2018)
Venkatesan Guruswami, Euiwoong Lee
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. Comb. 38 (3) (2018)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Inapproximability of Matrix p→q Norms. CoRR (2018)
Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff
-Low Rank Approximation. CoRR (2018)
Anupam Gupta, Euiwoong Lee, Jason Li
An FPT Algorithm Beating 2-Approximation for k-Cut. CoRR (2017)
Venkatesan Guruswami, Euiwoong Lee
Towards a Characterization of Approximation Resistance for Symmetric CSPs. Theory Comput. 13 (1) (2017)
Guru Guruganesh, Euiwoong Lee
Understanding the Correlation Gap for Matchings. CoRR (2017)
Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. APPROX-RANDOM (2017)
Venkatesan Guruswami, Euiwoong Lee
Nearly Optimal NP-Hardness of Unique Coverage. SIAM J. Comput. 46 (3) (2017)
Euiwoong Lee
APX-hardness of maximizing Nash social welfare with indivisible items. Inf. Process. Lett. 122 (2017)
Venkatesan Guruswami, Euiwoong Lee
Inapproximability of H-Transversal/Packing. SIAM J. Discret. Math. 31 (3) (2017)
Euiwoong Lee, Sahil Singla
Maximum Matching in the Online Batch-Arrival Model. IPCO (2017)
Kijung Shin, Euiwoong Lee, Dhivya Eswaran, Ariel D. Procaccia
Why You Should Charge Your Friends for Borrowing Your Stuff. IJCAI (2017)
Janardhan Kulkarni, Euiwoong Lee, Mohit Singh
Minimum Birkhoff-von Neumann Decomposition. IPCO (2017)
Guru Guruganesh, Euiwoong Lee
Understanding the Correlation Gap For Matchings. FSTTCS (2017)
Euiwoong Lee, Melanie Schmidt, John Wright
Improved and simplified inapproximability for k-means. Inf. Process. Lett. 120 (2017)

Euiwoong Lee.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Euiwoong Lee