The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper we consider the geometric version of the problem, where all points in a Euclidean space are candidates for ...
详细信息
ISBN:
(纸本)9783642033667
The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper we consider the geometric version of the problem, where all points in a Euclidean space are candidates for network nodes. We present the first general approach for geometric versions of basic variants of the buy-at-bulk network design problem. It enables us to obtain quasi-polynomial-time approximation schemes for basic variants of the buy-at-bulk geometric network design problem with polynomial total demand. Then, for instances with few sinks and low capacity links, we design very fast polynomial-time low-constant approximations algorithms.
We study the following generalization of the maximum matching problem in general graphs: Given a simple non-directed graph G = (V, E) and a partition of the edges into k classes (i.e. E = E-1 boolean OR ... boolean OR...
详细信息
ISBN:
(纸本)9783662444658;9783662444641
We study the following generalization of the maximum matching problem in general graphs: Given a simple non-directed graph G = (V, E) and a partition of the edges into k classes (i.e. E = E-1 boolean OR ... boolean OR E-k), we would like to compute a matching M on G of maximum cardinality or profit, such that vertical bar M boolean AND E-j vertical bar <= w(j) for every class E-j. Such problems were first studied in the context of network design in [17]. We study the problem from a linear programming point of view: We provide a polynomial time 1/2-approximation algorithm for the weighted case, matching the integrality gap of the natural LP formulation of the problem. For this, we use and adapt the technique of approximate convex decompositions [19] together with a different analysis and a polyhedral characterization of the natural linear program to derive our result. This improves over the existing 1/2, but with additive violation of the color bounds, approximation algorithm [14].
The Flexible Job Shop Problem is a generalization of the classical job shop scheduling problem in which for every operation there is a group of machines that can process it. The problem is to assign operations to mach...
详细信息
ISBN:
(纸本)3540673067
The Flexible Job Shop Problem is a generalization of the classical job shop scheduling problem in which for every operation there is a group of machines that can process it. The problem is to assign operations to machines and to order the operations on the machines, so that the operations can be processed in the smallest amount of time. We present a linear time approximation scheme for the non-preemptive version of the problem when the number m of machines and the maximum number mu Of operations per job are fixed. We also study the preemptive version of the problem when m and mu are fixed, and present a linear time (2 + epsilon)-approximation algorithm for the problem with migration.
The UNIQUE GAMES problem is a central problem in algorithms and complexity theory. Given an instance of UNIQUE GAMES, the STRONG UNIQUE GAMES problem asks to find the largest subset of vertices, such that the UNIQUE G...
详细信息
ISBN:
(纸本)9781611976465
The UNIQUE GAMES problem is a central problem in algorithms and complexity theory. Given an instance of UNIQUE GAMES, the STRONG UNIQUE GAMES problem asks to find the largest subset of vertices, such that the UNIQUE GAMES instance induced on them is completely satisfiable. In this work, we give new algorithmic and hardness results for the STRONG UNIQUE GAMES problem. Given an instance with label set size k where a set of 1-epsilon fraction of the vertices induce an instance that is completely satisfiable, our first algorithm produces a set of 1 - (O) over tilde (k(2)) epsilon root log n fraction of the vertices such that the UNIQUE GAMES induced on them is completely satisfiable. In the same setting, our second algorithm produces a set of 1 - (O) over tilde (k(2)) root epsilon log d (here d is the largest vertex degree of the graph) fraction of the vertices such that the UNIQUE GAMES induced on them is completely satisfiable. The technical core of our results is a new connection between STRONG UNIQUE GAMES and small-set vertex-expansion in graphs. Complementing this, assuming the Unique Games conjecture, we prove that there exists an absolute constant C such that it is NP-hard to compute a set of size larger than 1-C root epsilon log k log d such that all the constraints induced on this set are satisfied. Given an undirected graph G (V, E) the ODD CYCLE TRANSVERSAL problem, asks to delete the least fraction of vertices to make the induced graph on the remaining vertices bipartite. As a corollary to our main algorithmic results, we obtain an algorithm that outputs a set S such the graph induced on V n S is bipartite, and vertical bar S vertical bar/n <= O root epsilon log d (here d is the largest vertex degree and # is the optimal fraction of vertices that need to be deleted). Assuming the Unique Games conjecture, we prove a matching (up to constant factors) hardness.
We study the problem of scheduling n independent jobs on a system of m identical parallel machines in the presence of reservations. This constraint is practically important;for various reasons, some machines are not a...
详细信息
ISBN:
(纸本)9783540772194
We study the problem of scheduling n independent jobs on a system of m identical parallel machines in the presence of reservations. This constraint is practically important;for various reasons, some machines are not available during specified time intervals. The objective is to minimize the makespan. This problem is inapproximable in the general case unless P = NP which motivates the study of suitable restrictions. We use an approach based on algorithms for multiple subset sum problems;our technique yields a polynomial time approximation scheme (PTAS) which is best possible in the sense that the problem does not admit an FPTAS unless P = NP. The PTAS presented here is the first one for the problem under consideration;so far, not even for special cases approximation schemes have been proposed. We also derive a low cost algorithm with a constant approximation ratio and discuss additional FPTASes for special cases and complexity results.
Inspired by air traffic control and other applications where moving objects have to be labeled, we consider the following (static) point labeling problem: given a set P of n points in the plane and labels that are uni...
详细信息
ISBN:
(纸本)9783642137303
Inspired by air traffic control and other applications where moving objects have to be labeled, we consider the following (static) point labeling problem: given a set P of n points in the plane and labels that are unit squares, place a label with each point;in P in such a way that the number of free labels (labels not intersecting any other label) is maximized. We develop efficient constant-factor approximation algorithms for this problem, as well as PTASs, for various label-placement models.
Several recently-proposed data compression algorithms are based on the idea of representing a string by a context-free grammar. Most of these algorithms are known to be asymptotically optimal with respect to a station...
详细信息
ISBN:
(纸本)089871513X
Several recently-proposed data compression algorithms are based on the idea of representing a string by a context-free grammar. Most of these algorithms are known to be asymptotically optimal with respect to a stationary ergodic source and to achieve a low redundancy rate. However, such results do not reveal how effectively these algorithms exploit the grammar-model itself;that is, are the compressed strings produced as small as possible? We address this issue by analyzing the approximation ratio of several algorithms, that is, the maximum ratio between the size of the generated grammar and the smallest possible grammar over all inputs. On the negative side, we show that every polynomial-time grammar-compression algorithm has approximation ratio at least 8569/8568 unless P = NP. Moreover, achieving an approximation ratio of o(log n/ log log n) would require progress on an algebraic problem in a well-studied area. We then upper and lower bound approximation ratios for the following four previously-proposed gram-mar-based compression algorithms: SEQUENTIAL, BISECTION, GREEDY, and LZ78, each of which employs a distinct approach to compression. These results seem to indicate that there is much room to improve grammar-based compression algorithms.
Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmi...
详细信息
ISBN:
(纸本)9781424435128
Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmissions from its neighbors makes it non-trivial to design a minimum-latency broadcast algorithm, which is known to be NP-complete. We present a simple 12-approximation algorithm for the one-to-all broadcast problem that improves all previously known guarantees for this problem. We then consider the all-to-all broadcast problem where each node sends its own message to all other nodes. For the all-to-all broadcast problem, we present two algorithms with approximation ratios of 20 and 34, improving the best result available in the literature. Finally, we report experimental evaluation of our algorithms. Our studies indicate that our algorithms perform much better in practice than the worst-case guarantees provided in the theoretical analysis and achieve up to 37% performance improvement over existing schemes.
In this paper, we consider a variant of knapsack problem. There are two knapsacks with probably different capacities, owned by two agents respectively. Given a set of items, each with a fixed size and a profit, the tw...
详细信息
ISBN:
(纸本)9783642226151
In this paper, we consider a variant of knapsack problem. There are two knapsacks with probably different capacities, owned by two agents respectively. Given a set of items, each with a fixed size and a profit, the two agents select items and pack them into their own knapsacks under the capacity constraint. Same items can be packed simultaneously to different knapsacks. However, in this case the profit of such items can vary. One agent packs items into his knapsack to maximize the total profit, while another agent can only pack items into his knapsack as well but he cares the total profits of items packed into two knapsacks. The latter agent is a leader while the former is a follower. We aim at designing an approximation algorithm for the leader assuming that the follower is selfish. For different settings we provide approximation results.
We present an approximation algorithm for the Max 3-section problem which divides a weighted graph into 3 parts of equal size so as to maximize the weight of the edges connecting different parts. The algorithm is base...
详细信息
ISBN:
(纸本)9783642020254
We present an approximation algorithm for the Max 3-section problem which divides a weighted graph into 3 parts of equal size so as to maximize the weight of the edges connecting different parts. The algorithm is based on a complex semidefinite programming and can in some sense be viewed as a generalization of the approximation algorithm proposed by Ye [17] for the Max Bisection problem. Our algorithm can hit the 2/3 bound and has approximate ratio 0.6733 for Max 3-section that sightly improves the 2/3 bound obtained by Andersson [1] and Gaur [8], respectively.
暂无评论