2 Search Results for "Cohen, William W."

Document
DOI: 10.4230/LIPIcs.SWAT.2022.23
Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Authors: Michael Elkin, Yuval Gitlitz, and Ofer Neiman

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Let G = (V,E,w) be a weighted undirected graph with n vertices and m edges, and fix a set of s sources S ⊆ V. We study the problem of computing almost shortest paths (ASP) for all pairs in S × V in both classical centralized and parallel (PRAM) models of computation. Consider the regime of multiplicative approximation of 1+ε, for an arbitrarily small constant ε > 0 (henceforth (1+ε)-ASP for S × V). In this regime existing centralized algorithms require Ω(min{|E|s,n^ω}) time, where ω < 2.372 is the matrix multiplication exponent. Existing PRAM algorithms with polylogarithmic depth (aka time) require work Ω(min{|E|s,n^ω}). In a bold attempt to achieve centralized time close to the lower bound of m + n s, Cohen [Edith Cohen, 2000] devised an algorithm which, in addition to the multiplicative stretch of 1+ε, allows also additive error of β ⋅ W_{max}, where W_{max} is the maximum edge weight in G (assuming that the minimum edge weight is 1), and β = (log n)^{O((log 1/ρ)/ρ)} is polylogarithmic in n. It also depends on the (possibly) arbitrarily small parameter ρ > 0 that determines the running time O((m + ns)n^ρ) of the algorithm. The tradeoff of [Edith Cohen, 2000] was improved in [M. Elkin, 2001], whose algorithm has similar approximation guarantee and running time, but its β is (1/ρ)^{O((log 1/ρ)/ρ)}. However, the latter algorithm produces distance estimates rather than actual approximate shortest paths. Also, the additive terms in [Edith Cohen, 2000; M. Elkin, 2001] depend linearly on a possibly quite large global maximum edge weight W_{max}. In the current paper we significantly improve this state of affairs. Our centralized algorithm has running time O((m+ ns)n^ρ), and its PRAM counterpart has polylogarithmic depth and work O((m + ns)n^ρ), for an arbitrarily small constant ρ > 0. For a pair (s,v) ∈ S× V, it provides a path of length d̂(s,v) that satisfies d̂(s,v) ≤ (1+ε)d_G(s,v) + β ⋅ W(s,v), where W(s,v) is the weight of the heaviest edge on some shortest s-v path. Hence our additive term depends linearly on a local maximum edge weight, as opposed to the global maximum edge weight in [Edith Cohen, 2000; M. Elkin, 2001]. Finally, our β = (1/ρ)^{O(1/ρ)}, i.e., it is significantly smaller than in [Edith Cohen, 2000; M. Elkin, 2001]. We also extend a centralized algorithm of Dor et al. [D. Dor et al., 2000]. For a parameter κ = 1,2,…, this algorithm provides for unweighted graphs a purely additive approximation of 2(κ -1) for all pairs shortest paths (APASP) in time Õ(n^{2+1/κ}). Within the same running time, our algorithm for weighted graphs provides a purely additive error of 2(κ - 1) W(u,v), for every vertex pair (u,v) ∈ binom(V,2), with W(u,v) defined as above. On the way to these results we devise a suite of novel constructions of spanners, emulators and hopsets.
Cite as

Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Almost Shortest Paths with Near-Additive Error in Weighted Graphs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{elkin_et_al:LIPIcs.SWAT.2022.23,
  author =	{Elkin, Michael and Gitlitz, Yuval and Neiman, Ofer},
  title =	{{Almost Shortest Paths with Near-Additive Error in Weighted Graphs}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.23},
  URN =		{urn:nbn:de:0030-drops-161833},
  doi =		{10.4230/LIPIcs.SWAT.2022.23},
  annote =	{Keywords: spanners, hopset, shortest paths, PRAM, distance oracles}
}
Document
DOI: 10.4230/DagRep.5.11.90
Programming with "Big Code" (Dagstuhl Seminar 15472)

Authors: William W. Cohen, Charles Sutton, and Martin T. Vechev

Published in: Dagstuhl Reports, Volume 5, Issue 11 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15472 "Programming with "Big Code"". "Big Code" is a term used to refer to the increasing availability of the millions of programs found in open source repositories such as GitHub, BitBucket, and others. With this availability, an opportunity appears in developing new kinds of statistical programming tools that learn and leverage the effort that went into building, debugging and testing the programs in "Big Code" in order to solve various important and interesting programming challenges. Developing such statistical tools however requires deep expertise across multiple areas of computer science including machine learning, natural language processing, programming languages and software engineering. Because of its highly inter-disciplinary nature, the seminar involved top experts from these fields who have worked on or are interested in the area. The seminar was successful in familiarizing the participants with recent developments in the area, bringing new understanding to different communities and outlining future research directions.
Cite as

William W. Cohen, Charles Sutton, and Martin T. Vechev. Programming with "Big Code" (Dagstuhl Seminar 15472). In Dagstuhl Reports, Volume 5, Issue 11, pp. 90-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{cohen_et_al:DagRep.5.11.90,
  author =	{Cohen, William W. and Sutton, Charles and Vechev, Martin T.},
  title =	{{Programming with "Big Code" (Dagstuhl Seminar 15472)}},
  pages =	{90--102},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{11},
  editor =	{Cohen, William W. and Sutton, Charles and Vechev, Martin T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.11.90},
  URN =		{urn:nbn:de:0030-drops-57665},
  doi =		{10.4230/DagRep.5.11.90},
  annote =	{Keywords: machine learning, natural language processing, programming languages, software engineering, statistical programming tools}
}
  • Refine by Author
  • 1 Cohen, William W.
  • 1 Elkin, Michael
  • 1 Gitlitz, Yuval
  • 1 Neiman, Ofer
  • 1 Sutton, Charles
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 PRAM
  • 1 distance oracles
  • 1 hopset
  • 1 machine learning
  • 1 natural language processing
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2022

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact