Shi Li's Publications

Manuscripts

• Nairen Cao, S. Li and Jia Ye, Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering, Manuscript

Conference Papers

• S. Li, Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs, SODA 2025
• Michael Dinitz, Guy Kortsarz and S. Li, Degrees and Network Design: New Problems and Approximations, APPROX + RANDOM 2024
• Yuda Feng and S. Li, A Note on Approximating Weighted Nash Social Welfare with Additive Valuations, ICALP 2024, Best Paper Award of Track A
• S. Li, Chenyang Xu and Ruilong Zhang, Polylogarithmic Approximation for Robust s-t Path, ICALP 2024
• Sungjin Im, Ravi Kumar, S. Li, Aditya Petety and Manish Purohit, Online Load and Graph Balancing for Random Order Inputs, SPAA 2024, Outstanding Paper Award
• Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, S. Li, Alantha Newman and Lukas Vogl, Understanding the Cluster Linear Program for Correlation Clustering, STOC 2024
• Vincent Cohen-Addad, Euiwoong Lee, S. Li and Alantha Newman, Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering, FOCS 2023
• S. Li, Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems, ICALP 2023
• Ravishankar Krishnaswamy, S. Li and Varun Suriyanarayana, Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse, STOC 2023
• Sungjin Im and S. Li, Improved Approximations for Unrelated Machine Scheduling, SODA 2023
• Nairen Cao, Jeremy T. Fineman, S. Li, Julian Mestre, Katina Russell and Seeun William Umboh, Nested Active-Time Scheduling, ISAAC 2022
• Xiangyu Guo, S. Li, Kelin Luo and Yuhao Zhang, Online Food Delivery to Minimize Maximum Flow Time, ISAAC 2022
• Vincent Cohen-Addad, Yunus Esencayi, Chenglin Fan, Marco Gaboardi, S. Li and Di Wang, On Facility Location Problem in Local Differential Privacy Model, AISTATS 2022
• S. Li and Bundit Laekhanukit, Polynomial Integrality Gap of Flow LP for Directed Steiner Tree, SODA 2022
• S. Li and Jiayi Xian, Online Unrelated Machine Load Balancing with Predictions Revisited, ICML 2021, long presentation
• Xiangyu Guo, Janardhan Kulkarni, S. Li and Jiayi Xian, Consistent k-Median: Simpler, Better and Robust, AISTATS 2021
• S. Li, Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms, SODA 2021
• Di Wang, Xiangyu Guo, S. Li and Jinhui Xu, Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding, ACML 2020
• Xiangyu Guo, Janardhan Kulkarni, S. Li and Jiayi Xian, On the Facility Location Problem in Online and Dynamic Models, APPROX 2020
• Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, S. Li, Daniel Vaz and Jiayi Xian, On Approximating Degree-Bounded Network Design Problems, APPROX 2020
• Di Wang, Xiangyu Guo, Chaowen Guan, S. Li and Jinhui Xu, Estimating Stochastic Linear Combination of Non-linear Regressions, AAAI 2020
• Janardhan Kulkarni, S. Li, Jakub Tarnawski and Minwei Ye, Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints, SODA 2020
• Yunus Esencayi, Marco Gaboardi, S. Li and Di Wang, Facility Location Problem in Differential Privacy Model Revisited, NeurIPS 2019
• Fabrizio Grandoni, Bundit Laekhanukit and S. Li, O(log²k/loglog k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm, STOC 2019, invited to a special issue of SICOMP
• Sixu Piao, Zhongjie Ba, Dimitrios Koutsonikolas, Lu Su, S. Li and Kui Ren, Automating CSI Measurement with UAVs: from Problem Formulation to Energy-Optimal Solution, InfoComm 2019
• Michael Langberg, S. Li, Sai Vikneshwar Mani Jayaraman and Atri Rudra, Topology Dependent Bounds for (Some) FAQs, PODS 2019
• Shashwat Garg, Janardhan Kulkarni and S. Li, Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time, SODA 2019
• S. Li, On Facility Location with General Lower Bounds, SODA 2019
• Uri Feige, Janardhan Kulkarni and S. Li, A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time, SODA 2019
• Xiangyu Guo and S. Li, Distributed k-Clustering for Data with Heavy Noise, NeurIPS 2018, Spotlight
• David Harris, S. Li, Thomas Pensyl, Aravind Srinivason and Khoa Trinh, Approximation Algorithms for Stochastic Clustering, NeurlIPS 2018
• Janardhan Kulkarni and S. Li, Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models, APPROX 2018 (arXiv)
• S. Li, Minwei Ye and Jinhui Xu, Approximating Global Optimum for Probabilistic Truth Discovery, COCOON 2018, best paper award
• Ravishankar Krishnaswamy, S. Li and Sai Sandeep, Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding, STOC 2018
• S. Li, Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations, FOCS 2017, invited to a special issue of SICOMP
• Sungjin Im, S. Li and Benjamin Moseley, Breaking 1-1/e Barrier for Non-preemptive Throughput Maximization, IPCO 2017
• S. Li, Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities, SODA 2017
• Arkadev Chattopadhyay, Michael Langberg, S. Li and Atri Rudra, Tight Network Topology Dependent Bounds on Rounds of Communication, SODA 2017
• Sungjin Im and S. Li, Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions, FOCS 2016
• Gokalp Demirci and S. Li, Constant Approximation for Capacitated k-Median with (1+ε)-Capacity Violation, ICALP 2016
• Julia Chuzhoy, David Kim and S. Li, Improved Approximation for Node-Disjoint Paths in Planar Graphs, STOC 2016
• S. Li, Approximating Capacitated k-Median with (1+ε)k Open Facilities, SODA 2016
• Deeparnab Chakrabarty, Sanjeev Khanna and S. Li, On (1,ε)-Restricted Asgsignment Makespan Minimization, SODA 2015
• Sungjin Im, S. Li, Benjamin Moseley and Eric Torng, A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines, SODA 2015
• S. Li, On Uniform Capacitated k-Median beyond the Natural LP Relaxation, SODA 2015
• Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy and S. Li, Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach, SODA 2014
• Mohammadtaghi Hajiaghayi, Hu, Jian Li, S. Li and Barna Saha, A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median, SODA 2014
• Deeparnab Chakrabarty, Ravishankar Krishnaswamy, S. Li and Srivatsan Narayanan, Capacitated Network Design on Undirected Graphs, APPROX and RANDOM 2013
• S. Li and Ola Svensson, Approximating k-Median via Pseudo-Approximation, STOC 2013
• Julia Chuzhoy and S. Li, A Polylogarithmic Approximation for Edge-Disjoint-Paths with Congestion 2, FOCS 2012, co-winner of best paper award
• Moses Charikar and S. Li, A Dependent LP-Rounding Approach for the k-Median Problem, ICALP 2012 (extended)
• Parinya Chalermsook, Julia Chuzhoy, Alina Ene and S. Li, Approximation Algorithms and Hardness of Integral Concurrent Flow, STOC 2012 (extended)
• S. Li, A 1.488-Approximation Algorithm for the Uncapacitated Facility Location Problem, ICALP 2011, best student paper of Track A
• Moses Charikar, Tom Leighton, S. Li and Ankur Moitra, Vertex Sparsifiers and Abstract Rounding Algorithms, FOCS 2010
• S. Li, Xiang-Yang Li and YunHao Liu, Capacity of Large Scale Wireless Networks under Gaussian Channel Model, Mobicom 08

Journal Papers

• S. Li and Bundit Laekhanukit, Polynomial Integrality Gap of Flow LP for Directed Steiner Tree, ACM Transactions on Algorithms, 2024
• Fabrizio Grandoni, Bundit Laekhanukit and S. Li, O(log² k/ log log k)-Approximation Algorithm for Directed Steiner Tree, A Tight Quasi-Polynomial-Time Algorithm, SIAM Journal on Computing, 2023
• Xiangyu Guo, S. Li, Kelin Luo and Yuhao Zhang, Minimizing the Maximum Flow Time in the Online Food Delivery Problem, Algorithmic, 2023
• Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, S. Li, Daniel Vaz and Jiayi Xian, On Approximating Degree-Bounded Network Design Problems, Algorithmica
• Chandra Chekuri and S. Li, A note on the hardness of approximating the k-way Hypergraph Cut problem, Theory of Computing
• Sungjin Im, S. Li and Benjamin Moseley, Breaking 1-1/e Barrier for Non-preemptive Throughput Maximization, SIAM Journal on Discrete Mathematics
• S. Li, Jinhui Xu and Minwei Ye, Approximating global optimum for probabilistic truth discovery, Algorithmica
• David Harris, S. Li, Thomas Pensyl, Aravind Srinivason and Khoa Trinh, Approximation algorithms for stochastic clustering, Journal of Machine Learning Research
• S. Li, Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations, SIAM Journal on Computing, Special Section for FOCS 2017
• S. Li, Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities, Mathematics of Operations Research
• Julia Chuzhoy and S. Li, A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2, Journal of ACM 63(5), Dec 2016
• Shabbir Ahmed, Qie He, S. Li and George Nemhauser, On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid, SIAM Journal on Optimization
• S. Li, On Uniform Capacitated k-Median beyond the Natural LP Relaxation, Transactions on Algorithms 13(2), Jan 2017
• S. Li and Ola Svensson, Approximating k-Median via Pseudo-Approximation, SIAM Journal on Computing 45(2), 2016
• Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li, S. Li and Barna Saha, A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median, Transactions on Algorithms 12(3), June 2016
• S. Li and Gabriel Tucci, Traffic Congestion in Expanders and (p,δ)-Hyperbolic Spaces, Internet Mathematics 11(2), 2015
• S. Li, A 1.488-Approximation Algorithm for the Uncapacitated Facility Location Problem, Information and Computation 222, January 2013