• Login
    View Item 
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • ARC Talks and Events
    • View Item
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • ARC Talks and Events
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Towards Tight Approximation Bounds for Graph Diameter and Eccentricities

    Thumbnail
    View/Open
    williams.mp4 (369.0Mb)
    williams_videostream.html (1.012Kb)
    transcription.txt (34.65Kb)
    Date
    2018-05-16
    Author
    Vassilevska Williams, Virginia
    Metadata
    Show full item record
    Abstract
    Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much research has been devoted to how fast this parameter can be {\em approximated}. Chechik et al.\ [SODA 2014] showed that the diameter can be approximated within a multiplicative factor of $3/2$ in $\tO(m^{3/2})$ time. Roditty and Vassilevska W.\ [STOC 13] showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no $O(n^{2-\eps})$ time algorithm for $\eps>0$ can achieve an approximation factor better than $3/2$ in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than $3/2$. It was, however, completely plausible that a $3/2$-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no $O(m^{3/2-\eps})$ time algorithm can achieve an approximation factor better than $5/3$. We provide similarly tight results for other distance-related parameters, also providing new algorithms. To establish the our lower bounds we study the $S$-$T$ Diameter problem: Given a graph and two subsets $S$ and $T$ of vertices, output the largest distance between a vertex in $S$ and a vertex in $T$. We give new algorithms and show tight lower bounds that serve as a starting point for all other hardness results. In this talk I will explain the lower bound constructions for $S$-$T$ Diameter and will outline how one can extend them for Diameter as well. Joint work with Arturs Backurs, Nicole Wein, Liam Roditty and Gilad Segal. To appear in STOC 2018.
    URI
    http://hdl.handle.net/1853/59721
    Collections
    • ARC Talks and Events [88]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology