32 citations · 98 across the 32 of their papers we have counts for
5 papers · 2 filters
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…
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…