Source author record

Shanfei Li

Shanfei Li appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms math.OC

Catalog footprint

What is connected

3works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2014arXiv

An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem

In the $k$-median problem, given a set of locations, the goal is to select a subset of at most $k$ centers so as to minimize the total cost of connecting each location to its nearest center. We study the uniform hard capacitated version of the $k$-median problem, in which each selected center can only serve a limited number of locations. Inspired by the algorithm of Charikar, Guha, Tardos and Shmoys, we give a $(6+10α)$-approximation algorithm for this problem with increasing the capacities by a factor of $2+\frac{2}α, α\geq 4$, which improves the previous best $(32 l^2+28 l+7)$-approximation algorithm proposed by Byrka, Fleszar, Rybicki and Spoerhase violating the capacities by factor $2+\frac{3}{l-1}, l\in \{2,3,4,\dots\}$.

preprint2014arXiv

Approximation Algorithms for Hard Capacitated $k$-facility Location Problems

We study the capacitated $k$-facility location problem, in which we are given a set of clients with demands, a set of facilities with capacities and a constant number $k$. It costs $f_i$ to open facility $i$, and $c_{ij}$ for facility $i$ to serve one unit of demand from client $j$. The objective is to open at most $k$ facilities serving all the demands and satisfying the capacity constraints while minimizing the sum of service and opening costs. In this paper, we give the first fully polynomial time approximation scheme (FPTAS) for the single-sink (single-client) capacitated $k$-facility location problem. Then, we show that the capacitated $k$-facility location problem with uniform capacities is solvable in polynomial time if the number of clients is fixed by reducing it to a collection of transportation problems. Third, we analyze the structure of extreme point solutions, and examine the efficiency of this structure in designing approximation algorithms for capacitated $k$-facility location problems. Finally, we extend our results to obtain an improved approximation algorithm for the capacitated facility location problem with uniform opening cost.

preprint2013arXiv

Improved approximation algorithm for k-level UFL with penalties, a simplistic view on randomizing the scaling parameter

The state of the art in approximation algorithms for facility location problems are complicated combinations of various techniques. In particular, the currently best 1.488-approximation algorithm for the uncapacitated facility location (UFL) problem by Shi Li is presented as a result of a non-trivial randomization of a certain scaling parameter in the LP-rounding algorithm by Chudak and Shmoys combined with a primal-dual algorithm of Jain et al. In this paper we first give a simple interpretation of this randomization process in terms of solving an aux- iliary (factor revealing) LP. Then, armed with this simple view point, Abstract. we exercise the randomization on a more complicated algorithm for the k-level version of the problem with penalties in which the planner has the option to pay a penalty instead of connecting chosen clients, which results in an improved approximation algorithm.