Search

In this paper, we study the generalized submodular maximization problem with a non-negative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter α ∈ [ 0 , 1 ] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for α = 1 . For general value of the curvature parameter α ∈ [ 0 , 1 ] , we present an approximation algorithm with a factor of 1 + h α ( y ) + Δ ⋅ [ 3 + α − ( 2 + α ) y − ( 1 + α ) h α ( y ) ] 2 + α + ( 1 + α ) ( 1 − y ) , where y ∈ [ 0 , 1 ] is a predefined parameter for tuning the ratio. In particular, when α = 1 we obtain a ratio 0.5008 when setting y = 0.9 , coinciding with the renowned state-of-art approximate ratio; when α = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions.

In the paper, we consider the problem of maximizing the multilinear extension of a nonsubmodular set function subject to a k-cardinality constraint with adaptive rounds of evaluation queries. We devise an algorithm which achieves a ratio of ( 1 − e − γ 2 − ϵ ) and requires O ( log ⁡ n / ϵ 2 ) adaptive rounds and O ( n log ⁡ n / ϵ 2 ) queries, where γ is the continuous generic submodularity ratio that compares favorably in flexibility to the traditional submodularity ratio proposed by Das and Kempe. The key idea of our algorithm is originated from the parallel-greedy algorithm proposed by Chekuri et al., but incorporating with two major changes to retain the performance guarantee: First, identify all good coordinates with the continuous generic submodularity ratio and gradient values approximately as large as the best coordinate, and increase along all these coordinates uniformly; Second, increase x along these coordinates by a dynamical increment whose value depends on γ. The key difficulty of our algorithm is that when the function is nonsubmodular, the set of the best coordinate does not decrease during iterations; while provided submodularity, the decreasing can be ensured by the parallel-greedy algorithm. Our algorithms slightly compromise performance guarantee for the sake of extending to constrained nonsubmodular maximization with parallelism, provided that the state-of-art algorithm for the corresponding submodular version attains an approximation ratio of ( 1 − 1 / e − ϵ ) and requires O ( log ⁡ n / ϵ 2 ) adaptive rounds.

In the spherical k-means problem (SKMP), which is a well-studied clustering problem in text mining, we are given an n-point set D in d-dimensional unit sphere S d , and an integer k ≤ n . The goal is to find a center subset S ⊂ S d with | S | ≤ k that minimizes the sum of cosine dissimilarity measure for each point in D to the nearest center. We prove that any γ-approximation algorithm for the k-means problem (KMP) can be adapted to the SKMP with 2γ-approximation ratio. It follows that there is a local search ( 18 + ϵ ) -approximation algorithm for the SKMP, by leveraging the classical local search ( 9 + ϵ ) -approximation algorithm for the KMP. Therefore, an interesting problem arises, that is whether there exists an approximation algorithm using local search scheme directly for the SKMP. In this paper, we present a local search approximation algorithm for the SKMP and prove its performance guarantee is ( 2 ( 4 + 7 ) + ϵ ) . We also conduct numerical computation to show the efficiency of the local search approximation algorithm by single-swap operation in the end.

In this work, we investigate online bicriteria algorithms that consider both coverage and cost in the team formation problem, which selects a set of experts with the objective of maximizing the difference of two set functions f − l , where function f is non-negative normalized monotone approximately submodular, and function l is non-negative linear. By exploiting the problem's combinatorial structure, we present three bicriteria algorithms along with their corresponding competitive analysis. The first two algorithms handle the cases where function f is γ-weakly submodular, and strictly γ-weakly submodular, respectively. The last algorithm is more general by integrating the first two with extra parameters introduced.

In this paper, we investigate the two-stage submodular maximization problem, where there is a collection F = { f 1 , . . . , f m } of m submodular functions which are defined on the same element ground set Ω. The goal is to select a subset S ⊆ Ω of size at most l such that 1 m ∑ f ∈ F max T ⊆ S , T ∈ I ⁡ f ( T ) is maximized, where I denotes a specifically-defined independence system. We consider the two-stage submodular maximization with a P-matroid constraint and present a ( 1 / ( P + 1 ) ) ( 1 − 1 / e ( P + 1 ) ) -approximation algorithm. Furthermore, we extend the algorithm to the two-stage submodular maximization with a more generalized P-exchange system constraint and show the approximation ratio can be maintained with slightly modifications of the algorithm.

In this paper, we consider the dynamic k-level facility location problem, which is a generalization of the uncapacitated k-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for the problem which finds a solution within 6 times the optimum. This approximation ratio under a dynamic setting coincides with that of the simple dual ascent 6-approximation algorithm for the (static) multilevel facility location problem (Bumb, 2001) with a weak triangle inequality property.

We propose and study the MpUFLP (universal facility location problem in the p-th power of metric space) in this paper, where the universal facility location problem (UFLP) extends several classical facility location problems like the uncapacitated facility location, hard-capacitated facility location, soft-capacitated facility location, incremental-cost facility location, concave-cost facility location, etc. In UFLP, a set of facilities, a set of clients, as well as the distances between them are given. Each facility has its specific cost function w.r.t. the amount of clients assigned to that facility. The goal is to assign the clients to facilities such that the sum of facility cost and service cost is minimized. In traditional facility location problems, the unit service cost is proportional to the distance between the client and its assigned facility and thus metric. However, in our work, this assumption is removed and a generalized version of universal facility location problem is proposed, which is the so-called MnUFLP. When p = 2 , it is also known as l 2 2 measure considered by Jain and Vazirani [J. ACM'01] and Fernandes et al. [Math. Program.'15]. Particularly in this case, we extend their work to include the aforementioned variants of facility location and a local search based ( 11.18 + e ) -approximation algorithm is proposed. Furthermore, the reanalysis of the proposed algorithm gives a p-related performance guarantee for general p.

Given a seller with k types of items and n single-minded buyers, i.e., each buyer is only interested in a particular bundle of items, to maximize the revenue, the seller must assign some amount of bundles to each buyer with respect to the buyer's accepted price. Each buyer b i is associated with a value function v i ( ⋅ ) such that v i ( x ) is the accepted unit bundle price b i is willing to pay for x bundles. In this paper, we assume that bundles can be sold fractionally. The single-minded item selling problem is proved to be NP-hard. Moreover, we give an O ( k ) -approximation algorithm. For the online version, i.e., buyers come one by one and the decision must be made immediately on the arrival of each buyer, an O ( k ⋅ ( log ⁡ h + log ⁡ k ) ) -competitive algorithm is given, where h is the highest unit item price among all buyers.

Given a ground set U with a non-negative weight w i for each i ∈ U , a positive integer k and a collection of sets S , which is partitioned into a family of disjoint groups G , the goal of the Maximum Coverage problem with Group budget constraints (MCG) is to select k sets from S , such that the total weight of the union of the k sets is maximized and at most one set is selected from each group G ∈ G . We first present an approximation algorithm with a factor 1 − 1 e and an exponential time via randomized linear programming rounding technique. Then we improve the time complexity of the algorithm to O ( ( m + n ) 3.5 L + k 3.5 q 7 L ) for | S | = m , | U | = n , and L being the length of the input, by the key idea of modeling the selection of groups as computing a constrained flow in a corresponding auxiliary graph. The algorithm is later shown can be extended to solve two generalizations of MCG. Last but not the least, we present another algorithm with a time complexity O ( ( m + n ) 3.5 L + k δ 10.5 L ) and a slightly increased approximation ratio 1 − e 1 δ − 1 mainly based on the idea of partition, where δ ≥ 2 is a parameter tuning which can balance the time complexity and the ratio.

The input of the universal facility location problem includes a set of clients and a set of facilities. Our goal is to find an assignment such that each client is assigned while the total connection and facility cost is minimized. Here the connection cost is proportional to the distance between each client and its assigned facility, thus metric. The facility cost is a nondecreasing function with respect to the total number of clients assigned to the facility. The universal facility location problem is NP-hard since it generalizes several classical facility location problems. Our work considers the universal facility location problem with linear penalties, a generalized version of the universal facility location problem. Here each client can be rejected for service with certain penalty cost. Thus we have to consider penalty cost other than total connection and facility cost in our objective function. Based on local search method, we present a ( 5.83 + ϵ ) -approximation algorithm for this problem.

In the study of the homophily law of large scale complex networks, we get a combinatorial optimization problem which we call the Max k -Uncut problem. Given an n-vertex undirected graph G = ( V , E ) with nonnegative weights { w e | e ∈ E } defined on edges, and a positive integer k, the Max k -Uncut problem asks to find a partition { V 1 , V 2 , ⋯ , V k } of V such that the total weight of edges that are not cut is maximized. Intuitively, an edge that is not cut connects two vertices with the same or similar attributes since they are in the same part of the partition. Interestingly, the Max k -Uncut problem is just the complement of the classic Min k -Cut problem. For Max k -Uncut , we present a randomized ( 1 − k n ) 2 -approximation algorithm, a greedy ( 1 − 2 ( k − 1 ) n ) -approximation algorithm, and an Ω ( 1 2 α ) -approximation algorithm by reducing it to Densest k -Subgraph , where α is the approximation ratio of the Densest k -Subgraph problem. More importantly, we show that Max k -Uncut and Densest k -Subgraph are in fact equivalent in approximability up to a factor of 2. We also prove an approximation hardness result for Max k -Uncut under the assumption P ≠ NP .

We present a ( 1 + 3 + ϵ ) -approximation algorithm for the k-median problem with uniform penalties, extending the recent result by Li and Svensson for the classical k-median problem without penalties. One important difference of this work from that of Li and Svensson is a new definition of sparse instance to exploit the combinatorial structure of our problem.

The notion of penalty has been introduced into many combinatorial optimization models. In this paper, we consider the submodular vertex cover problems with linear and submodular penalties, which are two variants of the submodular vertex cover problem where not all the edges are required to be covered by a vertex cover, and the uncovered edges are penalized. The problem is to determine a vertex subset to cover some edges and penalize the uncovered edges such that the total cost including covering and penalty is minimized. To overcome the difficulty of implementing the primal-dual framework directly, we relax the two dual programs to slightly weaker versions. We then present two primal-dual approximation algorithms with approximation ratios of 2 and 4, respectively.

We offer the currently best approximation ratio 2.375 for the facility location problem with submodular penalties (FLPSP), improving not only the previous best combinatorial ratio 3, but also the previous best non-combinatorial ratio 2.488. We achieve this improved ratio by combining the primal-dual scheme with the greedy augmentation technique.