Numerous approximation algorithms for unit disk graphs have been proposed in the literature, exhibiting sharp trade-offs between running times and approximation ratios. We propose a method to obtain linear-time approx...
详细信息
ISBN:
(数字)9783319182636
ISBN:
(纸本)9783319182636;9783319182629
Numerous approximation algorithms for unit disk graphs have been proposed in the literature, exhibiting sharp trade-offs between running times and approximation ratios. We propose a method to obtain linear-time approximation algorithms for unit disk graph problems. Our method yields linear-time (4+epsilon)-approximations to the maximum-weight independent set and the minimum dominating set, bringing dramatic performance improvements when compared to previous algorithms that achieve the same approximation factors. Furthermore, we present an alternative linear-time approximation scheme for the minimum vertex cover, which could be obtained by an indirect application of our method.
作者：
Zhang, PengJiang, TaoLi, AngshengShandong Univ
Sch Comp Sci & Technol Jinan 250101 Peoples R China Univ Calif Riverside
Dept Comp Sci & Engn Riverside CA 92521 USA Tsinghua Univ
TNLIST Dept Comp Sci & Technol MOE Key Lab Bioinformat Beijing 100084 Peoples R China Tsinghua Univ
TNLIST Dept Comp Sci & Technol Bioinformat Div Beijing 100084 Peoples R China Chinese Acad Sci
Inst Software State Key Lab Comp Sci Beijing 100190 Peoples R China
The Maximum Happy Vertices (MHV) problem and the Maximum Happy Edges (MHE) problem are two fundamental problems arising in the study of the homophyly phenomenon in large scale networks. Both of these two problems are ...
详细信息
ISBN:
(纸本)9783319213989;9783319213972
The Maximum Happy Vertices (MHV) problem and the Maximum Happy Edges (MHE) problem are two fundamental problems arising in the study of the homophyly phenomenon in large scale networks. Both of these two problems are NP-hard. Interestingly, the MHE problem is a natural generalization of Multiway Uncut, the complement of the classic Multiway Cut problem. In this paper, we present new approximation algorithms for MHV and MHE based on randomized LP-rounding techniques. Specifically, we show that MHV can be approximated within 1/Delta+1, where Delta is the maximum vertex degree, and MHE can be approximated within 1/2 + root 2/4 f(k) >= 0.8535, where f(k) >= 1 is a function of the color number k. These results improve on the previous approximation ratios for MHV, MHE as well as Multiway Uncut in the literature.
In this paper we consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. We are given an undirected graph in which every edge is assigned a probability of exi...
详细信息
ISBN:
(数字)9783662483503
ISBN:
(纸本)9783662483503;9783662483497
In this paper we consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. We are given an undirected graph in which every edge is assigned a probability of existence and a positive profit, and each node is assigned a positive integer called timeout. We know whether an edge exists or not only after probing it. On this random graph we are executing a process, which one-by-one probes the edges and gradually constructs a matching. The process is constrained in two ways: once an edge is taken it cannot be removed from the matching, and the timeout of node v upper-bounds the number of edges incident to v that can be probed. The goal is to maximize the expected profit of the constructed matching. For this problem Bansal et al. [4] provided a 3-approximation algorithm for bipartite graphs, and a 4-approximation for general graphs. In this work we improve the approximation factors to 2.845 and 3.709, respectively. We also consider an online version of the bipartite case, where one side of the partition arrives node by node, and each time a node b arrives we have to decide which edges incident to b we want to probe, and in which order. Here we present a 4.07-approximation, improving on the 7.92-approximation of Bansal et al. [4]. The main technical ingredient in our result is a novel way of probing edges according to a random but non-uniform permutation. Patching this method with an algorithm that works best for large probability edges (plus some additional ideas) leads to our improved approximation factors.
A d-clique in a graph G = (V, E) is a subset S subset of V of vertices such that for pairs of vertices u, v is an element of S, the distance between u and v is at most d in G. A d-club in a graph G = (V, E) is a subse...
详细信息
ISBN:
(纸本)9783319266268;9783319266251
A d-clique in a graph G = (V, E) is a subset S subset of V of vertices such that for pairs of vertices u, v is an element of S, the distance between u and v is at most d in G. A d-club in a graph G = (V, E) is a subset S' subset of V of vertices that induces a subgraph of G of diameter at most d. Given a graph G with n vertices, the goal of Max d-Clique (Max d-Club, resp.) is to find a d-clique (d-club, resp.) of maximum cardinality in G. Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of n(1-epsilon) for any epsilon > 0 unless P = NP since they are identical to Max Clique [14,21]. Also, it is known [3] that it is NP-hard to approximate Max d-Club to within a factor of n(1/2-epsilon) for any fixed d >= 2 and for any e > 0. As for approximability of Max d-Club, there exists a polynomial-time algorithm which achieves an optimal approximation ratio of O(n(1/2)) for any even d >= 2 [3]. For any odd d >= 3, however, there still remains a gap between the O(n(2/3))-approximability and the Omega(n(1/2-epsilon))-inapproximability for Max d-Club [3]. In this paper, we first strengthen the approximability result for Max d-Club;we design a polynomial-time algorithm which achieves an optimal approximation ratio of O(n 1/2) for Max d-Club for any odd d >= 3. Then, by using the similar ideas, we show the O(n 1/2)-approximation algorithm for Max d-Clique on general graphs for any d >= 2. This is the best possible in polynomial time unless P = NP, as we can prove the Omega(n(1/2-epsilon))-inapproximability. Furthermore, we study the tractability of Max dClique and Max d-Club on subclasses of graphs.
Consider a setting where selfish agents are to be assigned to coalitions or projects from a set P. Each project k ∈ P is characterized by a valuation function;vk(S) is the value generated by a set S of agents working...
详细信息
We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset...
详细信息
We provide polynomial-time approximately optimal Bayesian mechanisms for makespan minimization on unrelated machines as well as for max-min fair allocations of indivisible goods, with approximation factors of 2 and mi...
详细信息
We consider the fundamental problem of scheduling data mules for managing a wireless sensor network. A data mule tours around a sensor network and can help with network maintenance such as data collection and battery ...
详细信息
We study problems that integrate buy-at-bulk network design into the classical (connected) facility location problem. In such problems, we need to open facilities, build a routing network, and route every client deman...
详细信息
We are given a set of items, and a set of knapsacks. Both the weight and the profit of an item are functions of the knapsack, and each knapsack has a positive real capacity. A restriction is setting that the number of...
详细信息
ISBN:
(纸本)9781479986477
We are given a set of items, and a set of knapsacks. Both the weight and the profit of an item are functions of the knapsack, and each knapsack has a positive real capacity. A restriction is setting that the number of the items which are admissible to each knapsack is no more than k, and these items are taken as input for each knapsack. We consider two following objectives: (1) maximizing the total profit of all the knapsacks (Max-Sum k-GMK), (2) maximizing the minimum profit of all the knapsacks (Max-Min k-GMK). We show that the two problems are NP-complete when k is greater than or equal to 4. For the Max-Sum k-GMK problem, we can obtain a 1/2-approximation algorithm, and especially when k=2, we design an optimal algorithm. For the Max-Min k-GMK problem, we present a 1/ (k-1)-approximation algorithm, and especially when k=2, this algorithm is an optimal algorithm.
暂无评论