SOSA 2019 January 8-9, 2019 - San Diego, CA, USA

2nd Symposium on Simplicity in Algorithms (SOSA 2019)



Jeremy T. Fineman and Michael Mitzenmacher (Eds.)
ISBN 978-3-95977-099-6, OASICS Vol. 69 ISSN 2190-6807
Additional Information
License
Conference Website
Complete volume (PDF, 10 MB)
Search Publication Server

Authors
  • Alman, Josh
  • Assadi, Sepehr
  • Barba, Luis
  • Bernstein, Aaron
  • Chang, Yi-Jun
  • Chekuri, Chandra
  • Dereniowski, Dariusz
  • Ducoffe, Guillaume
  • Felsner, Stefan
  • Filtser, Arnold
  • Fineman, Jeremy T.
  • Garg, Jugal
  • Ghaffari, Mohsen
  • Jin, Ce
  • Jin, Wenyu
  • Kaplan, Haim
  • Karmalkar, Sushrut
  • Kotrbcík, Michal
  • Kozma, László
  • Krauthgamer, Robert
  • Liu, Paul
  • Liu, Sixue
  • Manurangsi, Pasin
  • McGlaughlin, Peter
  • Mitzenmacher, Michael
  • Mulzer, Wolfgang
  • Pettie, Seth
  • Price, Eric
  • Quanrud, Kent
  • Rote, Günter
  • Skoviera, Martin
  • Taki, Setareh
  • Tarjan, Robert E.
  • Tiegel, Stefan
  • Trabelsi, Ohad
  • Uznanski, Przemyslaw
  • Vondrak, Jan
  • Wajc, David
  • Wolleb-Graf, Daniel
  • Wu, Hongxun
  • Xu, Chao
  • Zamir, Or
  • Zwick, Uri
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Fineman, Jeremy T. ; Mitzenmacher, Michael

    Abstract | Document (329 KB) | BibTeX

    Isotonic Regression by Dynamic Programming
    Authors: Rote, Günter

    Abstract | Document (885 KB) | BibTeX

    An Illuminating Algorithm for the Light Bulb Problem
    Authors: Alman, Josh

    Abstract | Document (411 KB) | BibTeX

    Simple Concurrent Labeling Algorithms for Connected Components
    Authors: Liu, Sixue ; Tarjan, Robert E.

    Abstract | Document (683 KB) | BibTeX

    A Framework for Searching in Graphs in the Presence of Errors
    Authors: Dereniowski, Dariusz ; Tiegel, Stefan ; Uznanski, Przemyslaw ; Wolleb-Graf, Daniel

    Abstract | Document (524 KB) | BibTeX

    Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps
    Authors: Kaplan, Haim ; Kozma, László ; Zamir, Or ; Zwick, Uri

    Abstract | Document (697 KB) | BibTeX

    Approximating Optimal Transport With Linear Programs
    Authors: Quanrud, Kent

    Abstract | Document (437 KB) | BibTeX

    LP Relaxation and Tree Packing for Minimum k-cuts
    Authors: Chekuri, Chandra ; Quanrud, Kent ; Xu, Chao

    Abstract | Document (485 KB) | BibTeX

    On Primal-Dual Circle Representations
    Authors: Felsner, Stefan ; Rote, Günter

    Abstract | Document (871 KB) | BibTeX

    Asymmetric Convex Intersection Testing
    Authors: Barba, Luis ; Mulzer, Wolfgang

    Abstract | Document (634 KB) | BibTeX

    Relaxed Voronoi: A Simple Framework for Terminal-Clustering Problems
    Authors: Filtser, Arnold ; Krauthgamer, Robert ; Trabelsi, Ohad

    Abstract | Document (763 KB) | BibTeX

    Towards a Unified Theory of Sparsification for Matching Problems
    Authors: Assadi, Sepehr ; Bernstein, Aaron

    Abstract | Document (516 KB) | BibTeX

    A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters
    Authors: Ducoffe, Guillaume

    Abstract | Document (470 KB) | BibTeX

    Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching
    Authors: Ghaffari, Mohsen ; Wajc, David

    Abstract | Document (421 KB) | BibTeX

    Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph
    Authors: Kotrbcík, Michal ; Skoviera, Martin

    Abstract | Document (380 KB) | BibTeX

    A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation
    Authors: Manurangsi, Pasin

    Abstract | Document (634 KB) | BibTeX

    Simple Contention Resolution via Multiplicative Weight Updates
    Authors: Chang, Yi-Jun ; Jin, Wenyu ; Pettie, Seth

    Abstract | Document (574 KB) | BibTeX

    A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum
    Authors: Jin, Ce ; Wu, Hongxun

    Abstract | Document (409 KB) | BibTeX

    Submodular Optimization in the MapReduce Model
    Authors: Liu, Paul ; Vondrak, Jan

    Abstract | Document (465 KB) | BibTeX

    Compressed Sensing with Adversarial Sparse Noise via L1 Regression
    Authors: Karmalkar, Sushrut ; Price, Eric

    Abstract | Document (515 KB) | BibTeX

    Approximating Maximin Share Allocations
    Authors: Garg, Jugal ; McGlaughlin, Peter ; Taki, Setareh

    Abstract | Document (389 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI