Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight Bounds for Restricted Grid Scheduling
126
0
0.0
(
0
)
Added by
Joan Boyar
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The following online bin packing problem is considered: Items with integer sizes are given and variable sized bins arrive online. A bin must be used if there is still an item remaining which fits in it when the bin arrives. The goal is to minimize the total size of all the bins used. Previously, a lower bound of 5/4 on the competitive ratio of this problem was achieved using jobs of size S and 2S-1. For these item sizes and maximum bin size 4S-3, we obtain asymptotically matching upper and lower bounds, which vary depending on the ratio of the number of small jobs to the number of large jobs.
rate research
Read More
Vizings celebrated theorem asserts that any graph of maximum degree $Delta$ admits an edge coloring using at most $Delta+1$ colors. In contrast, Bar-Noy, Naor and Motwani showed over a quarter century that the trivial greedy algorithm, which uses $2Delta-1$ colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with $Delta=O(log n)$, and they conjectured the existence of online algorithms using $Delta(1+o(1))$ colors for $Delta=omega(log n)$. Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS03 and Bahmani et al., SODA10). We resolve the above conjecture for emph{adversarial} vertex arrivals in bipartite graphs, for which we present a $(1+o(1))Delta$-edge-coloring algorithm for $Delta=omega(log n)$ known a priori. Surprisingly, if $Delta$ is not known ahead of time, we show that no $big(frac{e}{e-1} - Omega(1) big) Delta$-edge-coloring algorithm exists. We then provide an optimal, $big(frac{e}{e-1}+o(1)big)Delta$-edge-coloring algorithm for unknown $Delta=omega(log n)$. Key to our results, and of possible independent interest, is a novel fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.
We consider the following online optimization problem. We are given a graph $G$ and each vertex of the graph is assigned to one of $ell$ servers, where servers have capacity $k$ and we assume that the graph has $ell cdot k$ vertices. Initially, $G$ does not contain any edges and then the edges of $G$ are revealed one-by-one. The goal is to design an online algorithm $operatorname{ONL}$, which always places the connected components induced by the revealed edges on the same server and never exceeds the server capacities by more than $varepsilon k$ for constant $varepsilon>0$. Whenever $operatorname{ONL}$ learns about a new edge, the algorithm is allowed to move vertices from one server to another. Its objective is to minimize the number of vertex moves. More specifically, $operatorname{ONL}$ should minimize the competitive ratio: the total cost $operatorname{ONL}$ incurs compared to an optimal offline algorithm $operatorname{OPT}$. Our main contribution is a polynomial-time randomized algorithm, that is asymptotically optimal: we derive an upper bound of $O(log ell + log k)$ on its competitive ratio and show that no randomized online algorithm can achieve a competitive ratio of less than $Omega(log ell + log k)$. We also settle the open problem of the achievable competitive ratio by deterministic online algorithms, by deriving a competitive ratio of $Theta(ell lg k)$; to this end, we present an improved lower bound as well as a deterministic polynomial-time online algorithm. Our algorithms rely on a novel technique which combines efficient integer programming with a combinatorial approach for maintaining ILP solutions. We believe this technique is of independent interest and will find further applications in the future.
We study the problem of exploring an oriented grid with autonomous agents governed by finite automata. In the case of a 2-dimensional grid, the question how many agents are required to explore the grid, or equivalently, find a hidden treasure in the grid, is fully understood in both the synchronous and the semi-synchronous setting. For higher dimensions, Dobrev, Narayanan, Opatrny, and Pankratov [ICALP19] showed very recently that, surprisingly, a (small) constant number of agents suffices to find the treasure, independent of the number of dimensions, thereby disproving a conjecture by Cohen, Emek, Louidor, and Uitto [SODA17]. Dobrev et al. left as an open question whether their bounds on the number of agents can be improved. We answer this question in the affirmative for deterministic finite automata: we show that 3 synchronous and 4 semi-synchronous agents suffice to explore an $n$-dimensional grid for any constant $n$. The bounds are optimal and notably, the matching lower bounds already hold in the 2-dimensional case. Our techniques can also be used to make progress on other open questions asked by Dobrev et al.: we prove that 4 synchronous and 5 semi-synchronous agents suffice for polynomial-time exploration, and we show that, under a natural assumption, 3 synchronous and 4 semi-synchronous agents suffice to explore unoriented grids of arbitrary dimension (which, again, is tight).
We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,...,r} are to be stored in an array of size m >= n. The items are presented sequentially in an arbitrary order, and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If r<=m then we can simply store item j in location j but if r>m then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of such moves done by the algorithm. This problem is non-trivial when n=<m<r. In the case that m=Cn for some C>1, algorithms for this problem with cost O(log(n)^2) per item have been given [IKR81, Wil92, BCD+02]. When m=n, algorithms with cost O(log(n)^3) per item were given [Zha93, BS07]. In this paper we prove lower bounds that show that these algorithms are optimal, up to constant factors. Previously, the only lower bound known for this range of parameters was a lower bound of Omega(log(n)^2) for the restricted class of smooth algorithms [DSZ05a, Zha93]. We also provide an algorithm for the sparse case: If the number of items is polylogarithmic in the array size then the problem can be solved in amortized constant time per item.
We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function $f: mathbb{Z}^+ to mathbb{Z}^+$, such that for every integer $g>0$, every graph of treewidth at least $f(g)$ contains the $(gtimes g)$-grid as a minor. For every integer $g>0$, let $f(g)$ be the smallest value for which the theorem holds. Establishing tight bounds on $f(g)$ is an important graph-theoretic question. Robertson and Seymour showed that $f(g)=Omega(g^2log g)$ must hold. For a long time, the best known upper bounds on $f(g)$ were super-exponential in $g$. The first polynomial upper bound of $f(g)=O(g^{98}text{poly}log g)$ was proved by Chekuri and Chuzhoy. It was later improved to $f(g) = O(g^{36}text{poly} log g)$, and then to $f(g)=O(g^{19}text{poly}log g)$. In this paper we further improve this bound to $f(g)=O(g^{9}text{poly} log g)$. We believe that our proof is significantly simpler than the proofs of the previous bounds. Moreover, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem, it seems conceivable that the techniques proposed in this paper can lead to even tighter bounds on $f(g)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
