3 Search Results for "Anderson, Daniel"


Document
Parallel Batch-Dynamic Trees via Change Propagation

Authors: Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


Abstract
The dynamic trees problem is to maintain a forest subject to edge insertions and deletions while facilitating queries such as connectivity, path weights, and subtree weights. Dynamic trees are a fundamental building block of a large number of graph algorithms. Although traditionally studied in the single-update setting, dynamic algorithms capable of supporting batches of updates are increasingly relevant today due to the emergence of rapidly evolving dynamic datasets. Since processing updates on a single processor is often unrealistic for large batches of updates, designing parallel batch-dynamic algorithms that achieve provably low span is important for many applications. In this work, we design the first work-efficient parallel batch-dynamic algorithm for dynamic trees that is capable of supporting both path queries and subtree queries, as well as a variety of nonlocal queries. Previous work-efficient dynamic trees of Tseng et al. were only capable of handling subtree queries [ALENEX'19, (2019), pp. 92 - 106]. To achieve this, we propose a framework for algorithmically dynamizing static round-synchronous algorithms to obtain parallel batch-dynamic algorithms. In our framework, the algorithm designer can apply the technique to any suitably defined static algorithm. We then obtain theoretical guarantees for algorithms in our framework by defining the notion of a computation distance between two executions of the underlying algorithm. Our dynamic trees algorithm is obtained by applying our dynamization framework to the parallel tree contraction algorithm of Miller and Reif [FOCS'85, (1985), pp. 478 - 489], and then performing a novel analysis of the computation distance of this algorithm under batch updates. We show that k updates can be performed in O(klog(1+n/k)) work in expectation, which matches the algorithm of Tseng et al. while providing support for a substantially larger number of queries and applications.

Cite as

Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. Parallel Batch-Dynamic Trees via Change Propagation. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{acar_et_al:LIPIcs.ESA.2020.2,
  author =	{Acar, Umut A. and Anderson, Daniel and Blelloch, Guy E. and Dhulipala, Laxman and Westrick, Sam},
  title =	{{Parallel Batch-Dynamic Trees via Change Propagation}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.2},
  URN =		{urn:nbn:de:0030-drops-128686},
  doi =		{10.4230/LIPIcs.ESA.2020.2},
  annote =	{Keywords: Dynamic trees, Graph algorithms, Parallel algorithms, Dynamic algorithms}
}
Document
Track A: Algorithms, Complexity and Games
Minimum Cut in O(m log² n) Time

Authors: Paweł Gawrychowski, Shay Mozes, and Oren Weimann

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
We give a randomized algorithm that finds a minimum cut in an undirected weighted m-edge n-vertex graph G with high probability in O(m log² n) time. This is the first improvement to Karger’s celebrated O(m log³ n) time algorithm from 1996. Our main technical contribution is a deterministic O(m log n) time algorithm that, given a spanning tree T of G, finds a minimum cut of G that 2-respects (cuts two edges of) T.

Cite as

Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Minimum Cut in O(m log² n) Time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.ICALP.2020.57,
  author =	{Gawrychowski, Pawe{\l} and Mozes, Shay and Weimann, Oren},
  title =	{{Minimum Cut in O(m log² n) Time}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.57},
  URN =		{urn:nbn:de:0030-drops-124646},
  doi =		{10.4230/LIPIcs.ICALP.2020.57},
  annote =	{Keywords: Minimum cut, Minimum 2-respecting cut}
}
Document
A Contract and Balancing Mechanism for Sharing Capacity in a Communication Network

Authors: Edward Anderson, Frank Kelly, and Richard Steinberg

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)


Abstract
We propose a method for determining how much to charge users of a communication network when they share bandwidth. Our approach can be employed either when a network owner wishes to sell bandwidth for a specified period of time to a number of different users, or when users cooperate to build a network to be shared among themselves. We show how a Contract and Balancing Mechanism can be defined to mediate between rapidly fluctuating prices and the longer time scales over which bandwidth contracts might be traded. An important property of the process is that it avoids introducing perverse incentives for a capacity provider to increase congestion.

Cite as

Edward Anderson, Frank Kelly, and Richard Steinberg. A Contract and Balancing Mechanism for Sharing Capacity in a Communication Network. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.05011.3,
  author =	{Anderson, Edward and Kelly, Frank and Steinberg, Richard},
  title =	{{A Contract and Balancing Mechanism for Sharing Capacity in a Communication Network}},
  booktitle =	{Computing and Markets},
  pages =	{1--31},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.3},
  URN =		{urn:nbn:de:0030-drops-2041},
  doi =		{10.4230/DagSemProc.05011.3},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio}
}
  • Refine by Author
  • 1 Acar, Umut A.
  • 1 Anderson, Daniel
  • 1 Anderson, Edward
  • 1 Blelloch, Guy E.
  • 1 Dhulipala, Laxman
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Shared memory algorithms

  • Refine by Keyword
  • 1 Dynamic algorithms
  • 1 Dynamic trees
  • 1 Graph algorithms
  • 1 Minimum 2-respecting cut
  • 1 Minimum cut
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2020
  • 1 2005

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail