Search

Team formation plays an essential role in the labor market. In this paper, we propose two bicriteria algorithms to construct a balance between gain and cost in a team formation problem under the streaming model, subject to a cardinality constraint. We formulate the problem as maximizing the difference of a non-negative normalized monotone submodular function and a non-negative linear function. As an extension, we also consider the case where the first function is $$\gamma $$ -weakly submodular. Combining the greedy technique with the threshold method, we present bicriteria streaming algorithms and give detailed analysis for both of these models. Our analysis is competitive with that in Ene’s work.

In this paper, we consider the Bregman k-means problem (BKM) which is a variant of the classical k-means problem. For an n-point set $${\mathcal {S}}$$ and $$k \le n$$ with respect to $$\mu $$ -similar Bregman divergence, the BKM problem aims first to find a center subset $$C \subseteq {\mathcal {S}}$$ with $$ \mid C \mid = k$$ and then separate $${\mathcal {S}}$$ into k clusters according to C, such that the sum of $$\mu $$ -similar Bregman divergence from each point in $${\mathcal {S}}$$ to its nearest center is minimized. We propose a $$\mu $$ -similar BregMeans++ algorithm by employing the local search scheme, and prove that the algorithm deserves a constant approximation guarantee. Moreover, we extend our algorithm to solve a variant of BKM called noisy $$\mu $$ -similar Bregman k-means++ (noisy $$\mu $$ -BKM++) which is BKM in the noisy scenario. For the same instance and purpose as BKM, we consider the case of sampling a point with an imprecise probability by a factor between $$1-\varepsilon _1$$ and $$1+ \varepsilon _2$$ for $$\varepsilon _1 \in [0,1)$$ and $$\varepsilon _2 \ge 0$$ , and obtain an approximation ratio of $$O(\log ^2 k)$$ in expectation.

The spherical k-means problem (SKMP) is an important variant of the k-means clustering problem (KMP). In this paper, we consider the SKMP, which aims to divide the n points in a given data point set $${\mathcal {S}}$$ into k clusters so as to minimize the total sum of the cosine dissimilarity measure from each data point to their respective closest cluster center. Our main contribution is to design an expected constant approximation algorithm for the SKMP by integrating the seeding algorithm for the KMP and the local search technique. By utilizing the structure of the clusters, we further obtain an improved LocalSearch++ algorithm involving $$\varepsilon k$$ local search steps.

In this paper, we consider the $$\tau $$ -relaxed soft capacitated facility location problem ( $$\tau $$ -relaxed SCFLP), which extends several well-known facility location problems like the squared metric soft capacitated facility location problem (SMSCFLP), soft capacitated facility location problem (SCFLP), squared metric facility location problem and uncapacitated facility location problem. In the $$\tau $$ -relaxed SCFLP, we are given a facility set $$\mathcal {F}$$ , a client set and a parameter $$\tau \ge 1$$ . Every facility $$i \in \mathcal {F}$$ has a capacity $$u_i$$ and an opening cost $$f_i$$ , and can be opened multiple times. If facility i is opened l times, this facility can be connected by at most $$l u_i$$ clients and incurs an opening cost of $$l f_i$$ . Every facility-client pair has a connection cost. Under the assumption that the connection costs are non-negative, symmetric and satisfy the $$\tau $$ -relaxed triangle inequality, we wish to open some facilities (once or multiple times) and connect every client to an opened facility without violating the capacity constraint so as to minimize the total opening costs as well as connection costs. As our main contribution, we propose a primal-dual based $$(3 \tau + 1)$$ -approximation algorithm for the $$\tau $$ -relaxed SCFLP. Furthermore, our algorithm not only extends the applicability of the primal-dual technique but also improves the previous approximation guarantee for the SMSCFLP from $$11.18+ \varepsilon $$ to 10.

Submodular optimization has been well studied in combinatorial optimization. However, there are few works considering about non-submodular optimization problems which also have many applications, such as experimental design, some optimization problems in social networks, etc. In this paper, we consider the maximization of non-submodular function under a knapsack constraint, and explore the performance of the greedy algorithm, which is characterized by the submodularity ratio $$\beta $$ and curvature $$\alpha $$ . In particular, we prove that the greedy algorithm enjoys a tight approximation guarantee of $$ (1-e^{-\alpha \beta })/{\alpha }$$ for the above problem. To our knowledge, it is the first tight constant factor for this problem. We further utilize illustrative examples to demonstrate the performance of our algorithm.

Correlation clustering problem is a clustering problem which has many applications such as protein interaction networks, cross-lingual link detection, communication networks, and social computing. In this paper, we introduce two variants of correlation clustering problem: correlation clustering problem on uncertain graphs and correlation clustering problem with non-uniform hard constrained cluster sizes. Both problems overcome part of the limitations of the existing variants of correlation clustering problem and have practical applications in the real world. We provide a constant approximation algorithm and two approximation algorithms for the former and the latter problem, respectively.

Spherical k-means clustering as a known NP-hard variant of the k-means problem has broad applications in data mining. In contrast to k-means, it aims to partition a collection of given data distributed on a spherical surface into k sets so as to minimize the within-cluster sum of cosine dissimilarity. In the paper, we introduce spherical k-means clustering with penalties and give a $$2\max \{2,M\}(1+M)(\ln k+2)$$-approximation algorithm. Moreover, we prove that when against spherical k-means clustering with penalties but on separable instances, our algorithm is with an approximation ratio $$2\max \{3,M+1\}$$ with high probability, where M is the ratio of the maximal and the minimal penalty cost of the given data set.

In this paper, we consider the uniform capacitated k-means problem (UC-k-means), an extension of the classical k-means problem (k-means) in machine learning. In the UC-k-means, we are given a set $$\mathcal {D}$$ of n points in d-dimensional space and an integer k. Every point in the d-dimensional space has an uniform capacity which is an upper bound on the number of points in $$\mathcal {D}$$ that can be connected to this point. Every two-point pair in the space has an associated connecting cost, which is equal to the square of the distance between these two points. We want to find at most k points in the space as centers and connect every point in $$\mathcal {D}$$ to some center without violating the capacity constraint, such that the total connecting costs is minimized. Based on the technique of local search, we present a bi-criteria approximation algorithm, which has a constant approximation guarantee and violates the cardinality constraint within a constant factor, for the UC-k-means.

In this paper, we consider a variant of the classical uncapacitated facility location problem, so-called squared metric two-stage stochastic facility location problem (SM-2-SFLP) which can treat the uncertainty of the set of clients and facility costs. We assume that the connection cost is squared metric, a variant of the metric case which is widely researched. We give a new 0–1 integer linear programming for SM-2-SFLP. Based on the new formulation, we apply two known algorithms to SM-2-SFLP, and analyze the approximation ratio and per-scenario bound respectively.

We investigate the maximum directed cut (MaxDC) problem by designing a spectral partitioning algorithm. Given a directed graph with nonnegative arc weights, we wish to obtain a bipartition of the vertices such that the total weight of the directed cut arcs is maximized. Relaxing the MaxDC problem as a quadratic program allows us to explore combinatorial properties of the optimal solution, leading to a 0.272-approximation algorithm via the technique of spectral partitioning rounding.

In this paper, we study the k-means problem with (nonuniform) penalties (k-MPWP) which is a natural generalization of the classic k-means problem. In the k-MPWP, we are given an n-client set $$ {\mathcal {D}} \subset {\mathbb {R}}^d$$ , a penalty cost $$p_j>0$$ for each $$j \in {\mathcal {D}}$$ , and an integer $$k \le n$$ . The goal is to open a center subset $$F \subset {\mathbb {R}}^d$$ with $$ |F| \le k$$ and to choose a client subset $$P \subseteq {\mathcal {D}} $$ as the penalized client set such that the total cost (including the sum of squares of distance for each client in $$ {\mathcal {D}} \backslash P $$ to the nearest open center and the sum of penalty cost for each client in P) is minimized. We offer a local search $$( 81+ \varepsilon )$$ -approximation algorithm for the k-MPWP by using single-swap operation. We further improve the above approximation ratio to $$( 25+ \varepsilon )$$ by using multi-swap operation.

In this paper, we introduce a squared metric k-facility location problem (SM-k-FLP) which is a generalization of the squared metric facility location problem and k-facility location problem (k-FLP). In the SM-k-FLP, we are given a client set $$\mathcal {C}$$ and a facility set $$\mathcal {F} $$ from a metric space, a facility opening cost $$f_i \ge 0$$ for each $$ i \in \mathcal {F}$$ , and an integer k. The goal is to open a facility subset $$F \subseteq \mathcal {F}$$ with $$ |F| \le k$$ and to connect each client to the nearest open facility such that the total cost (including facility opening cost and the sum of squares of distances) is minimized. Using local search and scaling techniques, we offer a constant approximation algorithm for the SM-k-FLP.

We present a $$(20+{5}/{n})$$(20+5/n)-approximation algorithm for the non-uniform soft capacitated k-facility location problem, violating the capacitated constrains by no more than a factor of 25. The main technique is based on the primal---dual algorithm for the soft capacitated facility location problem, and the exploitation of the combinatorial structure of the fractional solution for the soft capacitated k-facility location problem.

In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For each client–facility pair, there is an unit service cost to serve the client with unit demand by the facility. The total demands served by a facility cannot exceed the uniform capacity. We want to open at most k facilities to serve all the demands of the clients without violating the capacity constraint such that the total opening and serving cost is minimized. The main contribution of this work is to present the first combinatorial bi-criteria approximation algorithm for the UC-k-FLP by violating the cardinality constraint.

In this paper, we consider an extension of the classical facility location problem, namely k-facility location problem with linear penalties. In contrast to the classical facility location problem, this problem opens no more than k facilities and pays a penalty cost for any non-served client. We present a local search algorithm for this problem with a similar but more technical analysis due to the extra penalty cost, compared to that in Zhang (Theoretical Computer Science 384:126–135, 2007). We show that the approximation ratio of the local search algorithm is $$2 + 1/p + \sqrt{3+ 2/p+ 1/p^2} + \epsilon $$ , where $$p \in {\mathbb {Z}}_+$$ is a parameter of the algorithm and $$\epsilon >0$$ is a positive number.

We study a precedence-constrained identical parallel machine scheduling problem with rejection. There is a communication delay between any two jobs connected in the precedence network where jobs may be rejected with penalty. The goal is to minimize the sum of the makespan and the rejection cost. We propose two 3-approximation algorithms for this problem under linear and submodular rejection costs respectively. These two algorithms are both based on linear programming rounding technique.

Graph partition problems have been investigated extensively in combinatorial optimization. In this work, we consider an important graph partition problem which has applications in the design of VLSI circuits, namely, the balanced Max-3-Uncut problem. We formulate the problem as a discrete linear program with complex variables and propose an approximation algorithm with an approximation ratio of 0.3456 using a semidefinite programming rounding technique along with a greedy swapping step afterwards to guarantee the balanced constraint. Our analysis utilizes a bivariate function, rather than the univariate function in previous work.

We present a unified semidefinite programming hierarchies rounding approximation algorithm for a class of maximum graph bisection problems with improved approximation ratios. Under the above algorithmic framework, we show that the approximation ratios of Max- $$\frac{n}{2}$$ n 2 -cut, Max- $$\frac{n}{2}$$ n 2 -dense-subgraph, and Max- $$\frac{n}{2}$$ n 2 -vertex-cover are equal to those of Max- $$\frac{n}{2}$$ n 2 -uncut, Max- $$\frac{n}{2}$$ n 2 -directed-cut, and Max- $$\frac{n}{2}$$ n 2 -directed-uncut, respectively.

In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.

We consider the max-bisection problem and the disjoint 2-catalog segmentation problem, two well-known NP-hard combinatorial optimization problems. For the first problem, we apply the semidefinite programming (SDP) relaxation and the RPR2 technique of Feige and Langberg (J. Algorithms 60:1---23, 2006) to obtain a performance curve as a function of the ratio of the optimal SDP value over the total weight through finer analysis under the assumption of convexity of the RPR2 function. This ratio is shown to be in the range of [0.5,1]. The performance curve implies better approximation performance when this ratio is away from 0.92, corresponding to the lowest point on this curve with the currently best approximation ratio of 0.7031 due to Feige and Langberg (J. Algorithms 60:1---23, 2006). For the second problem, similar technique results in an approximation ratio of 0.7469, improving the previously best known result 0.7317 due to Wu et al. (J. Ind. Manag. Optim. 8:117---126, 2012).

We consider the k-level capacitated facility location problem (k-CFLP), which is a natural variant of the classical facility location problem and has applications in supply chain management. We obtain the first (combinatorial) approximation algorithm with a performance factor of $k+2+\sqrt{k^{2}+2k+5}+\varepsilon$ (?>0) for this problem.