Source author record

Shichuan Deng

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

4works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Approximation Algorithms for Clustering with Dynamic Points

We study two generalizations of classic clustering problems called dynamic ordered $k$ -median and dynamic $k$ -supplier, where the points that need clustering evolve over time, and we are allowed to move the cluster centers between consecutive time steps. In these dynamic clustering problems, the general goal is to minimize certain combinations of the service cost of points and the movement cost of centers, or to minimize one subject to some constraints on the other. We obtain a constant-factor approximation algorithm for dynamic ordered $k$ -median under mild assumptions on the input. We give a 3-approximation for dynamic $k$ -supplier and a multi-criteria approximation for its outlier version where some points can be discarded, when the number of time steps is two. We complement the algorithms with almost matching hardness results.

preprint2022arXiv

Constant approximation for fault-tolerant median problems via iterative rounding

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 location problems, such as uniform fault-tolerant $k$ -median, uniform fault-tolerant facility location, matroid median, knapsack median, etc. We present a versatile iterative rounding framework and obtain a unifying constant-factor approximation algorithm.

preprint2022arXiv

Generalized Unrelated Machine Scheduling Problem

We study the generalized load-balancing (GLB) problem, where we are given $n$ jobs, each of which needs to be assigned to one of $m$ unrelated machines with processing times $\{p_{ij}\}$ . Under a job assignment $σ$ , the load of each machine $i$ is $ψ_i(\mathbf{p}_{i}[σ])$ where $ψ_i:\mathbb{R}^n\rightarrow\mathbb{R}_{\geq0}$ is a symmetric monotone norm and $\mathbf{p}_{i}[σ]$ is the $n$ -dimensional vector $\{p_{ij}\cdot \mathbf{1}[σ(j)=i]\}_{j\in [n]}$ . Our goal is to minimize the generalized makespan $ϕ(\mathsf{load}(σ))$ , where $ϕ:\mathbb{R}^m\rightarrow\mathbb{R}_{\geq0}$ is another symmetric monotone norm and $\mathsf{load}(σ)$ is the $m$ -dimensional machine load vector. This problem significantly generalizes many classic optimization problems, e.g., makespan minimization, set cover, minimum-norm load-balancing, etc. We obtain a polynomial time randomized algorithm that achieves an approximation factor of $O(\log n)$ , matching the lower bound of set cover up to constant factor. We achieve this by rounding a novel configuration LP relaxation with exponential number of variables. To approximately solve the configuration LP, we design an approximate separation oracle for its dual program. In particular, the separation oracle can be reduced to the norm minimization with a linear constraint (NormLin) problem and we devise a polynomial time approximation scheme (PTAS) for it, which may be of independent interest.

preprint2021arXiv

Generalized Load Balancing and Clustering Problems with Norm Minimization

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 function of the vectors. For example, in the problem of makespan minimization on unrelated parallel machines, a feasible job assignment induces a vector containing the sizes of assigned jobs for each machine, and the goal is to minimize the $L_\infty$ norm of $L_1$ norms of the vectors. Another example is fault-tolerant $k$ -center, where each client is connected to multiple open facilities, thus having a vector of distances to these facilities, and the goal is to minimize the $L_\infty$ norm of $L_\infty$ norms of these vectors. In this paper, we study the maximum of norm problem. Given an arbitrary symmetric monotone norm $f$ , the objective is defined as the maximum ( $L_\infty$ norm) of $f$ -norm values of the induced cost vectors. This versatile formulation captures a wide variety of problems, including makespan minimization, fault-tolerant $k$ -center and many others. We give concrete results for load balancing on unrelated parallel machines and clustering problems, including constant-factor approximation algorithms when $f$ belongs with a certain rich family of norms, and $O(\log n)$ -approximations when $f$ is general and satisfies some mild assumptions. We also consider the aforementioned problems in a generalized fairness setting. As a concrete example, the insight is to prevent a scheduling algorithm from assigning too many jobs consistently on any machine in a job-recurring scenario, and causing the machine's controller to fail. Our algorithm needs to stochastically output a feasible solution minimizing the objective function, and satisfy the given marginal fairness constraints.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Shichuan Deng

Research overview

Is this your work?

4 publications

Approximation Algorithms for Clustering with Dynamic Points

Constant approximation for fault-tolerant median problems via iterative rounding

Generalized Unrelated Machine Scheduling Problem

Generalized Load Balancing and Clustering Problems with Norm Minimization

See the researcher in context

Building this map preview