Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAchieving Optimal Backlog in Multi-Processor Cup Games
56
0
0.0
(
0
)
Added by
William Kuszmaul
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
We study an optimal targeting problem for super-modular games with binary actions and finitely many players. The considered problem consists in the selection of a subset of players of minimum size such that, when the actions of these players are forced to a controlled value while the others are left to repeatedly play a best response action, the system will converge to the greatest Nash equilibrium of the game. Our main contributions consist in showing that the problem is NP-complete and in proposing an efficient iterative algorithm with provable convergence properties for its solution. We discuss in detail the special case of network coordination games and its relation with the notion of cohesiveness. Finally, we show with simulations the strength of our approach with respect to naive heuristics based on classical network centrality measures.
In this paper, an optimal output consensus problem is studied for discrete-time linear multiagent systems subject to external disturbances. Each agent is assigned with a local cost function which is known only to itself. Distributed protocols are to be designed to guarantee an output consensus for these high-order agents and meanwhile minimize the aggregate cost as the sum of these local costs. To overcome the difficulties brought by high-order dynamics and external disturbances, we develop an embedded design and constructively present a distributed rule to solve this problem. The proposed control includes three terms: an optimal signal generator under a directed information graph, an observer-based compensator to reject these disturbances, and a reference tracking controller for these linear agents. It is shown to solve the formulated problem with some mild assumptions. A numerical example is also provided to illustrate the effectiveness of our proposed distributed control laws.
We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count Unique Games, is a promise problem in which the yes case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the yes case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion. We also show that a modest improvement to the parameters for which we give results would refute the Unique Games Conjecture.
In this work, we provide faster algorithms for approximating the optimal transport distance, e.g. earth movers distance, between two discrete probability distributions $mu, u in Delta^n$. Given a cost function $C : [n] times [n] to mathbb{R}_{geq 0}$ where $C(i,j) leq 1$ quantifies the penalty of transporting a unit of mass from $i$ to $j$, we show how to compute a coupling $X$ between $r$ and $c$ in time $widetilde{O}left(n^2 /epsilon right)$ whose expected transportation cost is within an additive $epsilon$ of optimal. This improves upon the previously best known running time for this problem of $widetilde{O}left(text{min}left{ n^{9/4}/epsilon, n^2/epsilon^2 right}right)$. We achieve our results by providing reductions from optimal transport to canonical optimization problems for which recent algorithmic efforts have provided nearly-linear time algorithms. Leveraging nearly linear time algorithms for solving packing linear programs and for solving the matrix balancing problem, we obtain two separate proofs of our stated running time. Further, one of our algorithms is easily parallelized and can be implemented with depth $widetilde{O}(1/epsilon)$. Moreover, we show that further algorithmic improvements to our result would be surprising in the sense that any improvement would yield an $o(n^{2.5})$ algorithm for textit{maximum cardinality bipartite matching}, for which currently the only known algorithms for achieving such a result are based on fast-matrix multiplication.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
