Search

The \begin{document}$k$\end{document} -center clustering is one of the well-studied clustering problems in computer science. We are given a set of data points \begin{document}$P\subseteq R^d$\end{document} , where \begin{document}$R^d$\end{document} is \begin{document}$d$\end{document} dimensional Euclidean space. We need to select \begin{document}$k≤ |P|$\end{document} points as centers and partition the set \begin{document}$P$\end{document} into \begin{document}$k$\end{document} clusters with each point connecting to its nearest center. The goal is to minimize the maximum radius. We consider the so-called online \begin{document}$k$\end{document} -center clustering model where the data points in \begin{document}$R^d$\end{document} arrive over time. We present the bi-criteria \begin{document}$(\frac{n}{k}, (\log\frac{U^*}{L^*})^2)$\end{document} -competitive algorithm and \begin{document}$(\frac{n}{k}, \logγ\log\frac{nγ}{k})$\end{document} -competitive algorithm for semi-online and fully-online \begin{document}$k$\end{document} -center clustering respectively, where \begin{document}$U^*$\end{document} is the maximum cluster radius of optimal solution, \begin{document}$L^*$\end{document} is the minimum distance of two distinct points of \begin{document}$P$\end{document} , \begin{document}$γ$\end{document} is the ratio of the maximum distance of two distinct points and the minimum distance of two distinct points of \begin{document}$P$\end{document} and \begin{document}$n$\end{document} is the number of points that will arrive in total.

Different from the classical \begin{document}$ k $\end{document}-means problem, the functional \begin{document}$ k $\end{document}-means problem involves a kind of dynamic data, which is generated by continuous processes. In this paper, we mainly design an \begin{document}$ O(\ln\; k) $\end{document}-approximation algorithm based on the seeding method for functional \begin{document}$ k $\end{document}-means problem. Moreover, the numerical experiment presented shows that this algorithm is more efficient than the functional \begin{document}$ k $\end{document}-means clustering algorithm.

We study stable instances of the \begin{document}$ k $\end{document}-means problem with penalties in fixed-dimensional Euclidean space. An instance of the problem is called \begin{document}$ \alpha $\end{document}-stable if this instance exists a sole optimal solution and the solution keeps unchanged when distances and penalty costs are scaled by a factor of no more than \begin{document}$ \alpha $\end{document}. Stable instances of clustering problem have been used to explain why certain heuristic algorithms with poor theoretical guarantees perform quite well in practical. For any fixed \begin{document}$ \epsilon > 0 $\end{document}, we show that when using a common multi-swap local-search algorithm, a \begin{document}$ (1+\epsilon) $\end{document}-stable instance of the \begin{document}$ k $\end{document}-means problem with penalties in fixed-dimensional Euclidean space can be solved accurately in polynomial time.

The \begin{document}$ k $\end{document}-means problem is a classical combinatorial optimization problem which has lots of applications in many fields such as machine learning, data mining, etc. We consider a variant of \begin{document}$ k $\end{document}-means problem in the spherical space, that is, spherical \begin{document}$ k $\end{document}-means problem with penalties. In the problem, it is allowable that some nodes in the spherical space can not be clustered by paying some penalty costs. Based on local search scheme, we propose a \begin{document}$ \left(4 (11+4\sqrt{7})+ \epsilon\right) $\end{document}-approximation algorithm using singe-swap operation, where \begin{document}$ \epsilon $\end{document} is a positive constant.

The problem of maximizing a given set function with a cardinality constraint has widespread applications. A number of algorithms have been provided to solve the maximization problem when the set function is monotone and submodular. However, reality-based set functions may not be submodular and may involve large-scale and noisy data sets. In this paper, we present the Stochastic-Lazier-Greedy Algorithm (SLG) to solve the corresponding non-submodular maximization problem and offer a performance guarantee of the algorithm. The guarantee is related to a submodularity ratio, which characterizes the closeness of to submodularity. Our algorithm also can be viewed as an extension of several previous greedy algorithms.

We study two unrelated machine scheduling problems with machine dependent release dates to minimize the makespan. For the case with fixed processing time where processing job $j$ on machine $i$ requires time $p_{ij}$ and incurs a cost of $c_{ij}$, we derive a $2$-approximation algorithm. For the problem with variable processing times where the cost increases linearly as the processing time decreases, we propose a $(2+\epsilon)$-approximation algorithm.

We introduce two set cover problems with submodular costs and linear/submodular penalties and offer two approximation algorithms of ratios $\eta$ and $2\eta$ respectively via the primal-dual technique, where $\eta$ is the largest number of sets that each element belongs to.

In this paper, we consider the $k$-level facility location problem with submodular penalties ($k$-FLPSP). We propose a primal-dual $6$-approximation (combinatorial) algorithm for the $k$-FLPSP.

In this paper, we consider the $2$-catalog segmentation problem. For the disjoint version, we propose an approximation algorithm based on the non-uniform rotation technique using a semidefinite programming ($SDP$) relaxation. We give the performance curve depending on the ratio between the value of optimal SDP solution and the total weight. In this curve, the lowest point implies the approximation ratio is $0.7317$ which is the best ratio for the disjoint version until now. We also consider the performance curve of the joint version.