ﻻ يوجد ملخص باللغة العربية
In recent years, the capacitated center problems have attracted a lot of research interest. Given a set of vertices $V$, we want to find a subset of vertices $S$, called centers, such that the maximum cluster radius is minimized. Moreover, each center in $S$ should satisfy some capacity constraint, which could be an upper or lower bound on the number of vertices it can serve. Capacitated $k$-center problems with one-sided bounds (upper or lower) have been well studied in previous work, and a constant factor approximation was obtained. We are the first to study the capacitated center problem with both capacity lower and upper bounds (with or without outliers). We assume each vertex has a uniform lower bound and a non-uniform upper bound. For the case of opening exactly $k$ centers, we note that a generalization of a recent LP approach can achieve constant factor approximation algorithms for our problems. Our main contribution is a simple combinatorial algorithm for the case where there is no cardinality constraint on the number of open centers. Our combinatorial algorithm is simpler and achieves better constant approximation factor compared to the LP approach.
We study the $mathcal{F}$-center problem with outliers: given a metric space $(X,d)$, a general down-closed family $mathcal{F}$ of subsets of $X$, and a parameter $m$, we need to locate a subset $Sin mathcal{F}$ of centers such that the maximum dista
In the Metric Capacitated Covering (MCC) problem, given a set of balls $mathcal{B}$ in a metric space $P$ with metric $d$ and a capacity parameter $U$, the goal is to find a minimum sized subset $mathcal{B}subseteq mathcal{B}$ and an assignment of th
In this paper we initiate the study of the heterogeneous capacitated $k$-center problem: given a metric space $X = (F cup C, d)$, and a collection of capacities. The goal is to open each capacity at a unique facility location in $F$, and also to assi
The $k$-Facility Location problem is a generalization of the classical problems $k$-Median and Facility Location. The goal is to select a subset of at most $k$ facilities that minimizes the total cost of opened facilities and established connections
We discuss folklore statements about distance functions in manifolds with two sided bounded curvature. The topics include regularity, subsets of positive reach and the cut locus.