Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of n weighted vertices and ...a k-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper k-coloring of the vertices. The cost of recoloring a vertex is the vertex’s weight. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm. We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an O(logn)-competitive deterministic algorithm and an Ω(logn) lower bound on the competitive ratio of randomized algorithms. For (Δ+1)-coloring, where Δ is the maximal node degree, we present tight bounds of Θ(Δ) and Θ(logΔ) on the competitive ratios of deterministic and randomized algorithms, respectively (where Δ denotes the maximum degree). We also consider the fully dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are arbitrarily weighted, and all our lower bounds hold even in the uniform weights (unweighted) case.
We consider the online Minimum-Cost Perfect Matching with Delays (MPMD) problem introduced by Emek et al. (STOC 2016), in which a general metric space is given, and requests for points in space are ...submitted in different times in this space by an adversary. The goal is to match requests, while minimizing the sum of distances between matched pairs in addition to the time intervals passed from the moment each request appeared until it is matched. In the online Minimum-Cost Bipartite Perfect Matching with Delays (MBPMD) problem introduced by Ashlagi et al. (APPROX/RANDOM 2017), each request is also associated with one of two classes, and requests can only be matched with requests of the other class. Previous algorithms for the problems mentioned above, include randomized
O
(
log
(
n
)
)
-competitive algorithms for known and finite metric spaces,
n
being the size of the metric space, and a deterministic
O
m
-competitive algorithm,
m
being the number of requests. We introduce
O
1
𝜖
m
log
2
3
2
+
𝜖
-competitive deterministic algorithms for both problems and for any fixed
𝜖
> 0. In particular, for a small enough
𝜖
the competitive ratio becomes
O
m
0.59
. These are the first deterministic algorithms for the mentioned online matching problems, achieving a sub-linear competitive ratio. We also show that the analysis of our algorithms is tight. Our algorithms do not need to know the metric space in advance.
We consider network design problems with deadline or delay. All previous results for these models are based on randomized embedding of the graph into a tree (HST) and then solving the problem on this ...tree. We show that this is not necessary. In particular, we design a deterministic framework for these problems which is not based on embedding. This enables us to provide deterministic poly-log( n )-competitive algorithms for Steiner tree, generalized Steiner tree, node weighted Steiner tree, (non-uniform) facility location and directed Steiner tree with deadlines or with delay (where n is the number of nodes). Our deterministic algorithms also give improved guarantees over some previous randomized results. In addition, we show a lower bound of poly \text{log}(n) for some of these problems, which implies that our framework is optimal up to the power of the poly-log. Our algorithms and techniques differ significantly from those in all previous considerations of these problems.
The online machine minimization problem seeks to design a preemptive scheduling algorithm on multiple machines — each job j arrives at its release time rj, has to be processed for pj time units, and ...must be completed by its deadline dj. The goal is to minimize the number of machines the algorithm uses. We improve the O(logm)-competitive algorithm by Chen, Megow and Schewior (SODA 2016) and provide an O(logmloglogm)-competitive algorithm.
The loss of serving in the dark Azar, Yossi; Cohen, Ilan Reuven; Gamzu, Iftah
Information processing letters,
February 2023, 2023-02-00, Letnik:
180
Journal Article
Recenzirano
We study the following balls and bins stochastic process: There is a buffer with B bins, and there is a stream of balls X=〈X1,X2,…,XT〉 such that Xi is the number of balls that arrive before time i ...but after time i−1. Once a ball arrives, it is stored in one of the unoccupied bins. If all the bins are occupied then the ball is thrown away. In each time step, we select a bin uniformly at random, clear it, and gain its content. Once the stream of balls ends, all the remaining balls in the buffer are cleared and added to our gain. We are interested in analyzing the expected gain of this randomized process with respect to that of an optimal gain-maximizing strategy, which gets the same online stream of balls, and clears a ball from a bin, if exists, at any step. We name this gain ratio the loss of serving in the dark.
In this paper, we determine the exact loss of serving in the dark. We prove that the expected gain of the randomized process is worse by a factor of ρ+ϵ from that of the optimal gain-maximizing strategy where ϵ=O(1B1/3) and ρ=maxα>1αeα/((α−1)eα+e−1)≈1.69996. We also demonstrate that this bound is essentially tight as there are specific ball streams for which the above-mentioned gain ratio tends to ρ. Our stochastic process occurs naturally in packets scheduling and mechanisms design applications.
•A natural balls and bins stochastic process.•Establishing an asymptotic tight bound to the loss of this process using novel analysis ideas.•The stochastic process occurs naturally in various applications.
We discuss the well known online job scheduling problem with release times and deadlines, alongside an extended model—buffer management for packets with processing requirements. For job scheduling, ...an
Ω
log
κ
log
log
κ
lower bound on the competitive ratio of any randomized preemptive algorithm was shown by Canetti and Irani (Proceedings of the 27th annual ACM symposium on Theory of computing, ACM, pp 606–615,
1995
), where
κ
is the the maximum job duration or the maximum job value (the minimum is assumed to be 1). The proof of this well-known result is fairly elaborate and involved. In contrast, we show a significantly improved lower bound of
Ω
(
log
κ
)
using a simple proof. Our result matches the easy upper bound and closes a gap which was supposedly open for 20 years. We also discuss the problem of handling a FIFO buffer of a limited capacity, where packets arrive over time and may be preempted. Most of the work in buffer management considers the case where each packet has unit processing requirement. We consider a model where packets require some number of processing cycles before they can be transmitted. We aim to maximize the value of transmitted packets. We show an
Ω
log
κ
log
log
κ
lower bound on the competitive ratio of randomized algorithms in this setting. We also present bounds for several special cases. For packets with unit values we also show a
φ
≈
1.618
lower bound on the competitive ratio of deterministic algorithms, and a 2-competitive algorithm. For the case of packets with constant densities we present a 4-competitive algorithm.
Tractable near-optimal policies for crawling Azar, Yossi; Horvitz, Eric; Lubetzky, Eyal ...
Proceedings of the National Academy of Sciences - PNAS,
08/2018, Letnik:
115, Številka:
32
Journal Article
Recenzirano
Odprti dostop
The problem of maintaining a local cache of n constantly changing pages arises in multiple mechanisms such as web crawlers and proxy servers. In these, the resources for polling pages for possible ...updates are typically limited. The goal is to devise a polling and fetching policy that maximizes the utility of served pages that are up to date. Cho and Garcia-Molina (2003) ACM Trans Database Syst 28:390–426 formulated this as an optimization problem, which can be solved numerically for small values of n, but appears intractable in general. Here, we show that the optimal randomized policy can be found exactly in O(n log n) operations. Moreover, using the optimal probabilities to define in linear time a deterministic schedule yields a tractable policy that in experiments attains 99% of the optimum.
In this paper, we present a framework used to construct and analyze algorithms for online optimization problems with deadlines or with delay over a metric space. Using this framework, we present ...algorithms for several different problems. We present an O(D ^ 2) -competitive deterministic algorithm for online multilevel aggregation with delay on a tree of depth D, an exponential improvement over the O(D 4 2 D ) -competitive algorithm of Bienkowski et al. (ESA '16), where the only previously-known improvement was for the special case of deadlines by Buchbinder et al. (SODA '17). We also present an O(log 2 n) -competitive randomized algorithm for online service with delay over any general metric space of n points, improving upon the O(log 4 n) -competitive algorithm by Azar et al. (STOC '17). In addition, we present the problem of online facility location with deadlines. In this problem, requests arrive over time in a metric space, and need to be served until their deadlines by facilities that are opened momentarily for some cost. We also consider the problem of facility location with delay, in which the deadlines are replaced with arbitrary delay functions. For those problems, we present O(log 2 n) -competitive algorithms, with n the number of points in the metric space. The algorithmic framework we present includes techniques for the design of algorithms as well as techniques for their analysis.
PDF
