32 citations · 57 across the 8 of their papers we have counts for
4 papers · 1 filter
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…