Shi Li

ORCID

Publication Activity (10 Years)

Years Active: 2010-2024
Publications (10 Years): 87

Top Venues

Publications

Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
Understanding the Cluster Linear Program for Correlation Clustering. STOC (2024)
Xiangyu Guo, Shi Li, Kelin Luo, Yuhao Zhang
Minimizing the Maximum Flow Time in the Online Food Delivery Problem. Algorithmica 86 (4) (2024)
Yuda Feng, Shi Li
A Note on Approximating Weighted Nash Social Welfare with Additive Valuations. CoRR (2024)
Shi Li, Chenyang Xu, Ruilong Zhang
Polylogarithmic Approximations for Robust s-t Path. ICALP (2024)
Sungjin Im, Ravi Kumar, Shi Li, Aditya Petety, Manish Purohit
Online Load and Graph Balancing for Random Order Inputs. CoRR (2024)
Yuda Feng, Shi Li
A Note on Approximating Weighted Nash Social Welfare with Additive Valuations. ICALP (2024)
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
Understanding the Cluster LP for Correlation Clustering. CoRR (2024)
Sungjin Im, Ravi Kumar, Shi Li, Aditya Petety, Manish Purohit
Online Load and Graph Balancing for Random Order Inputs. SPAA (2024)
Sungjin Im, Shi Li
Improved Approximations for Unrelated Machine Scheduling. SODA (2023)
Michael Dinitz, Guy Kortsarz, Shi Li
Degrees and Network Design: New Problems and Approximations. CoRR (2023)
Ravishankar Krishnaswamy, Shi Li, Varun Suriyanarayana
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse. STOC (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)
Shi Li
Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems. ICALP (2023)
Xiangyu Guo, Kelin Luo, Shi Li, Yuhao Zhang
Minimizing the Maximum Flow Time in the Online Food Delivery Problem. ISAAC (2022)
Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, Jiayi Xian
On Approximating Degree-Bounded Network Design Problems. Algorithmica 84 (5) (2022)
Shi Li, Bundit Laekhanukit
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree. SODA (2022)
Sungjin Im, Shi Li
Improved Approximations for Unrelated Machine Scheduling. CoRR (2022)
Ravishankar Krishnaswamy, Shi Li, Varun Suriyanarayana
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse. CoRR (2022)
Vincent Cohen-Addad, Yunus Esencayi, Chenglin Fan, Marco Gaboardi, Shi Li, Di Wang
On Facility Location Problem in the Local Differential Privacy Model. AISTATS (2022)
Shi Li, Jiayi Xian
Online Unrelated Machine Load Balancing with Predictions Revisited. ICML (2021)
Shi Li, Bundit Laekhanukit
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree. CoRR (2021)
Shi Li
Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms. SODA (2021)
Xiangyu Guo, Shi Li, Kelin Luo, Yuhao Zhang
Online Food Delivery to Minimize Maximum Flow Time. CoRR (2021)
Xiangyu Guo, Janardhan Kulkarni, Shi Li, Jiayi Xian
Consistent k-Median: Simpler, Better and Robust. AISTATS (2021)
Janardhan Kulkarni, Shi Li, Jakub Tarnawski, Minwei Ye
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints. SODA (2020)
Xiangyu Guo, Janardhan Kulkarni, Shi Li, Jiayi Xian
The Power of Recourse: Better Algorithms for Facility Location in Online and Dynamic Models. CoRR (2020)
Shi Li
Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms. CoRR (2020)
Shi Li, Sai Vikneshwar Mani Jayaraman, Atri Rudra
Covering the Relational Join. CoRR (2020)
Di Wang, Xiangyu Guo, Shi Li, Jinhui Xu
Robust high dimensional expectation maximization algorithm via trimmed hard thresholding. Mach. Learn. 109 (12) (2020)
Di Wang, Xiangyu Guo, Chaowen Guan, Shi Li, Jinhui Xu
Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably. CoRR (2020)
Di Wang, Xiangyu Guo, Chaowen Guan, Shi Li, Jinhui Xu
Estimating stochastic linear combination of non-linear regressions efficiently and scalably. Neurocomputing 399 (2020)
Xiangyu Guo, Janardhan Kulkarni, Shi Li, Jiayi Xian
Consistent k-Median: Simpler, Better and Robust. CoRR (2020)
Shi Li, Jinhui Xu, Minwei Ye
Approximating Global Optimum for Probabilistic Truth Discovery. Algorithmica 82 (10) (2020)
Di Wang, Xiangyu Guo, Chaowen Guan, Shi Li, Jinhui Xu
Estimating Stochastic Linear Combination of Non-Linear Regressions. AAAI (2020)
Sungjin Im, Shi Li, Benjamin Moseley
Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization. SIAM J. Discret. Math. 34 (3) (2020)
Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, Jiayi Xian
On Approximating Degree-Bounded Network Design Problems. APPROX-RANDOM (2020)
Chandra Chekuri, Shi Li
On the Hardness of Approximating the k-Way Hypergraph Cut problem. Theory Comput. 16 (2020)
Di Wang, Xiangyu Guo, Shi Li, Jinhui Xu
Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding. CoRR (2020)
Janardhan Kulkarni, Shi Li, Jakub Tarnawski, Minwei Ye
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints. CoRR (2020)
Xiangyu Guo, Janardhan Kulkarni, Shi Li, Jiayi Xian
On the Facility Location Problem in Online and Dynamic Models. APPROX-RANDOM (2020)
Michael Langberg, Shi Li, Sai Vikneshwar Mani Jayaraman, Atri Rudra
Topology Dependent Bounds For FAQs. CoRR (2020)
Shi Li
Constant Approximation Algorithm for Nonuniform Capacitated Multi-Item Lot Sizing via Strong Covering Inequalities. Math. Oper. Res. 45 (3) (2020)
Shi Li
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. SIAM J. Comput. 49 (4) (2020)
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li
)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. STOC (2019)
Shi Li
On Facility Location with General Lower Bounds. SODA (2019)
David G. Harris, Shi Li, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh
Approximation Algorithms for Stochastic Clustering. J. Mach. Learn. Res. 20 (2019)
Shashwat Garg, Janardhan Kulkarni, Shi Li
Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time. SODA (2019)
Xiangyu Guo, Bundit Laekhanukit, Shi Li, Jiayi Xian
Tight Approximation for Variants of Directed Steiner Tree via State-Tree Decomposition and Linear Programming Rounding. CoRR (2019)
Yunus Esencayi, Marco Gaboardi, Shi Li, Di Wang
Facility Location Problem in Differential Privacy Model Revisited. NeurIPS (2019)
Uriel Feige, Janardhan Kulkarni, Shi Li
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time. SODA (2019)
Yunus Esencayi, Marco Gaboardi, Shi Li, Di Wang
Facility Location Problem in Differential Privacy Model Revisited. CoRR (2019)
Michael Langberg, Shi Li, Sai Vikneshwar Mani Jayaraman, Atri Rudra
Topology Dependent Bounds For FAQs. PODS (2019)
Sixu Piao, Zhongjie Ba, Lu Su, Dimitrios Koutsonikolas, Shi Li, Kui Ren
Automating CSI Measurement with UAVs: from Problem Formulation to Energy-Optimal Solution. INFOCOM (2019)
Shi Li, Jinhui Xu, Minwei Ye
Approximating Global Optimum for Probabilistic Truth Discovery. COCOON (2018)
David G. Harris, Shi Li, Aravind Srinivasan, Khoa Trinh, Thomas W. Pensyl
Approximation algorithms for stochastic clustering. NeurIPS (2018)
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li
k/log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm. CoRR (2018)
David G. Harris, Shi Li, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh
Approximation algorithms for stochastic clustering. CoRR (2018)
Ravishankar Krishnaswamy, Shi Li, Sai Sandeep
Constant approximation for k-median and k-means with outliers via iterative rounding. STOC (2018)
Shi Li, Xiangyu Guo
Distributed k-Clustering for Data with Heavy Noise. NeurIPS (2018)
Shi Li, Xiangyu Guo
Distributed k-Clustering for Data with Heavy Noise. CoRR (2018)
Janardhan Kulkarni, Shi Li
Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models. APPROX-RANDOM (2018)
Uriel Feige, Janardhan Kulkarni, Shi Li
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time. CoRR (2018)
Shi Li
On Facility Location with General Lower Bounds. CoRR (2018)
Janardhan Kulkarni, Shi Li
Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models. CoRR (2018)
Shi Li
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. FOCS (2017)
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra
Tight Network Topology Dependent Bounds on Rounds of Communication. SODA (2017)
Shi Li
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. CoRR (2017)
Shi Li
Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities. SODA (2017)
Ravishankar Krishnaswamy, Shi Li, Sai Sandeep
Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding. CoRR (2017)
Sungjin Im, Shi Li, Benjamin Moseley
Breaking 1 - 1/e Barrier for Non-preemptive Throughput Maximization. IPCO (2017)
Shi Li
-Median Beyond the Natural LP Relaxation. ACM Trans. Algorithms 13 (2) (2017)
H. Gökalp Demirci, Shi Li
Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation. ICALP (2016)
Shabbir Ahmed, Qie He, Shi Li, George L. Nemhauser
On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid. SIAM J. Optim. 26 (4) (2016)
Julia Chuzhoy, Shi Li
A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2. J. ACM 63 (5) (2016)
H. Gökalp Demirci, Shi Li
Constant Approximation for Capacitated k-Median with (1 + ε)-Capacity Violation. CoRR (2016)
Mohammad Taghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha
-Median. ACM Trans. Algorithms 12 (3) (2016)
Sungjin Im, Shi Li
Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions. CoRR (2016)
Shi Li
open facilities. SODA (2016)
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra
Tight Network Topology Dependent Bounds on Rounds of Communication. CoRR (2016)
Sungjin Im, Shi Li
Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions. FOCS (2016)
Shi Li
Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities. CoRR (2016)
Shabbir Ahmed, Qie He, Shi Li, George L. Nemhauser
On the computational complexity of minimum-concave-cost flow in a two-dimensional grid. CoRR (2016)
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra
Tight Network Topology Dependent Bounds on Rounds of Communication. Electron. Colloquium Comput. Complex. 23 (2016)
Julia Chuzhoy, David H. K. Kim, Shi Li
Improved approximation for node-disjoint paths in planar graphs. STOC (2016)
Julia Chuzhoy, David H. K. Kim, Shi Li
Improved Approximation for Node-Disjoint Paths in Planar Graphs. CoRR (2016)
Shi Li, Ola Svensson
Approximating k-Median via Pseudo-Approximation. SIAM J. Comput. 45 (2) (2016)
Shi Li
-Median Beyond the Natural LP Relaxation. SODA (2015)
Shi Li, Gabriel H. Tucci
, δ)-Hyperbolic Spaces. Internet Math. 11 (2) (2015)
Sungjin Im, Shi Li, Benjamin Moseley, Eric Torng
A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]. SODA (2015)
Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li
)-Restricted Assignment Makespan Minimization. SODA (2015)
Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li
On $(1, ε)$-Restricted Assignment Makespan Minimization. CoRR (2014)
Shi Li
On Uniform Capacitated $k$-Median Beyond the Natural LP Relaxation. CoRR (2014)
Shi Li
Approximating capacitated $k$-median with $(1+ε)k$ open facilities. CoRR (2014)
Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li
Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach. SODA (2014)
Kaiyu Guan, David Medvigy, Eric F. Wood, Kelly K. Caylor, Shi Li, Su-Jong Jeong
Deriving Vegetation Phenological Time and Trajectory Information Over Africa Using SEVIRI Daily LAI. IEEE Trans. Geosci. Remote. Sens. 52 (2) (2014)
MohammadTaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha
-Median. SODA (2014)
Shi Li, Ola Svensson
Approximating k-median via pseudo-approximation. STOC (2013)
Shi Li
A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222 (2013)
Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Shi Li, Srivatsan Narayanan
Capacitated Network Design on Undirected Graphs. APPROX-RANDOM (2013)

Shi Li.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Shi Li