SOSA 2018 January 7-10, 2018 - New Orleans, LA, USA

1st Symposium on Simplicity in Algorithms (SOSA 2018)



Raimund Seidel (Ed.)
ISBN 978-3-95977-064-4, OASICS Vol. 61 ISSN 2190-6807
Additional Information
License
Conference Website
Complete volume (PDF, 7 MB)
Search Publication Server


Authors
  • Aggarwal, Divesh
  • Berenbrink, Petra
  • Borodin, Allan
  • Cao, Yixin
  • Chakrabarty, Deeparnab
  • Chan, Timothy M.
  • Chekuri, Chandra
  • Cohen, Michael B.
  • Eden, Talya
  • Idleman, Mark
  • Jansen, Klaus
  • Jayram, T.S.
  • Kaaser, Dominik
  • Khanna, Sanjeev
  • Kling, Peter
  • Kopelowitz, Tsvi
  • McGregor, Andrew
  • Nelson, Jelani
  • Newman, Alantha
  • Otterbach, Lena
  • Pankratov, Denis
  • Porat, Ely
  • Rohwedder, Lars
  • Rosenbaum, Will
  • Rukkanchanunt, Thapanapong
  • Salehi-Abari, Amirali
  • Seidel, Raimund
  • Stephens-Davidowitz, Noah
  • Vorotnikova, Sofya
  • Williams, R. Ryan

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Seidel, Raimund

    Abstract | Document (327 KB) | BibTeX

    A Naive Algorithm for Feedback Vertex Set
    Authors: Cao, Yixin

    Abstract | Document (497 KB) | BibTeX

    A Note on Iterated Rounding for the Survivable Network Design Problem
    Authors: Chekuri, Chandra ; Rukkanchanunt, Thapanapong

    Abstract | Document (512 KB) | BibTeX

    Congestion Minimization for Multipath Routing via Multiroute Flows
    Authors: Chekuri, Chandra ; Idleman, Mark

    Abstract | Document (485 KB) | BibTeX

    Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling
    Authors: Chakrabarty, Deeparnab ; Khanna, Sanjeev

    Abstract | Document (543 KB) | BibTeX

    Approximation Schemes for 0-1 Knapsack
    Authors: Chan, Timothy M.

    Abstract | Document (495 KB) | BibTeX

    Counting Solutions to Polynomial Systems via Reductions
    Authors: Williams, R. Ryan

    Abstract | Document (553 KB) | BibTeX

    On Sampling Edges Almost Uniformly
    Authors: Eden, Talya ; Rosenbaum, Will

    Abstract | Document (469 KB) | BibTeX

    A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version
    Authors: Borodin, Allan ; Pankratov, Denis ; Salehi-Abari, Amirali

    Abstract | Document (498 KB) | BibTeX

    Simple and Efficient Leader Election
    Authors: Berenbrink, Petra ; Kaaser, Dominik ; Kling, Peter ; Otterbach, Lena

    Abstract | Document (565 KB) | BibTeX

    A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance
    Authors: Kopelowitz, Tsvi ; Porat, Ely

    Abstract | Document (418 KB) | BibTeX

    Compact LP Relaxations for Allocation Problems
    Authors: Jansen, Klaus ; Rohwedder, Lars

    Abstract | Document (529 KB) | BibTeX

    Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP)
    Authors: Aggarwal, Divesh ; Stephens-Davidowitz, Noah

    Abstract | Document (616 KB) | BibTeX

    Complex Semidefinite Programming and Max-k-Cut
    Authors: Newman, Alantha

    Abstract | Document (470 KB) | BibTeX

    A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs
    Authors: McGregor, Andrew ; Vorotnikova, Sofya

    Abstract | Document (387 KB) | BibTeX

    Simple Analyses of the Sparse Johnson-Lindenstrauss Transform
    Authors: Cohen, Michael B. ; Jayram, T.S. ; Nelson, Jelani

    Abstract | Document (500 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI