A 3.8165-competitive 2-space bounded 2-dimensional bin packing algorithm is described. Moreover, a 3.6-competitive online square packing algorithm with two active bins is presented.
A 3.8165-competitive 2-space bounded 2-dimensional bin packing algorithm is described. Moreover, a 3.6-competitive online square packing algorithm with two active bins is presented.
We consider the following problem of scheduling with conflicts (SWC): Find a minimum makespan schedule on identical machines where conflicting jobs cannot be scheduled concurrently. We study the problem when conflicts...
详细信息
We consider the following problem of scheduling with conflicts (SWC): Find a minimum makespan schedule on identical machines where conflicting jobs cannot be scheduled concurrently. We study the problem when conflicts between jobs are modeled by general graphs. Our first main positive result is an exact algorithm for two machines and job sizes in {1, 2}. For jobs sizes in {1, 2, 3}, we can obtain a 4/3-approximation, which improves on the 3 2 approximation that was previously known for this case. Our main negative result is that for jobs sizes in {1, 2, 3, 4}, the problem is APX-hard. Our second contribution is the initiation of the study of an online model for SWC, where we present the first results in this model. Specifically, we prove a lower bound of 2-1/m on the competitive ratio of any deterministic online algorithm for m machines and unit jobs, and an upper bound of 2 when the algorithm is not restricted computationally. For three machines we can show that an efficient greedy algorithm achieves this bound. For two machines we present a more complex algorithm that achieves a competitive ratio of 2-1/7 when the number of jobs is known in advance to the algorithm.
The time-dependent traveling salesman problem (TDTSP) is a variant of TSP with time-dependent edge costs. We study some restrictions of TDTSP where the number of edge cost changes are limited. We find competitive rati...
详细信息
The time-dependent traveling salesman problem (TDTSP) is a variant of TSP with time-dependent edge costs. We study some restrictions of TDTSP where the number of edge cost changes are limited. We find competitive ratios for online versions of TDTSP. From these we derive polynomial time approximation algorithms for graphs with edge costs one and two. In addition, we present an approximation algorithm for the orienteering problem with edge costs one and two.
The problem of online checkpointing is a classical problem with numerous applications that has been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memor...
详细信息
The problem of online checkpointing is a classical problem with numerous applications that has been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. Bringmann, Doerr, Neumann, and Sliacan studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59 - o(1) for all k and smaller than ln 4 - o(1) approximate to 1.39 for the sparse subset of k's, which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k. In this article, we solve the main problems left open in the above-mentioned paper by proving that ln 4 is a tight upper and lower bound on the asymptotic discrepancy for all large k and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k <= 10. In the last part of the article, we describe some new applications of this online checkpointing problem.
We study online scheduling problems on a single processor that can be viewed as extensions of the well-studied problem of minimizing total weighted flow time. In particular, we provide a framework of analysis that is ...
详细信息
We study online scheduling problems on a single processor that can be viewed as extensions of the well-studied problem of minimizing total weighted flow time. In particular, we provide a framework of analysis that is derived by duality properties, does not rely on potential functions and is applicable to a variety of scheduling problems. A key ingredient in our approach is bypassing the need for "black-box" rounding of fractional solutions, which yields improved competitive ratios. We begin with an interpretation of Highest-Density-First (HDF) as a primal-dual algorithm, and a corresponding proof that HDF is optimal for total fractional weighted flow time (and thus scalable for the integral objective). Building upon the salient ideas of the proof, we show how to apply and extend this analysis to the more general problem of minimizing n-ary sumation is the flow time and g is a non-decreasing cost function. Among other results, we present improved competitive ratios for the setting in which g is a concave function, and the setting of same-density jobs but general cost functions. We further apply our framework of analysis to online weighted completion time with general cost functions as well as scheduling under polyhedral constraints.
online graph problems are considered in models where the irrevocability requirement is relaxed. We consider the Late Accept model, where a request can be accepted at a later point, but any acceptance is irrevocable. S...
详细信息
online graph problems are considered in models where the irrevocability requirement is relaxed. We consider the Late Accept model, where a request can be accepted at a later point, but any acceptance is irrevocable. Similarly, we consider a Late Reject model, where an accepted request can later be rejected, but any rejection is irrevocable (this is sometimes called preemption). Finally, we consider the Late Accept/Reject model, where late accepts and rejects are both allowed, but any late reject is irrevocable. We consider four classical graph problems: For Maximum Independent Set, the Late Accept/Reject model is necessary to obtain a constant competitive ratio, for Minimum Vertex Cover the Late Accept model is sufficient, and for Minimum Spanning Forest the Late Reject model is sufficient. The Maximum Matching problem admits constant competitive ratios in all cases. We also consider Maximum Acyclic Subgraph and Maximum Planar Subgraph, which exhibit patterns similar to Maximum Independent Set.
We consider the following buffer management problem arising in QoS networks: Packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packe...
详细信息
We consider the following buffer management problem arising in QoS networks: Packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. Packets not forwarded before their deadlines are lost. The main result of the article is an online 64/33 approximate to 1.939-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. For the 2-uniform case we give an algorithm with ratio approximate to 1.377 and a matching lower bound.
The relative worst order ratio is a measure for the quality of online algorithms. Unlike the competitive ratio, it compares algorithms directly without involving an optimal offline algorithm. The measure has been succ...
详细信息
The relative worst order ratio is a measure for the quality of online algorithms. Unlike the competitive ratio, it compares algorithms directly without involving an optimal offline algorithm. The measure has been successfully applied to problems like paging and bin packing. In this paper, we apply it to machine scheduling. We show that for preemptive scheduling, the measure separates multiple pairs of algorithms which have the same competitive ratios;with the relative worst order ratio, the algorithm which is "intuitively better" is also provably better. Moreover, we show one such example for non-preemptive scheduling.
We consider the sorting buffers problem. Input to this problem is a sequence of requests, each specified by a point in a metric space. There is a "server" that moves from point to point to serve these reques...
详细信息
We consider the sorting buffers problem. Input to this problem is a sequence of requests, each specified by a point in a metric space. There is a "server" that moves from point to point to serve these requests. To serve a request, the server needs to visit the point corresponding to that request. The objective is to minimize the total distance traveled by the server in the metric space. In order to achieve this, the server is allowed to serve the requests in any order that requires to "buffer" at most k requests at any time. Thus a valid reordering can serve a request only after serving all but k previous requests. In this paper, we consider this problem on the line metric which is motivated by its application to the disc scheduling problem. We present first approximation algorithms with non-trivial approximation ratios in both online and offline settings. On a line metric with n uniformly spaced points, we give a randomized online algorithm with a competitive ratio of O(log(2) n) in expectation against an oblivious adversary. In the offline setting, our algorithm yields the first constant-factor approximation and runs in quasi-polynomial time N center dot n center dot k(O(logn)) where N is the total number of requests. Our approach is based on a dynamic program that keeps track of the number of pending requests in each of O(logn) line segments that are geometrically increasing in length. (C) 2008 Elsevier B.V. All rights reserved.
暂无评论