Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Minimum Backlog Problem
486
0
0.0
(
0
)
Added by
Jukka Suomela
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the minimum backlog problem (MBP). This online problem arises, e.g., in the context of sensor networks. We focus on two main variants of MBP. The discrete MBP is a 2-person game played on a graph $G=(V,E)$. The player is initially located at a vertex of the graph. In each time step, the adversary pours a total of one unit of water into cups that are located on the vertices of the graph, arbitrarily distributing the water among the cups. The player then moves from her current vertex to an adjacent vertex and empties the cup at that vertex. The players objective is to minimize the backlog, i.e., the maximum amount of water in any cup at any time. The geometric MBP is a continuous-time version of the MBP: the cups are points in the two-dimensional plane, the adversary pours water continuously at a constant rate, and the player moves in the plane with unit speed. Again, the players objective is to minimize the backlog. We show that the competitive ratio of any algorithm for the MBP has a lower bound of $Omega(D)$, where $D$ is the diameter of the graph (for the discrete MBP) or the diameter of the point set (for the geometric MBP). Therefore we focus on determining a strategy for the player that guarantees a uniform upper bound on the absolute value of the backlog. For the absolute value of the backlog there is a trivial lower bound of $Omega(D)$, and the deamortization analysis of Dietz and Sleator gives an upper bound of $O(Dlog N)$ for $N$ cups. Our main result is a tight upper bound for the geometric MBP: we show that there is a strategy for the player that guarantees a backlog of $O(D)$, independently of the number of cups.
rate research
Read More
Minimum Label Cut (or Hedge Connectivity) problem is defined as follows: given an undirected graph $G=(V, E)$ with $n$ vertices and $m$ edges, in which, each edge is labeled (with one or multiple labels) from a label set $L={ell_1,ell_2, ..., ell_{|L|}}$, the edges may be weighted with weight set $W ={w_1, w_2, ..., w_m}$, the label cut problem(hedge connectivity) problem asks for the minimum number of edge sets(each edge set (or hedge) is the edges with the same label) whose removal disconnects the source-sink pair of vertices or the whole graph with minimum total weights(minimum cardinality for unweighted version). This problem is more general than edge connectivity and hypergraph edge connectivity problem and has a lot of applications in MPLS, IP networks, synchronous optical networks, image segmentation, and other areas. However, due to limited communications between different communities, this problem was studied in different names, with some important existing literature citations missing, or sometimes the results are misleading with some errors. In this paper, we make a further investigation of this problem, give uniform definitions, fix existing errors, provide new insights and show some new results. Specifically, we show the relationship between non-overlapping version(each edge only has one label) and overlapping version(each edge has multiple labels), by fixing the error in the existing literature; hardness and approximation performance between weighted version and unweighted version and some useful properties for further research.
The single- and multi- processor cup games can be used to model natural problems in areas such as processor scheduling, deamortization, and buffer management. At the beginning of the single-processor cup game, $n$ cups are initially empty. In each step of the game, a filler distributes $1$ unit of water among the cups, and then an emptier selects a cup and removes $1 + epsilon$ units from that cup. The goal of the emptier is to minimize the amount of water in the fullest cup, also known as the backlog. It is known that the greedy algorithm (i.e., empty the fullest cup) achieves backlog $O(log n)$, and that no deterministic algorithm can do better. We show that the performance of the greedy algorithm can be greatly improved with a small amount of randomization: After any step $i$, and for any $k ge Omega(log epsilon^{-1})$, the emptier achieves backlog at most $O(k)$ with probability at least $1 -O(2^{-2^k})$. Whereas bounds for the single-processor cup game have been known for more than fifteen years, proving nontrivial bounds on backlog for the multi-processor extension has remained open. We present a simple analysis of the greedy algorithm for the multi-processor cup game, establishing a backlog of $O(epsilon^{-1} log n)$, as long as $delta$, the games other speed-augmentation constant, is at least $1/poly(n)$. Turning to randomized algorithms, we encounter an unexpected phenomenon: When the number of processors $p$ is large, the backlog after each step drops to emph{constant} with large probability. Specifically, we show that if $delta$ and $epsilon$ satisfy reasonable constraints, then there exists an algorithm that bounds the backlog after a given step by three or less with probability at least $1 - O(exp(-Omega(epsilon^2 p))$. We further extend the guarantees of our randomized algorithm to consider larger backlogs.
In this paper we consider two problems regarding the scheduling of available personnel in order to perform a given quantity of work, which can be arbitrarily decomposed into a sequence of activities. We are interested in schedules which minimize the overall dissatisfaction, where each employees dissatisfaction is modeled as a time-dependent linear function. For the two situations considered we provide a detailed mathematical analysis, as well as efficient algorithms for determining optimal schedules.
We consider a transmission scheduling problem in which multiple systems receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall age of information. We call this problem the Min-Age problem. This problem is first studied by He textit{et al.} [IEEE Trans. Inform. Theory, 2018], who identified several special cases where the problem can be solved optimally in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant $r geq 1$, every $r$-approximation algorithm for the Min-WCS problem can be transformed into an $r$-approximation algorithm for the Min-Age problem. Second, we give a randomized 2.733-approximation algorithm and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-Age problem is NP-hard.
We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query $S subset V$, the oracle returns the size of the cut between $S$ and $V setminus S$. We provide algorithms computing an exact minimum $s$-$t$ cut in $G$ with $tilde{O}(n^{5/3})$ queries, and computing an exact global minimum cut of $G$ with only $tilde{O}(n)$ queries (while learning the graph requires $tilde{Theta}(n^2)$ queries).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
