1 citations · 2 across the 6 of their papers we have counts for
6 papers · 1 filter
Constant approximation for fault-tolerant median problems via iterative rounding
Shichuan Deng
In this paper, we study the fault-tolerant matroid median and fault-tolerant knapsack median problems. These two problems generalize many fundamental clustering and facility locati…
Generalized Unrelated Machine Scheduling Problem
Shichuan Deng, Jian Li, Yuval Rabani
We study the generalized load-balancing (GLB) problem, where we are given jobs, each of which needs to be assigned to one of unrelated machines with processing times $\{p_{…
On Clustering with Discounts
Shichuan Deng
We study the -median with discounts problem, wherein we are given clients with non-negative discounts and seek to open at most facilities. The goal is to minimize the sum of…
Ordered -Median with Outliers and Fault-Tolerance
Shichuan Deng, Qianfan Zhang
In this paper, we study two natural generalizations of ordered -median, named robust ordered -median and fault-tolerant ordered -median. In ordered -median, given a fin…
Generalized Load Balancing and Clustering Problems with Norm Minimization
Shichuan Deng
In many fundamental combinatorial optimization problems, a feasible solution induces some real cost vectors as an intermediate result, and the optimization objective is a certain f…
Approximation Algorithms for Clustering with Dynamic Points
Shichuan Deng, Jian Li, Yuval Rabani
We study two generalizations of classic clustering problems called dynamic ordered -median and dynamic -supplier, where the points that need clustering evolve over time, and…