1,721,010 research outputs found
The Red-Blue Pebble Game on Trees and DAGs with Large Input
No full textISSN:0302-9743ISSN:1611-3349ISSN:1611-334
On the Computational Power of Energy-Constrained Mobile Robots:Algorithms and Cross-Model Analysis
No full textWe consider distributed systems of identical autonomous computational entities, called robots, moving and operating in the plane in synchronous Look - Compute - Move (LCM ) cycles. The algorithmic capabilities of these systems have been extensively investigated in the literature under four distinct models (OBLOT, FSTA, FCOM, LUMI ), each identifying different levels of memory persistence and communication capabilities of the robots. Despite their differences, they all always assume that robots have unlimited amounts of energy. In this paper, we remove this assumption and start the study of the computational capabilities of robots whose energy is limited, albeit renewable. We first study the impact that memory persistence and communication capabilities have on the computational power of such energy-constrained systems of robots; we do so by analyzing the computational relationship between the four models under this energy constraint. We provide a complete characterization of this relationship. We then study the difference in computational power caused by the energy restriction and provide a complete characterization of the relationship between energy-constrained and unrestricted robots in each model. We prove that within LUMI there is no difference; an integral part of the proof is the design and analysis of an algorithm that in LUMI allows energy-constrained robots to execute correctly any protocol for robots with unlimited energy. We then show the (apparently counterintuitive) result that in all other models, the energy constraint actually provides the robots with a computational advantage.</p
Minimum-cost paths for electric cars
No full textAn electric car equipped with a battery of a finite capacity travels on a road network with an infrastructure of charging stations. Each charging station has a possibly different cost per unit of energy. Traversing a given road segment requires a specified amount of energy that may be positive, zero or negative. The car can only traverse a road segment if it has enough charge to do so (the charge cannot drop below zero), and it cannot charge its battery beyond its capacity. To travel from one point to another the car needs to choose a travel plan consisting of a path in the network and a recharging schedule that specifies how much energy to charge at each charging station on the path, making sure of having enough energy to reach the next charging station or the destination. The cost of the plan is the total charging cost along the chosen path. We reduce the problem of computing plans between every two junctions of the network to two problems: Finding optimal energetic paths when no charging is allowed and finding standard shortest paths. When there are no negative cycles in the network, we obtain an O(n3)-time algorithm for computing all-pairs travel plans, where n is the number of junctions in the network. We obtain slightly faster algorithms under some further assumptions. We also consider the case in which a bound is placed on the number of rechargings allowed.</p
Simpler constant factor approximation algorithms for weighted flow time – now for any p-norm
No full textA prominent problem in scheduling theory is the weighted flow time problem on one machine. We are given a machine and a set of jobs, each of them characterized by a processing time, a release time, and a weight. The goal is to find a (possibly preemptive) schedule for the jobs in order to minimize the sum of the weighted flow times, where the flow time of a job is the time between its release time and its completion time. It had been a longstanding important open question to find a polynomial time O(1)-approximation algorithm for the problem. In a break-through result, Batra, Garg, and Kumar (FOCS 2018) presented such an algorithm with pseudopolynomial running time. Its running time was improved to polynomial time by Feige, Kulkarni, and Li (SODA 2019). The approximation ratios of these algorithms are relatively large, but they were improved to 2 + ? by Rohwedder and Wiese (STOC 2022) and subsequently to 1 + ? by Armbruster, Rohwedder, and Wiese (STOC 2023). All these algorithms are quite complicated and involve for example a reduction to (geometric) covering problems, dynamic programs to solve those, and LP-rounding methods to reduce the running time to a polynomial in the input size. In this paper, we present a much simpler (6 + ?)-approximation algorithm for the problem that does not use any of these reductions, but which works on the input jobs directly. It even generalizes directly to an O(1)-approximation algorithm for minimizing the p-norm of the jobs’ flow times, for any 0 < p < 8 (the original problem setting corresponds to p = 1). Prior to our work, for p > 1 only a pseudopolynomial time O(1)-approximation algorithm was known for this variant, and no algorithm for p < 1. For the same objective function, we present a very simple QPTAS for the setting of constantly many unrelated machines for 0 < p < 8 (and assuming quasi-polynomially bounded input data). It works in the cases with and without the possibility to migrate a job to a different machine. This is the first QPTAS for the problem if migrations are allowed, and it is arguably simpler than the known QPTAS for minimizing the weighted sum of the jobs’ flow times without migration
Computing in Additive Networks with Bounded-Information Codes
No full textThis paper studies the theory of the additive wireless network model, in which the received signal is abstracted as an addition of the transmitted signals. Our central observation is that the crucial challenge for computing in this model is not high contention, as assumed previously, but rather guaranteeing a bounded amount of information in each neighborhood per round, a property that we show is achievable using a new random coding technique. Technically, we provide efficient algorithms for fundamental distributed tasks in additive networks, such as solving various symmetry breaking problems, approximating network parameters, and solving an asymmetry revealing problem such as computing a maximal input. The key method used is a novel random coding technique that allows a node to successfully decode the received information, as long as it does not contain too many distinct values. We then design our algorithms to produce a limited amount of information in each neighborhood in order to leverage our enriched toolbox for computing in additive networks.National Science Foundation (U.S.) (Award CCF-1217506)National Science Foundation (U.S.) (Award CCF-AF-0937274)National Science Foundation (U.S.) (Award CCF-0939370)United States. Air Force Office of Scientific Research (Contract FA9550-14-1-0403)United States. Air Force Office of Scientific Research (Contract FA9550-13-1-0042
Distributed Planar Reachability in Nearly Optimal Time
Full text linkWe present nearly optimal distributed algorithms for fundamental reachability problems in planar graphs. In the single-source reachability problem given is an n-vertex directed graph G = (V,E) and a source node s, it is required to determine the subset of nodes that are reachable from s in G. We present the first distributed reachability algorithm for planar graphs that runs in nearly optimal time of Õ(D) rounds, where D is the undirected diameter of the graph. This improves the complexity of Õ(D²) rounds implied by the recent work of [Li and Parter, STOC'19].
We also consider the more general reachability problem of identifying the strongly connected components (SCCs) of the graph. We present an Õ(D)-round algorithm that computes for each node in the graph an identifier of its strongly connected component in G. No non-trivial upper bound for this problem (even in general graphs) has been known before.
Our algorithms are based on characterizing the structural interactions between balanced cycle separators. We show that the reachability relations between separator nodes can be compressed due to a Monge-like property of their directed shortest paths. The algorithmic results are obtained by combining this structural characterization with the recursive graph partitioning machinery of [Li and Parter, STOC'19]
\~{O}ptimal Vertex Fault-Tolerant Spanners in \~{O}ptimal Time: Sequential, Distributed and Parallel
Full text linkWe (nearly) settle the time complexity for computing vertex fault-tolerant
(VFT) spanners with optimal sparsity (up to polylogarithmic factors). VFT
spanners are sparse subgraphs that preserve distance information, up to a small
multiplicative stretch, in the presence of vertex failures. These structures
were introduced by [Chechik et al., STOC 2009] and have received a lot of
attention since then. We provide algorithms for computing nearly optimal
-VFT spanners for any -vertex -edge graph, with near optimal running
time in several computational models:
- A randomized sequential algorithm with a runtime of
(i.e., independent in the number of faults ). The state-of-the-art time
bound is by [Bodwin, Dinitz and
Robelle, SODA 2021].
- A distributed congest algorithm of rounds. Improving
upon [Dinitz and Robelle, PODC 2020] that obtained FT spanners with
near-optimal sparsity in rounds.
- A PRAM (CRCW) algorithm with work and
depth. Prior bounds implied by [Dinitz and Krauthgamer, PODC 2011] obtained
sub-optimal FT spanners using work and
depth.
An immediate corollary provides the first nearly-optimal PRAM algorithm for
computing nearly optimal -\emph{vertex} connectivity certificates
using polylogarithmic depth and near-linear work. This improves the
state-of-the-art parallel bounds of depth and
work, by [Karger and Motwani, STOC'93].Comment: STOC 202
Small Cuts and Connectivity Certificates: A Fault Tolerant Approach
Full text linkWe revisit classical connectivity problems in the {CONGEST} model of distributed computing. By using techniques from fault tolerant network design, we show improved constructions, some of which are even "local" (i.e., with O~(1) rounds) for problems that are closely related to hard global problems (i.e., with a lower bound of Omega(Diam+sqrt{n}) rounds).
Distributed Minimum Cut: Nanongkai and Su presented a randomized algorithm for computing a (1+epsilon)-approximation of the minimum cut using O~(D +sqrt{n}) rounds where D is the diameter of the graph. For a sufficiently large minimum cut lambda=Omega(sqrt{n}), this is tight due to Das Sarma et al. [FOCS '11], Ghaffari and Kuhn [DISC '13].
- Small Cuts: A special setting that remains open is where the graph connectivity lambda is small (i.e., constant). The only lower bound for this case is Omega(D), with a matching bound known only for lambda <= 2 due to Pritchard and Thurimella [TALG '11]. Recently, Daga, Henzinger, Nanongkai and Saranurak [STOC '19] raised the open problem of computing the minimum cut in poly(D) rounds for any lambda=O(1). In this paper, we resolve this problem by presenting a surprisingly simple algorithm, that takes a completely different approach than the existing algorithms. Our algorithm has also the benefit that it computes all minimum cuts in the graph, and naturally extends to vertex cuts as well. At the heart of the algorithm is a graph sampling approach usually used in the context of fault tolerant (FT) design.
- Deterministic Algorithms: While the existing distributed minimum cut algorithms are randomized, our algorithm can be made deterministic within the same round complexity. To obtain this, we introduce a novel definition of universal sets along with their efficient computation. This allows us to derandomize the FT graph sampling technique, which might be of independent interest.
- Computation of all Edge Connectivities: We also consider the more general task of computing the edge connectivity of all the edges in the graph. In the output format, it is required that the endpoints u,v of every edge (u,v) learn the cardinality of the u-v cut in the graph. We provide the first sublinear algorithm for this problem for the case of constant connectivity values. Specifically, by using the recent notion of low-congestion cycle cover, combined with the sampling technique, we compute all edge connectivities in poly(D) * 2^{O(sqrt{log n log log n})} rounds.
Sparse Certificates: For an n-vertex graph G and an integer lambda, a lambda-sparse certificate H is a subgraph H subseteq G with O(lambda n) edges which is lambda-connected iff G is lambda-connected. For D-diameter graphs, constructions of sparse certificates for lambda in {2,3} have been provided by Thurimella [J. Alg. '97] and Dori [PODC '18] respectively using O~(D) number of rounds. The problem of devising such certificates with o(D+sqrt{n}) rounds was left open by Dori [PODC '18] for any lambda >= 4. Using connections to fault tolerant spanners, we considerably improve the round complexity for any lambda in [1,n] and epsilon in (0,1), by showing a construction of (1-epsilon)lambda-sparse certificates with O(lambda n) edges using only O(1/epsilon^2 * log^{2+o(1)} n) rounds
(Delta+1) Coloring in the Congested Clique Model
No full textIn this paper, we present improved algorithms for the (Delta+1) (vertex) coloring problem in the Congested Clique model of distributed computing. In this model, the input is a graph on n nodes, initially each node knows only its incident edges, and per round each two nodes can exchange O(log n) bits of information.
Our key result is a randomized (Delta+1) vertex coloring algorithm that works in O(log log Delta * log^* Delta)-rounds. This is achieved by combining the recent breakthrough result of [Chang-Li-Pettie, STOC'18] in the {LOCAL} model and a degree reduction technique. We also get the following results with high probability: (1) (Delta+1)-coloring for Delta=O((n/log n)^{1-epsilon}) for any epsilon in (0,1), within O(log(1/epsilon)log^* Delta) rounds, and (2) (Delta+Delta^{1/2+o(1)})-coloring within O(log^* Delta) rounds. Turning to deterministic algorithms, we show a (Delta+1)-coloring algorithm that works in O(log Delta) rounds. Our new bounds provide exponential improvements over the state of the art
Graphs Shortcuts: New Bounds and Algorithms (Invited Talk)
No full textFor an n-vertex digraph G = (V,E), a shortcut set is a (small) subset of edges H taken from the transitive closure of G that, when added to G guarantees that the diameter of G ∪ H is small. Shortcut sets, introduced by Thorup in 1993, have a wide range of applications in algorithm design, especially in the context of parallel, distributed and dynamic computation on directed graphs. A folklore result in this context shows that every n-vertex digraph admits a shortcut set of linear size (i.e., of O(n) edges) that reduces the diameter to Õ(√n). Despite extensive research over the years, the question of whether one can reduce the diameter to o(√n) with Õ(n) shortcut edges has been left open.
In this talk, I will present the first improved diameter-sparsity tradeoff for this problem, breaking the √n diameter barrier. Specifically, we show an O(n^ω)-time randomized algorithm for computing a linear shortcut set that reduces the diameter of the digraph to Õ(n^{1/3}). I also present time efficient algorithms for computing these shortcuts and explain the limitations of the current approaches. Finally, I will draw some connections between shortcuts and several forms of graph sparsification (e.g., reachability preservers, spanners). Based on a joint work with Shimon Kogan (SODA 2022, ICALP 2022, FOCS 2022, SODA 2023)
- …
