We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Williamson et ...
详细信息
We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Williamson et al. in Combinatorica 15(3):435-454, 1995. https://***/10.1007/BF01299747). Williamson et al. prove an approximation ratio of two for connectivity augmentation problems where the connectivity requirements can be specified by uncrossable functions. They state: "Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar. A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems." Our main result proves that the primal-dual algorithm of Williamson et al. achieves an approximation ratio of 16 for a class of functions that generalizes the notion of an uncrossable function. There exist instances that can be handled by our methods where none of the optimal dual solutions has a laminar support. We present three applications of our main result to problems in the area of network design. (1) A 16-approximation algorithm for augmenting a family of small cuts of a graph G. The previous best approximation ratio was O(log |V(G)|). (2) A 16 center dot (sic)k/u(min)(sic)-approximation algorithm for the Cap-k-ECSS problem which is as follows: Given an undirected graph G = (V, E) with edge costs c is an element of Q(>= 0)(E) and edge capacities u is an element of Z(>= 0)(E), find a minimum-cost subset of the edges F subset of E such that the capacity of any cut in (V, F) is at least k;u(min) (respectively, u(max)) denotes the minimum (respectively, maximum) capacity of an edge in E, and w.l.o.g. u(max) <= k. The previous best approximation ratio was min(O(log |V|), k, 2u(max)). (3) A 20-approximation algorithm for the model o
We consider a new dynamic edge covering and scheduling problem that focuses on assigning resources to nodes in a network to minimize the amount of time required to process all edges in it. Resources need to be co-loca...
详细信息
We consider a new dynamic edge covering and scheduling problem that focuses on assigning resources to nodes in a network to minimize the amount of time required to process all edges in it. Resources need to be co-located at the endpoints of an edge for it to be processed and, therefore, this problem contains both edge covering and scheduling decisions. These new problems have motivating applications in traffic systems and military intelligence operations. We provide complexity results for the dynamic edge covering and scheduling problem over different types of networks. We then show that existing approximation algorithms for parallel machine scheduling problems can be leveraged to provide approximation algorithms for this new class of problems over certain types of networks.
We consider a well-studied multi-echelon (deterministic) inventory control problem, known in the literature as the one-warehouse multi-retailer (OWMR) problem. We propose a simple and fast 2-approximation algorithm fo...
详细信息
We consider a well-studied multi-echelon (deterministic) inventory control problem, known in the literature as the one-warehouse multi-retailer (OWMR) problem. We propose a simple and fast 2-approximation algorithm for this NP-hard problem, by recombining the solutions of single-echelon relaxations at the warehouse and at the retailers. We then show that our approach remains valid under quite general assumptions on the cost structures and under capacity constraints at some retailers. In particular, we present the first approximation algorithms for the OWMR problem with nonlinear holding costs, truckload discount on procurement costs, or with capacity constraints at some retailers. In all cases, the procedure is purely combinatorial and can be implemented to run in low polynomial time.
In this paper, we investigate two spanning tree problems of graphs with k given sources. Let G = (V, E,w) be an undirected graph with nonnegative edge lengths and S ⊂ V a set of k specified sources. The first problem ...
详细信息
In this paper we study the subset-sum problem (SSP), which is the problem of finding, given a set of n positive integers and a knapsack of capacity c, a subset the sum of which is closest to c without exceeding the va...
详细信息
In this paper we study the subset-sum problem (SSP), which is the problem of finding, given a set of n positive integers and a knapsack of capacity c, a subset the sum of which is closest to c without exceeding the value c. A short algorithm with worst-case guarantee 3/4 is introduced which outperforms Martello and Toth's 3/4 algorithm requiring a complexity time of O(n) instead of O(n(2)). The second linear time algorithm reaches a 4/5 worst-case performance ratio. Both bounds are shown to be tight. Computational results on randomly generated and deterministic test problems are reported. (C) 2000 Published by Elsevier Science B.V. All rights reserved.
In the job shop scheduling problem, there are m machines and n jobs. A job consists of a sequence of operations, each of which must be processed on a specified machine, and the aim is to complete all jobs as quickly a...
详细信息
In the job shop scheduling problem, there are m machines and n jobs. A job consists of a sequence of operations, each of which must be processed on a specified machine, and the aim is to complete all jobs as quickly as possible. This problem is strongly VP-hard even for very restrictive special cases. The authors give the first randomized and deterministic polynomial-time algorithms that yield polylogarithmic approximations to the optimal length schedule. These algorithms also extend to the more general case where a job is given not by a linear ordering of the machines on which it must be processed but by an arbitrary partial order. Comparable bounds can also be obtained when there are m' types of machines, a specified number of machines of each type, and each operation must be processed on one of the machines of a specified type, as well as for the problem of scheduling unrelated parallel machines subject to chain precedence constraints.
Adaptive-modulation transceivers have been widely used in wireless communications nowadays. The tradeoff between symbol error rate and data rate can be tuned by adjusting the constellation size. In this paper, we prop...
详细信息
Adaptive-modulation transceivers have been widely used in wireless communications nowadays. The tradeoff between symbol error rate and data rate can be tuned by adjusting the constellation size. In this paper, we propose a constellation subset selection (CSS) approach and design the novel efficient approximation algorithms to tackle the CSS problems. The approximation ratios for these algorithms are derived. The theoretical studies on how to control the target symbol error rate by selecting an appropriate parameter K are also presented. Monte Carlo simulation results show that our CSS scheme really can reach below the target error probability.
We consider a transmission scheduling problem in which multiple agents receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the pr...
详细信息
We consider a transmission scheduling problem in which multiple agents receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall Age of Information (AoI). We call this problem the Min-AoI problem. Several special cases of the problem are known to be solvable in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant r >= 1, every r-approximation algorithm for the Min-WCS problem can be transformed into an r-approximation algorithm for the Min-AoI problem. Second, we give a randomized 2.619-approximation algorithm, a randomized 3-approximation algorithm, which outperforms the previous one in certain scenarios, and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-AoI problem is NP-hard.
The index coding problem is concerned with broadcasting encoded information to a collection of receivers in a way that enables each receiver to discover its required data based on its side information, which comprises...
详细信息
The index coding problem is concerned with broadcasting encoded information to a collection of receivers in a way that enables each receiver to discover its required data based on its side information, which comprises the data required by some of the others. Given the side information map, represented by a graph in the symmetric case and by a digraph otherwise, the goal is to devise a coding scheme of minimum broadcast length. We present a general method for developing efficient algorithms for approximating the index coding rate for prescribed families of instances. As applications, we obtain polynomial-time algorithms that approximate the index coding rate of graphs and digraphs on n vertices to within factors of O(n/log(2)n) and O(n/log n) respectively. This improves on the approximation factors of O(n/log n) for graphs and O(n & sdot;log log n/log n) for digraphs achieved by Blasiak, Kleinberg, and Lubetzky. For the family of quasi-line graphs, we exhibit a polynomial-time algorithm that approximates the index coding rate to within a factor of 2. This improves on the approximation factor of O(n(2/3)) achieved by Arbabjolfaei and Kim for graphs on n vertices taken from certain sub-families of quasi-line graphs. Our approach is applicable for approximating a variety of additional graph and digraph quantities to within the same approximation factors. Specifically, it captures every graph quantity sandwiched between the independence number and the clique cover number and every digraph quantity sandwiched between the maximum size of an acyclic induced sub-digraph and the directed clique cover number.
We introduce a new two-side approximation method for the channel scheduling problem, which controls the accuracy of approximation in two sides by a pair of parameters (f, g). We present a series of simple and practica...
详细信息
We introduce a new two-side approximation method for the channel scheduling problem, which controls the accuracy of approximation in two sides by a pair of parameters (f, g). We present a series of simple and practical-for-implementation greedy algorithms which give constant factor approximation in both sides. First, we propose four approximation algorithms for the weighted channel allocation problem: 1. a greedy algorithm for the multichannel with fixed interference radius scheduling problem is proposed and an one side O(1)-IS-approximation is obtained;2. a greedy (O(1), O(1))-approximation algorithm for single channel with fixed interference radius scheduling problem is presented;3. we improve the existing algorithm for the multichannel scheduling and show an vertical bar E vertical bar(O(d/epsilon)) time (1 - epsilon)-approximation algorithm;4. we speed up the polynomial time approximation scheme for single-channel scheduling through merging two algorithms and show a (1 - epsilon, O(1))-approximation algorithm. Next, we study two polynomial time constant factor greedy approximation algorithms for the unweighted channel allocation with variate interference radius. A greedy O(1)-approximation algorithm for the multichannel scheduling problem and an (O(1), O(1))-approximation algorithm for single-channel scheduling problem are developed. At last, we do some experiments to verify the effectiveness of our proposed methods.
暂无评论