We discuss two approximation paradigms that were used to construct many approximationalgorithms during the last two decades, the primal-dual schema and the local ratio technique. Recently, primal-dual algorithms were...
详细信息
We discuss two approximation paradigms that were used to construct many approximationalgorithms during the last two decades, the primal-dual schema and the local ratio technique. Recently, primal-dual algorithms were devised by first constructing a local ratio algorithm and then transforming it into a primal-dual algorithm. this was done in the case of the 2-approximationalgorithms for the feedback vertex set problem and in the case of the first primal-dual algorithms for maximization problems. Subsequently, the nature of the connection between the two paradigms was posed as an open question by Williamson [ Math. Program., 91 ( 2002), pp. 447 - 478]. In this paper we answer this question by showing that the two paradigms are equivalent.
In an online k-server routing problem, a crew of k servers has to visit points in a metric space as they arrive in real time. Possible objective functions include minimizing the makespan (k-Traveling Salesman Problem)...
详细信息
In an online k-server routing problem, a crew of k servers has to visit points in a metric space as they arrive in real time. Possible objective functions include minimizing the makespan (k-Traveling Salesman Problem) and minimizing the sum of completion times (k-Traveling Repairman Problem). We give competitive algorithms, resource augmentation results and lower bounds for k-server routing problems in a wide class of metric spaces. In some cases the competitive ratio is dramatically better than that of the corresponding single server problem. Namely, we give a 1+O((log k)/k)-competitive algorithm for the k-Traveling Salesman Problem and the k-Traveling Repairman Problem when the underlying metric space is the real line. We also prove that a similar result cannot hold for the Euclidean plane.
We consider the following network design problem;Given a vertex set V with a metric cost c on V, an integer ka parts per thousand yen1, and a degree specification b, find a minimum cost k-edge-connected multigraph on ...
详细信息
We consider the following network design problem;Given a vertex set V with a metric cost c on V, an integer ka parts per thousand yen1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex vaV is equal to b(v). this problem generalizes metric TSP. In this paper, we show that the problem admits a rho-approximation algorithm if b(v)a parts per thousand yen2, vaV, where rho=2.5 if k is even, and rho=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.
We give first constant-factor approximations for various cases of the coupled-task single machine and two-machine flow shop scheduling problems with exact delays and makespan as the objective function. In particular, ...
详细信息
ISBN:
(纸本)9783540695134
We give first constant-factor approximations for various cases of the coupled-task single machine and two-machine flow shop scheduling problems with exact delays and makespan as the objective function. In particular, we design 3.5- and 3-approximationalgorithms for the general cases of the single-machine and the two-machine problems, respectively. We also prove that the existence of a (2 - epsilon)-approximation algorithm for the single-machine problem as well as the existence of a (1.5 - epsilon)-approximation algorithm for the two-machine problem implies P = NP. the inapproximability results are valid for the cases when the operations of each job have equal processing times and for these cases the approximation ratios achieved by. our algorithms are very close to best possible: we prove that the single machine problem is approximable within a factor of 2.5 and the two-machine problem is approximable within a factor of 2.
Completely automated electronic securities exchanges and algorithms for trading in these exchanges have become very important for modern finance. In [4], Kakade el al. introduced the limit order market model, which is...
详细信息
ISBN:
(纸本)9783540921844
Completely automated electronic securities exchanges and algorithms for trading in these exchanges have become very important for modern finance. In [4], Kakade el al. introduced the limit order market model, which is a prevalent paradigm in electronic markets. In this paper, we consider bothonline and offline algorithms for maximizing revenue when selling in limit order markets. We first prove that the standard reservation price algorithm has an optimal competitive ratio for this problem. this ratio is not constant, and so we consider computing solutions offline. We show that the offline optimization problem is NP-hard, even for very restricted instances. We complement the hardness result by presenting an approximation scheme that runs in polynomial time for a wide class of instances.
We present several efficient online and offline strategies for assigning periodic tasks to the nodes of a distributed system, such that the tasks can be feasibly scheduled by the node using some local static/dynamic p...
详细信息
In this paper, we study online multidimensional bin packing problem when all items are hypercubes. Based on the techniques in one dimensional bin packing algorithm Super Harmonic by Seiden, we give a framework for onl...
详细信息
ISBN:
(纸本)9783540695134
In this paper, we study online multidimensional bin packing problem when all items are hypercubes. Based on the techniques in one dimensional bin packing algorithm Super Harmonic by Seiden, we give a framework for online hypercube packing problem and obtain new upper bounds of asymptotic competitive ratios. For square packing, we get an upper bound of 2.1439, which is better than 2.24437. For cube packing, we also give a new upper bound 2.6852 which is better than 2.9421 by Epstein and van Stee.
Given is an element of, for N sufficiently large, we give a metric on N points which cannot be isometrically embedded in l(infinity)(b) for b < N N-is an element of.
ISBN:
(纸本)3540424709
Given is an element of, for N sufficiently large, we give a metric on N points which cannot be isometrically embedded in l(infinity)(b) for b < N N-is an element of.
We study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. the flow of each commodity can be split on several paths. Arcs are equipped with load dependent price f...
详细信息
We study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. the flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm showing that for affine price functions this algorithm is 4K(2)/(1+K)(2) -competitive, where K is the number of commodities. For networks with two nodes and parallel arcs, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. We then investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. the variant of the greedy algorithm that produces unsplittable flows is (3 + 2 root 2)-competitive, and we prove a lower bound of 2 for the competitive ratio of any deterministic online algorithm.
We analyze the simple greedy algorithm that iteratively removes the endpoints of a maximum-degree edge in a graph, where the degree of an edge is the sum of the degrees of its endpoints. this algorithm provides a 2-ap...
详细信息
ISBN:
(纸本)9783540695134
We analyze the simple greedy algorithm that iteratively removes the endpoints of a maximum-degree edge in a graph, where the degree of an edge is the sum of the degrees of its endpoints. this algorithm provides a 2-approximation to the minimum edge dominating set and minimum maximal matching problems. We refine its analysis and give an expression of the approximation ratio that is strictly less than 2 in the cases where the input graph has n vertices and at least epsilon((n)(2)) edges, 2 for epsilon > 1/2. this ratio is shown to be asymptotically tight for epsilon > 1/2.
暂无评论