We revisit the Stochastic Score Classification (SSC) problem introduced by Gkenosis et al. (ESA 2018): We are given n tests. Each test j can be conducted at cost c(j), and it succeeds independently with probability p(...
详细信息
We revisit the Stochastic Score Classification (SSC) problem introduced by Gkenosis et al. (ESA 2018): We are given n tests. Each test j can be conducted at cost c(j), and it succeeds independently with probability p(j). Further, a partition of the (integer) interval {0,. ..,n} into B smaller intervals is known. The goal is to conduct tests so as to determine that interval from the partition in which the number of successful tests lies while minimizing the expected cost. Ghuge, Gupta, and Nagarajan (IPCO 2022) recently showed that a polynomial-time constant-factor approximation algorithm exists. We show that interweaving the two strategies that order tests increasingly by their c(j)/p(j) and c j/(1- p(j)) ratios, respectively-as already proposed by Gkensosis et al. for a special case-yields a small approximation ratio. We also show that the approximation ratio can be slightly decreased from 6 to 3 + 2 root 2 approximate to 5.828 by adding in a third strategy that simply orders tests increasingly by their costs. The similar analyses for both algorithms are nontrivial but arguably clean. Finally, we complement the implied upper bound of 3 + 2 root 2 on the adaptivity gap with a lower bound of 3/2. Since the lower-bound instance is a so-called unit-cost k- of-n instance, we settle the adaptivity gap in this case.
We study the spectrum assignment (SA) problem in ring networks with shortest path (or, more generally, fixed) routing. With fixed routing, each traffic demand follows a predetermined path to its destination. In earlie...
详细信息
ISBN:
(纸本)9781479969593
We study the spectrum assignment (SA) problem in ring networks with shortest path (or, more generally, fixed) routing. With fixed routing, each traffic demand follows a predetermined path to its destination. In earlier work, we have shown that the SA problem can be viewed as a multiprocessor problem. Based on this insight, we prove that, under the shortest path assumption, the SA problem can be solved in polynomial time in small rings, and we develop constant-ratio approximation algorithms for large rings. For rings of size up to 16 nodes (the maximum size of a SONET/SDH ring), the approximation ratios of our algorithms are strictly smaller than the best known ratio to date.
In the well-studied Unsplittable Flow on a Path problem (UFP), we are given a path graph with edge capacities. Furthermore, we are given a collection of n tasks, each one characterized by a sub path, a weight, and a d...
详细信息
ISBN:
(纸本)9783319286846;9783319286839
In the well-studied Unsplittable Flow on a Path problem (UFP), we are given a path graph with edge capacities. Furthermore, we are given a collection of n tasks, each one characterized by a sub path, a weight, and a demand. Our goal is to select a maximum weight subset of tasks so that the total demand of selected tasks using each edge is upper bounded by the corresponding capacity. Chakaravarthy et al. [ESA'14] studied a generalization of UFP, bagUFP, where tasks are partitioned into bags, and we can select at most one task per bag. Intuitively, bags model jobs that can be executed at different times (with different duration, weight, and demand). They gave a 0(log n) approximation for bagUFP. This is also the best known ratio in the case of uniform weights. In this paper we achieve the following main results:
We investigate two NP-complete vertex partition problems on edge weighted complete graphs with 3k vertices. The first problem asks to partition the graph into k vertex disjoint paths of length 2 (referred to as 2-path...
详细信息
ISBN:
(纸本)9783662483503;9783662483497
We investigate two NP-complete vertex partition problems on edge weighted complete graphs with 3k vertices. The first problem asks to partition the graph into k vertex disjoint paths of length 2 (referred to as 2-paths) such that the total weight of the paths is maximized. We present a cubic time approximation algorithm that computes a 2-path partition whose total weight is at least .5833 of the weight of an optimal partition;improving upon the (.5265 - epsilon)-approximation algorithm of [26]. Restricting the input graph to have edge weights in {0, 1}, we present a .75 approximation algorithm improving upon the .55-approximation algorithm of [16]. Combining this algorithm with a previously known approximation algorithm for the 3-Set Packing problem, we obtain a .6-approximation algorithm for the problem of partitioning a {0, 1}-edge-weighted graph into k vertex disjoint triangles of maximum total weight. The best known approximation algorithm for general weights achieves an approximation ratio of .5257 [4].
In Constrained Fault-Tolerant Resource Allocation (FTRA) problem, we are given a set of sites containing facilities as resources and a set of clients accessing these resources. Each site i can open at most R-i facilit...
详细信息
ISBN:
(纸本)9783642401633
In Constrained Fault-Tolerant Resource Allocation (FTRA) problem, we are given a set of sites containing facilities as resources and a set of clients accessing these resources. Each site i can open at most R-i facilities with opening cost f(i). Each client j requires an allocation of r(j) open facilities and connecting j to any facility at site i incurs a connection cost c(ij). The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation (FTRA(infinity)) [1] and the classical Fault-Tolerant Facility Location (FTFL) [2] problems: for every site i, FTRA(infinity) does not have the constraint R-i, whereas FTFL sets R-i = 1. These problems are said to be uniform if all r(j)'s are the same, and general otherwise. For the general metric FTRA, we first give an LP-rounding algorithm achieving an approximation ratio of 4. Then we show the problem reduces to FTFL, implying the ratio of 1.7245 from [3]. For the uniform FTRA, we provide a 1.52-approximation primal-dual algorithm in O (n(4)) time, where n is the total number of sites and clients. (C) 2015 Elsevier B.V. All rights reserved.
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
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...
详细信息
暂无评论