32 citations · 98 across the 32 of their papers we have counts for
6 papers · 1 filter
Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities
Shi Li
We study the non-uniform capacitated multi-item lot-sizing (\lotsizing) problem. In this problem, there is a set of demands over a planning horizon of time periods and all dema…
Tight Network Topology Dependent Bounds on Rounds of Communication
Arkadev Chattopadhyay, Michael Langberg, Shi Li +1
We prove tight network topology dependent bounds on the round complexity of computing well studied -party functions such as set disjointness and element distinctness. Unlike the…
Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions
Sungjin Im, Shi Li
In this paper we consider the classic scheduling problem of minimizing total weighted completion time on unrelated machines when jobs have release times, i.e, $R | r_{ij} | \sum_j…
Improved Approximation for Node-Disjoint Paths in Planar Graphs
Julia Chuzhoy, David H. K. Kim, Shi Li
We study the classical Node-Disjoint Paths (NDP) problem: given an -vertex graph and a collection of pairs of vertices of called deman…
Constant Approximation for Capacitated -Median with -Capacity Violation
Gökalp Demirci, Shi Li
We study the Capacitated k-Median problem for which existing constant-factor approximation algorithms are all pseudo-approximations that violate either the capacities or the upper…
On the computational complexity of minimum-concave-cost flow in a two-dimensional grid
Shabbir Ahmed, Qie He, Shi Li +1
We study the minimum-concave-cost flow problem on a two-dimensional grid. We characterize the computational complexity of this problem based on the number of rows and columns of th…