We present improved approximation algorithms in stochastic optimization. We prove that the multi-stage stochastic versions of covering integer programs (such as set cover and vertex cover) admit essentially the same a...
详细信息
ISBN:
(纸本)9780898716245
We present improved approximation algorithms in stochastic optimization. We prove that the multi-stage stochastic versions of covering integer programs (such as set cover and vertex cover) admit essentially the same approximation algorithms as their standard (non-stochastic) counterparts;this improves upon work of Swamy & Shmoys that shows an approximability which depends multiplicatively on the number of stages. We also present approximation algorithms for facility location and some of its variants in the 2-stage recourse model, improving on previous approximation guarantees.
A number of recent papers on approximation algorithms have used the square roots of unity, -1 and 1, to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit ve...
详细信息
ISBN:
(纸本)9781581133493
A number of recent papers on approximation algorithms have used the square roots of unity, -1 and 1, to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimum solutions to these problems. In this paper, we consider using the cube roots of unity, 1, e(i2pi/3), and e(i4pi/3), to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in Goemans and Williamson (J. ACM 42 (1995) 1115-1145) to obtain near-optimum solutions to the problems. In particular, we consider the problem of maximizing the total weight of satisfied equations x(u) - x(v) drop c (mod 3) and inequations x - x(v) not equivalent to c (mod 3), where x(u) epsilon {0, 1, 2} for all u. This problem can be used to model the MAx-3-CUT problem and a directed variant we call MAX-3-DICUT. For the general problem, we obtain a 0.793733-approximation algorithm. If the instance contains only inequations (as it does for MAX-3-CUT), we obtain a performance guarantee of (7)/(12) + (3)/(4pi2) arccos(2)(- 1/4) - epsilon>0.836008. This compares with proven performance guarantees of 0.800217 for MAX-3-CUT (by Frieze and Jerrum (Algorithmica 18 (1997) 67-81) and 1 + 10(-8) for the general problem (by Andersson et al. (J. algorithms 3 39 (2001) 162-204)). It matches the guarantee of 0.836008 for MAX-3-CUT found independently by de Klerk et al. (On approximate graph colouring and Max-k-Cut algorithms based on the 9-function, Manuscript, October 2000). We show that all these algorithms are in fact equivalent in the case of MAX-3CUT, and that our algorithm is the same as that of Andersson et al. in the more gener
We present an approximation algorithm that takes a pool of pre-trained models as input and produces from it a cascaded model with similar accuracy but lower average-case cost. Applied to state-of-the-art ImageNet clas...
详细信息
ISBN:
(纸本)9781510867963
We present an approximation algorithm that takes a pool of pre-trained models as input and produces from it a cascaded model with similar accuracy but lower average-case cost. Applied to state-of-the-art ImageNet classification models, this yields up to a 2x reduction in floating point multiplications, and up to a 6x reduction in average-case memory I/O. The auto-generated cascades exhibit intuitive properties, such as using lower-resolution input for easier images and requiring higher prediction confidence when using a computationally cheaper model.
We give a randomized fixed parameter tractable algorithm to approximately count the number of copies of a k-vertex graph with bounded treewidth in an n vertex graph. As a consequence, we get randomized algorithms with...
详细信息
ISBN:
(纸本)3540001425
We give a randomized fixed parameter tractable algorithm to approximately count the number of copies of a k-vertex graph with bounded treewidth in an n vertex graph. As a consequence, we get randomized algorithms with running time k(O(k))n(O(1)), approximation ratio 1/k(O(k)), and error probability 2(-nO(1)) for (a) approximately counting the number of matchings of size k in an n vertex graph and (b) approximately counting the number of paths of length k in an n vertex graph. Our algorithm is based on the Karp-Luby approximate counting technique [8] applied to fixed parameter tractable problems, and the color-coding technique of Alon, Yuster and Zwick [1]. We also show some W-hardness results for parameterized exact counting problems.
Cellular networks are generally modeled as node-weighted graphs, where the nodes represent cells and the edges represent the possibility of radio interference. An algorithm for the channel assignment problem must assi...
详细信息
ISBN:
(纸本)3540669167
Cellular networks are generally modeled as node-weighted graphs, where the nodes represent cells and the edges represent the possibility of radio interference. An algorithm for the channel assignment problem must assign as many channels as the weight indicates to every node, such that any two channels assigned to the same node satisfy the co-site constraint, and any two channels assigned to adjacent nodes satisfy the inter-site constraint. We describe several approximation algorithms for channel assignment with arbitrary co-site and inter-site constraints and reuse distance 2 for odd cycles and so-called hexagon graphs that are often used to model cellular networks. The algorithms given for odd cycles are optimal for some values of constraints, and have performance ratio at most 1+1/(n-1) for all other cases, where n is the length of the cycle. Our main result is an algorithm of performance ratio at most 4/3+epsilon for hexagon graphs with arbitrary co-site and inter-site constraints.
In the classical facility location problem we are given a set of facilities, with associated opening costs, and a set of clients. The goal is to open a subset of facilities, and to connect each client to the closest o...
详细信息
ISBN:
(纸本)9783642208072
In the classical facility location problem we are given a set of facilities, with associated opening costs, and a set of clients. The goal is to open a subset of facilities, and to connect each client to the closest open facility, so that the total connection and opening cost is minimized. In some applications, however, open facilities need to be connected via an infrastructure. Furthermore, connecting two facilities among them is typically more expensive than connecting a client to a facility (for a given path length). This scenario motivated the study of the connected facility location problem (CFL). Here we are also given a parameter M >= 1. A feasible solution consists of a subset of open facilities and a Steiner tree connecting them. The cost of the solution is now the opening cost, plus the connection cost, plus M times the cost of the Steiner tree. In this paper we investigate the approximability of CFL and related problems. More precisely, we achieve the following results: We present a new, simple 3.19 approximation algorithm for CFL. The previous best approximation factor is 3.92 [Eisenbrand, Grandoni, RothvoB, Schafer-'10]. We show that SROB, i.e. the special case of CFL where all opening costs are 0, is hard to approximate within 1.28. The previous best lower bound for SROB is 1.01, and derives trivially from Steiner tree inapproximability [Chlebik, Chlebikova-'08]. The same inapproximability result extends to other well-studied problems, such as virtual private network and single-sink buy-at-bulk. We introduce and study a natural multi-commodity generalization MCFL of CFL. In MCFL we are given source-sink pairs (rather than clients) that we wish to connect. A feasible solution consists of a subset of open facilities, and a forest (rather than a tree) spanning them. Source-sink connection paths can use several trees in the forest, but must enter and leave each tree at open facilities. We present the first constant approximation for MCFL.
Many data dissemination and publish-subscribe systems that guarantee the privacy and authenticity of the participants rely on symmetric key cryptography. An important problem in such a system is to maintain the shared...
详细信息
ISBN:
(纸本)9783642028816
Many data dissemination and publish-subscribe systems that guarantee the privacy and authenticity of the participants rely on symmetric key cryptography. An important problem in such a system is to maintain the shared group key as the group membership changes. We consider the problem of determining a key hierarchy that minimizes the average communication cost of an update, given update frequencies of the group members and an edge-weighted undirected graph that captures routing costs. We first present a polynomial-time approximation scheme for minimizing the average number of multicast messages needed for an update. We next show that when routing costs are considered, the problem is NP-hard even when the underlying routing network is a tree network or even when every group member has the same update frequency. Our main result is a polynomial time constant-factor approximation algorithm for the general case where the routing network is an arbitrary weighted graph and group members have nonuniform update frequencies.
We consider a variant of the classic multi-armed bandit problem (MAB), which we call FEEDBACK MAB, where the reward obtained by playing each of n independent arms varies according to an underlying on/off Markov proces...
详细信息
ISBN:
(纸本)9780769530109
We consider a variant of the classic multi-armed bandit problem (MAB), which we call FEEDBACK MAB, where the reward obtained by playing each of n independent arms varies according to an underlying on/off Markov process with known parameters. The evolution of the Markov chain happens irrespective of whether the arm is played, and furthermore, the exact state of the Markov chain is only revealed to the player when the arm is played and the reward observed. At most one arm (or in general, M arms) can be played any time step. The goal is to design a policy for playing the arms in order to maximize the infinite horizon time average expected reward. This problem is an instance of a Partially Observable Markov Decision Process (POMDP), and a special case of the notoriously intractable "restless bandit" problem. Unlike the stochastic MAB problem, the FEEDBACK MAB problem does not admit to greedy index-based optimal policies. The state of the system at any time step encodes the beliefs about the states of different arms, and the policy decisions change these beliefs - this aspect complicates the design and analysis of simple algorithms. We design a constant factor approximation to the FEEDBACK MAB problem by solving and rounding a natural LP relaxation to this problem. As far as we are aware, this is the first approximation algorithm for a POMDP problem.
The mixed postman problem, a generalization of the Chinese postman problem, is that of finding a shortest tour that traverses each edge of a given mixed graph (a graph containing both undirected and directed edges) at...
详细信息
ISBN:
(纸本)354064590X
The mixed postman problem, a generalization of the Chinese postman problem, is that of finding a shortest tour that traverses each edge of a given mixed graph (a graph containing both undirected and directed edges) at least once. The problem is solvable in polynomial time either if the graph is undirected or if the graph is directed, but NP-hard in mixed graphs. An approximation algorithm with a performance ratio of 3/2 for the postman problem on mixed graphs is presented.
Polynomial time approximation algorithms are proposed with constant approximation factors for a problem of computing the smallest cardinality set of identical disks whose union intersects each segment from a given set...
详细信息
ISBN:
(纸本)9783030226299;9783030226282
Polynomial time approximation algorithms are proposed with constant approximation factors for a problem of computing the smallest cardinality set of identical disks whose union intersects each segment from a given set E of n straight line segments on the plane. This problem has important applications in operations research, namely in wireless and road network analysis. It is equivalent to finding the least cardinality piercing (or hitting) set for the corresponding family of n Euclidean r-neighborhoods of straight line segments of E on the plane, which are called r-hippodromes in the literature. When the number of distinct orientations is upper bounded by k of segments from E, a simple O(n log n)-time 4k-approximate algorithm is known for this problem. Besides, when E contains arbitrary straight line segments, overlapping at most at their endpoints, O(n(4) log n)-time 100-approximate algorithm is given recently. In the present paper, simple approximation algorithms are proposed with small approximation factors for E, being edge set of some special plane graphs of interest in road network applications;here the number of distinct orientations of straight line segments from E can be arbitrarily large. More precisely, O(n(2))-time approximation algorithms are constructed for edge sets of either Gabriel or relative neighborhood graphs or of Euclidean minimum spanning trees with factors of 14, 12 and 10 respectively. These algorithms are much faster, more accurate and conceptually much simpler than the aforementioned 100-approximate algorithm for the general case of the problem on edge sets of arbitrary plane graphs.
暂无评论