ESA 2019 September 9-11, 2019, Munich/Garching, Germany

27th Annual European Symposium on Algorithms (ESA 2019)



Michael A. Bender and Ola Svensson and Grzegorz Herman (Eds.)
ISBN 978-3-95977-124-5, LIPICS Vol. 144 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 48 MB)
Search Publication Server

Authors
  • Adamczyk, Marek
  • Afshani, Peyman
  • Akitaya, Hugo A.
  • Alstrup, Stephen
  • Amir, Amihood
  • Angelidakis, Haris
  • Antoniadis, Antonios
  • Apers, Simon
  • Arkin, Esther M.
  • Aumüller, Martin
  • Awasthi, Pranjal
  • Bampis, Evripidis
  • Bandyapadhyay, Sayan
  • Bartier, Valentin
  • Bauer, Ulrich
  • Baum, Moritz
  • Behnezhad, Soheil
  • Belovs, Aleksandrs
  • Bender, Michael A.
  • Bergougnoux, Benjamin
  • Berndt, Sebastian
  • Besa, Juan José
  • Biermeier, Felix
  • Birmpas, Georgios
  • Bläsius, Thomas
  • Blum, Avrim
  • Boissonnat, Jean-Daniel
  • Boneh, Itai
  • Bonnet, Édouard
  • Bousquet, Nicolas
  • Brand, Cornelius
  • Bringmann, Karl
  • Buchhold, Valentin
  • Byrka, Jaroslaw
  • Chakrabarty, Deeparnab
  • Charalampopoulos, Panagiotis
  • Chatziafratis, Vaggos
  • Chen, Jiehua
  • Chen, Jing
  • Chimani, Markus
  • Christiani, Tobias
  • Chudnovsky, Maria
  • Chun, Jinhee
  • Cohen-Addad, Vincent
  • Cristi, Andrés
  • Czerwinski, Wojciech
  • Czyzowicz, Jurek
  • Dahlgaard, Søren
  • Daknama, Rami
  • Da Lozzo, Giordano
  • Damerius, Christoph
  • Damian, Mirela
  • Dan, Chen
  • Demaine, Erik D.
  • Derakhshan, Mahsa
  • Dereniowski, Dariusz
  • Devillers, Olivier
  • Dietzfelbinger, Martin
  • Ding, Hu
  • Dinklage, Patrick
  • Dujmovic, Vida
  • Dutta, Kunal
  • Eiben, Eduard
  • Elbassioni, Khaled
  • Ellert, Jonas
  • Emek, Yuval
  • Epstein, Leah
  • Escoffier, Bruno
  • Fagerberg, Rolf
  • Farahbakhsh Touli, Elena
  • Ferraioli, Diodato
  • Filtser, Arnold
  • Fischer, Johannes
  • Flatland, Robin
  • Fomin, Fedor V.
  • Friedrich, Tobias
  • Ganian, Robert
  • Geissmann, Barbara
  • Georgiadis, Loukas
  • Giannis, Konstantinos
  • Gibney, Daniel
  • Glisse, Marc
  • Goldbraikh, Adam
  • Golovach, Petr A.
  • Goodrich, Michael T.
  • Goodrich, Timothy D.
  • Gottesbüren, Lars
  • Grandoni, Fabrizio
  • Gritzbach, Sascha
  • Haddadan, Arash
  • Hajiaghayi, MohammadTaghi
  • Hamann, Michael
  • Hammer, David
  • Herman, Grzegorz
  • Hermelin, Danny
  • Hitron, Yael
  • Hoeksma, Ruben
  • Hoffmann, Michael
  • Huang, Shenwei
  • Hübschle-Schneider, Lorenz
  • Iacono, John
  • Inamdar, Tanmay
  • Italiano, Giuseppe F.
  • Ito, Takehiro
  • Iwata, Yoichi
  • Jacob, Riko
  • Jansen, Bart M. P.
  • Jansen, Klaus
  • Jünger, Michael
  • Kaaser, Dominik
  • Kakimura, Naonori
  • Kamiyama, Naoyuki
  • Kanté, Mamadou Moustapha
  • Kantor, Erez
  • Kaplan, Haim
  • Karanasiou, Aikaterini
  • Karczmarz, Adam
  • Katzmann, Maximilian
  • Kikuchi, Kenya
  • Kisfaludi-Bak, Sándor
  • Klemz, Boris
  • Kling, Peter
  • Kloster, Kyle
  • Klost, Katharina
  • Knittel, Marina
  • Kobayashi, Yusuke
  • Kondratovsky, Eitan
  • Köppl, Dominik
  • Korman, Matias
  • Kostitsyna, Irina
  • Kowalik, Lukasz
  • Kratsch, Stefan
  • Krishnamurthy, Akshay
  • Kulik, Ariel
  • Kutten, Shay
  • Lacki, Jakub
  • Laura, Luigi
  • Lavallee, Brian
  • Lavi, Ron
  • Leucci, Stefano
  • Levin, Asaf
  • Li, Huan
  • Liu, Chih-Hung
  • Liu, Quanquan C.
  • Löffler, Maarten
  • Lokshtanov, Daniel
  • Maack, Marten
  • Makino, Kazuhisa
  • Mallach, Sven
  • Marcinkowski, Jan
  • Markakis, Evangelos
  • Masarík, Tomás
  • Mazumdar, Arya
  • McCauley, Samuel
  • McGregor, Andrew
  • Meesum, Syed M.
  • Meier, Adrian
  • Meierhans, Simon
  • Meyer, Ulrich
  • Mirzanezhad, Majid
  • Mouawad, Amer E.
  • Mucha, Marcin
  • Mulzer, Wolfgang
  • Muzi, Irene
  • Nadara, Wojciech
  • Nederlof, Jesper
  • Newman, Alantha
  • Nölke, Lukas
  • Okamoto, Yoshio
  • Ordyniak, Sebastian
  • Pagh, Rasmus
  • Pai, Shreyas
  • Palop, Belen
  • Pal, Soumyabrata
  • Panagiotou, Konstantinos
  • Panolan, Fahad
  • Parada, Irene
  • Parter, Merav
  • Pawlewicz, Jakub
  • Pelc, Andrzej
  • Penna, Paolo
  • Penschuck, Manuel
  • Pilipczuk, Marcin
  • Pilipczuk, Michal
  • Pissis, Solon P.
  • Räcke, Harald
  • Radermacher, Marcel
  • Radoszewski, Jakub
  • Rahul, C. S.
  • Ramanujan, M. S.
  • Rathod, Abhishek
  • Rau, Malin
  • Ravi, R.
  • Reisser, Simon
  • Roditty, Liam
  • Rohwedder, Lars
  • Rollin, Jonathan
  • Rudenko, Oleksandr
  • Rutter, Ignaz
  • Rzazewski, Pawel
  • Sacristán, Vera
  • Saha, Barna
  • Saleh, Hamed
  • Sanders, Peter
  • Sankowski, Piotr
  • Sarpatwar, Kanthi
  • Sauer, Jonas
  • Saurabh, Saket
  • Schäfer, Guido
  • Schewior, Kevin
  • Schieber, Baruch
  • Schlipf, Lena
  • Schmid, Stefan
  • Schulz, André
  • Schwartz, Roy
  • Seiferth, Paul
  • Shachnai, Hadas
  • Sharir, Micha
  • Shi, Yangguang
  • Singh, Shikha
  • Sitchinava, Nodari
  • Sorge, Manuel
  • Spirkl, Sophie
  • Spreer, Jonathan
  • Stausholm, Nina Mesing
  • Stöckel, Morten
  • Strash, Darren
  • Stumpf, Peter
  • Subramanian, Sanjay
  • Sullivan, Blair D.
  • Sun, He
  • Svensson, Ola
  • Swamy, Chaitanya
  • Teiller, Alexandre
  • Thankachan, Sharma V.
  • Thorup, Mikkel
  • Tokuyama, Takeshi
  • Tsakalidis, Konstantinos
  • Ueckerdt, Torsten
  • Vakilian, Ali
  • van de Kerkhof, Mees
  • van der Poel, Andrew
  • van Leeuwen, Erik Jan
  • van Renssen, André
  • Varadarajan, Kasturi
  • Ventre, Carmine
  • Vesterli, Michael
  • Vollmer, Michael
  • Wagner, Dorothea
  • Walzer, Stefan
  • Wang, Yusu
  • Wang, Zixiu
  • Wegner, Franziska
  • Wegrzycki, Karol
  • Wenk, Carola
  • Weyand, Christopher
  • Wiedera, Tilo
  • Wiese, Andreas
  • Wlodarczyk, Michal
  • Wolf, Matthias
  • Wulff-Nilsen, Christian
  • Yeheskel, Ran
  • Yu, Haikuo
  • Zanetti, Luca
  • Zehavi, Meirav
  • Zhong, Mingxian
  • Zündorf, Tobias
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Bender, Michael A. ; Svensson, Ola ; Herman, Grzegorz

    Abstract | Document (318 KB) | BibTeX

    Constant-Factor FPT Approximation for Capacitated k-Median
    Authors: Adamczyk, Marek ; Byrka, Jaroslaw ; Marcinkowski, Jan ; Meesum, Syed M. ; Wlodarczyk, Michal

    Abstract | Document (523 KB) | BibTeX

    Fragile Complexity of Comparison-Based Algorithms
    Authors: Afshani, Peyman ; Fagerberg, Rolf ; Hammer, David ; Jacob, Riko ; Kostitsyna, Irina ; Meyer, Ulrich ; Penschuck, Manuel ; Sitchinava, Nodari

    Abstract | Document (649 KB) | BibTeX

    Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers
    Authors: Akitaya, Hugo A. ; Arkin, Esther M. ; Damian, Mirela ; Demaine, Erik D. ; Dujmovic, Vida ; Flatland, Robin ; Korman, Matias ; Palop, Belen ; Parada, Irene ; van Renssen, André ; Sacristán, Vera

    Abstract | Document (1,339 KB) | BibTeX

    Constructing Light Spanners Deterministically in Near-Linear Time
    Authors: Alstrup, Stephen ; Dahlgaard, Søren ; Filtser, Arnold ; Stöckel, Morten ; Wulff-Nilsen, Christian

    Abstract | Document (590 KB) | BibTeX

    Repetition Detection in a Dynamic String
    Authors: Amir, Amihood ; Boneh, Itai ; Charalampopoulos, Panagiotis ; Kondratovsky, Eitan

    Abstract | Document (660 KB) | BibTeX

    Longest Common Substring Made Fully Dynamic
    Authors: Amir, Amihood ; Charalampopoulos, Panagiotis ; Pissis, Solon P. ; Radoszewski, Jakub

    Abstract | Document (598 KB) | BibTeX

    Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem
    Authors: Angelidakis, Haris ; Awasthi, Pranjal ; Blum, Avrim ; Chatziafratis, Vaggos ; Dan, Chen

    Abstract | Document (570 KB) | BibTeX

    On the Complexity of Anchored Rectangle Packing
    Authors: Antoniadis, Antonios ; Biermeier, Felix ; Cristi, Andrés ; Damerius, Christoph ; Hoeksma, Ruben ; Kaaser, Dominik ; Kling, Peter ; Nölke, Lukas

    Abstract | Document (760 KB) | BibTeX

    Quantum Walk Sampling by Growing Seed Sets
    Authors: Apers, Simon

    Abstract | Document (475 KB) | BibTeX

    PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors
    Authors: Aumüller, Martin ; Christiani, Tobias ; Pagh, Rasmus ; Vesterli, Michael

    Abstract | Document (795 KB) | BibTeX

    Online Multistage Subset Maximization Problems
    Authors: Bampis, Evripidis ; Escoffier, Bruno ; Schewior, Kevin ; Teiller, Alexandre

    Abstract | Document (492 KB) | BibTeX

    A Constant Approximation for Colorful k-Center
    Authors: Bandyapadhyay, Sayan ; Inamdar, Tanmay ; Pai, Shreyas ; Varadarajan, Kasturi

    Abstract | Document (521 KB) | BibTeX

    Parametrized Complexity of Expansion Height
    Authors: Bauer, Ulrich ; Rathod, Abhishek ; Spreer, Jonathan

    Abstract | Document (545 KB) | BibTeX

    UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution
    Authors: Baum, Moritz ; Buchhold, Valentin ; Sauer, Jonas ; Wagner, Dorothea ; Zündorf, Tobias

    Abstract | Document (481 KB) | BibTeX

    Streaming and Massively Parallel Algorithms for Edge Coloring
    Authors: Behnezhad, Soheil ; Derakhshan, Mahsa ; Hajiaghayi, MohammadTaghi ; Knittel, Marina ; Saleh, Hamed

    Abstract | Document (504 KB) | BibTeX

    Quantum Algorithms for Classical Probability Distributions
    Authors: Belovs, Aleksandrs

    Abstract | Document (443 KB) | BibTeX

    More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints
    Authors: Bergougnoux, Benjamin ; Kanté, Mamadou Moustapha

    Abstract | Document (571 KB) | BibTeX

    Online Bin Covering with Limited Migration
    Authors: Berndt, Sebastian ; Epstein, Leah ; Jansen, Klaus ; Levin, Asaf ; Maack, Marten ; Rohwedder, Lars

    Abstract | Document (504 KB) | BibTeX

    Computing k-Modal Embeddings of Planar Digraphs
    Authors: Besa, Juan José ; Da Lozzo, Giordano ; Goodrich, Michael T.

    Abstract | Document (814 KB) | BibTeX

    Cost Sharing over Combinatorial Domains: Complement-Free Cost Functions and Beyond
    Authors: Birmpas, Georgios ; Markakis, Evangelos ; Schäfer, Guido

    Abstract | Document (533 KB) | BibTeX

    Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs
    Authors: Bläsius, Thomas ; Friedrich, Tobias ; Katzmann, Maximilian ; Meyer, Ulrich ; Penschuck, Manuel ; Weyand, Christopher

    Abstract | Document (717 KB) | BibTeX

    Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets
    Authors: Boissonnat, Jean-Daniel ; Devillers, Olivier ; Dutta, Kunal ; Glisse, Marc

    Abstract | Document (514 KB) | BibTeX

    Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
    Authors: Bonnet, Édouard ; Iwata, Yoichi ; Jansen, Bart M. P. ; Kowalik, Lukasz

    Abstract | Document (609 KB) | BibTeX

    Linear Transformations Between Colorings in Chordal Graphs
    Authors: Bousquet, Nicolas ; Bartier, Valentin

    Abstract | Document (664 KB) | BibTeX

    Patching Colors with Tensors
    Authors: Brand, Cornelius

    Abstract | Document (488 KB) | BibTeX

    On Geometric Set Cover for Orthants
    Authors: Bringmann, Karl ; Kisfaludi-Bak, Sándor ; Pilipczuk, Michal ; van Leeuwen, Erik Jan

    Abstract | Document (1,036 KB) | BibTeX

    Simpler and Better Algorithms for Minimum-Norm Load Balancing
    Authors: Chakrabarty, Deeparnab ; Swamy, Chaitanya

    Abstract | Document (476 KB) | BibTeX

    On Computing Centroids According to the p-Norms of Hamming Distance Vectors
    Authors: Chen, Jiehua ; Hermelin, Danny ; Sorge, Manuel

    Abstract | Document (779 KB) | BibTeX

    Non-Cooperative Rational Interactive Proofs
    Authors: Chen, Jing ; McCauley, Samuel ; Singh, Shikha

    Abstract | Document (532 KB) | BibTeX

    Stronger ILPs for the Graph Genus Problem
    Authors: Chimani, Markus ; Wiedera, Tilo

    Abstract | Document (643 KB) | BibTeX

    Complexity of C_k-Coloring in Hereditary Classes of Graphs
    Authors: Chudnovsky, Maria ; Huang, Shenwei ; Rzazewski, Pawel ; Spirkl, Sophie ; Zhong, Mingxian

    Abstract | Document (546 KB) | BibTeX

    Consistent Digital Curved Rays and Pseudoline Arrangements
    Authors: Chun, Jinhee ; Kikuchi, Kenya ; Tokuyama, Takeshi

    Abstract | Document (823 KB) | BibTeX

    Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs
    Authors: Cohen-Addad, Vincent ; Pilipczuk, Marcin ; Pilipczuk, Michal

    Abstract | Document (776 KB) | BibTeX

    Improved Bounds for the Excluded-Minor Approximation of Treedepth
    Authors: Czerwinski, Wojciech ; Nadara, Wojciech ; Pilipczuk, Marcin

    Abstract | Document (665 KB) | BibTeX

    Building a Nest by an Automaton
    Authors: Czyzowicz, Jurek ; Dereniowski, Dariusz ; Pelc, Andrzej

    Abstract | Document (552 KB) | BibTeX

    Robustness of Randomized Rumour Spreading
    Authors: Daknama, Rami ; Panagiotou, Konstantinos ; Reisser, Simon

    Abstract | Document (537 KB) | BibTeX

    Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
    Authors: Demaine, Erik D. ; Goodrich, Timothy D. ; Kloster, Kyle ; Lavallee, Brian ; Liu, Quanquan C. ; Sullivan, Blair D. ; Vakilian, Ali ; van der Poel, Andrew

    Abstract | Document (592 KB) | BibTeX

    Dense Peelable Random Uniform Hypergraphs
    Authors: Dietzfelbinger, Martin ; Walzer, Stefan

    Abstract | Document (645 KB) | BibTeX

    Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications
    Authors: Dietzfelbinger, Martin ; Walzer, Stefan

    Abstract | Document (637 KB) | BibTeX

    Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction
    Authors: Ding, Hu ; Yu, Haikuo ; Wang, Zixiu

    Abstract | Document (1,300 KB) | BibTeX

    Bidirectional Text Compression in External Memory
    Authors: Dinklage, Patrick ; Ellert, Jonas ; Fischer, Johannes ; Köppl, Dominik ; Penschuck, Manuel

    Abstract | Document (864 KB) | BibTeX

    Bisection of Bounded Treewidth Graphs by Convolutions
    Authors: Eiben, Eduard ; Lokshtanov, Daniel ; Mouawad, Amer E.

    Abstract | Document (503 KB) | BibTeX

    Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
    Authors: Elbassioni, Khaled ; Makino, Kazuhisa

    Abstract | Document (605 KB) | BibTeX

    Online Disjoint Set Cover Without Prior Knowledge
    Authors: Emek, Yuval ; Goldbraikh, Adam ; Kantor, Erez

    Abstract | Document (524 KB) | BibTeX

    Bayesian Generalized Network Design
    Authors: Emek, Yuval ; Kutten, Shay ; Lavi, Ron ; Shi, Yangguang

    Abstract | Document (555 KB) | BibTeX

    Obviously Strategyproof Mechanisms for Machine Scheduling
    Authors: Ferraioli, Diodato ; Meier, Adrian ; Penna, Paolo ; Ventre, Carmine

    Abstract | Document (528 KB) | BibTeX

    Going Far From Degeneracy
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (544 KB) | BibTeX

    Group Activity Selection with Few Agent Types
    Authors: Ganian, Robert ; Ordyniak, Sebastian ; Rahul, C. S.

    Abstract | Document (601 KB) | BibTeX

    Optimal Sorting with Persistent Comparison Errors
    Authors: Geissmann, Barbara ; Leucci, Stefano ; Liu, Chih-Hung ; Penna, Paolo

    Abstract | Document (678 KB) | BibTeX

    Dynamic Dominators and Low-High Orders in DAGs
    Authors: Georgiadis, Loukas ; Giannis, Konstantinos ; Italiano, Giuseppe F. ; Karanasiou, Aikaterini ; Laura, Luigi

    Abstract | Document (732 KB) | BibTeX

    On the Hardness and Inapproximability of Recognizing Wheeler Graphs
    Authors: Gibney, Daniel ; Thankachan, Sharma V.

    Abstract | Document (856 KB) | BibTeX

    Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
    Authors: Gottesbüren, Lars ; Hamann, Michael ; Wagner, Dorothea

    Abstract | Document (1,275 KB) | BibTeX

    Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
    Authors: Grandoni, Fabrizio ; Kratsch, Stefan ; Wiese, Andreas

    Abstract | Document (557 KB) | BibTeX

    Packing Cars into Narrow Roads: PTASs for Limited Supply Highway
    Authors: Grandoni, Fabrizio ; Wiese, Andreas

    Abstract | Document (510 KB) | BibTeX

    Engineering Negative Cycle Canceling for Wind Farm Cabling
    Authors: Gritzbach, Sascha ; Ueckerdt, Torsten ; Wagner, Dorothea ; Wegner, Franziska ; Wolf, Matthias

    Abstract | Document (829 KB) | BibTeX

    Towards Improving Christofides Algorithm for Half-Integer TSP
    Authors: Haddadan, Arash ; Newman, Alantha

    Abstract | Document (510 KB) | BibTeX

    Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons
    Authors: Hitron, Yael ; Parter, Merav

    Abstract | Document (1,768 KB) | BibTeX

    Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian
    Authors: Hoffmann, Michael ; Klemz, Boris

    Abstract | Document (657 KB) | BibTeX

    Parallel Weighted Random Sampling
    Authors: Hübschle-Schneider, Lorenz ; Sanders, Peter

    Abstract | Document (658 KB) | BibTeX

    External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms
    Authors: Iacono, John ; Jacob, Riko ; Tsakalidis, Konstantinos

    Abstract | Document (509 KB) | BibTeX

    Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
    Authors: Ito, Takehiro ; Kakimura, Naonori ; Kamiyama, Naoyuki ; Kobayashi, Yusuke ; Okamoto, Yoshio

    Abstract | Document (1,044 KB) | BibTeX

    Closing the Gap for Pseudo-Polynomial Strip Packing
    Authors: Jansen, Klaus ; Rau, Malin

    Abstract | Document (453 KB) | BibTeX

    Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization
    Authors: Jünger, Michael ; Mallach, Sven

    Abstract | Document (773 KB) | BibTeX

    Triangles and Girth in Disk Graphs and Transmission Graphs
    Authors: Kaplan, Haim ; Klost, Katharina ; Mulzer, Wolfgang ; Roditty, Liam ; Seiferth, Paul ; Sharir, Micha

    Abstract | Document (515 KB) | BibTeX

    Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
    Authors: Karczmarz, Adam ; Lacki, Jakub

    Abstract | Document (531 KB) | BibTeX

    Min-Cost Flow in Unit-Capacity Planar Graphs
    Authors: Karczmarz, Adam ; Sankowski, Piotr

    Abstract | Document (566 KB) | BibTeX

    Global Curve Simplification
    Authors: van de Kerkhof, Mees ; Kostitsyna, Irina ; Löffler, Maarten ; Mirzanezhad, Majid ; Wenk, Carola

    Abstract | Document (771 KB) | BibTeX

    Trace Reconstruction: Generalized and Parameterized
    Authors: Krishnamurthy, Akshay ; Mazumdar, Arya ; McGregor, Andrew ; Pal, Soumyabrata

    Abstract | Document (603 KB) | BibTeX

    Generalized Assignment via Submodular Optimization with Reserved Capacity
    Authors: Kulik, Ariel ; Sarpatwar, Kanthi ; Schieber, Baruch ; Shachnai, Hadas

    Abstract | Document (565 KB) | BibTeX

    Resilient Dictionaries for Randomly Unreliable Memory
    Authors: Leucci, Stefano ; Liu, Chih-Hung ; Meierhans, Simon

    Abstract | Document (613 KB) | BibTeX

    Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
    Authors: Li, Huan ; Sun, He ; Zanetti, Luca

    Abstract | Document (568 KB) | BibTeX

    Packing Directed Circuits Quarter-Integrally
    Authors: Masarík, Tomás ; Muzi, Irene ; Pilipczuk, Marcin ; Rzazewski, Pawel ; Sorge, Manuel

    Abstract | Document (707 KB) | BibTeX

    Equal-Subset-Sum Faster Than the Meet-in-the-Middle
    Authors: Mucha, Marcin ; Nederlof, Jesper ; Pawlewicz, Jakub ; Wegrzycki, Karol

    Abstract | Document (525 KB) | BibTeX

    Hardness of Bichromatic Closest Pair with Jaccard Similarity
    Authors: Pagh, Rasmus ; Stausholm, Nina Mesing ; Thorup, Mikkel

    Abstract | Document (513 KB) | BibTeX

    Compact Oblivious Routing
    Authors: Räcke, Harald ; Schmid, Stefan

    Abstract | Document (443 KB) | BibTeX

    Geometric Crossing-Minimization - A Scalable Randomized Approach
    Authors: Radermacher, Marcel ; Rutter, Ignaz

    Abstract | Document (709 KB) | BibTeX

    An Approximate Kernel for Connected Feedback Vertex Set
    Authors: Ramanujan, M. S.

    Abstract | Document (778 KB) | BibTeX

    Multicommodity Multicast, Wireless and Fast
    Authors: Ravi, R. ; Rudenko, Oleksandr

    Abstract | Document (3,231 KB) | BibTeX

    Recognizing Planar Laman Graphs
    Authors: Rollin, Jonathan ; Schlipf, Lena ; Schulz, André

    Abstract | Document (561 KB) | BibTeX

    Simultaneous Representation of Proper and Unit Interval Graphs
    Authors: Rutter, Ignaz ; Strash, Darren ; Stumpf, Peter ; Vollmer, Michael

    Abstract | Document (1,015 KB) | BibTeX

    Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost
    Authors: Saha, Barna ; Subramanian, Sanjay

    Abstract | Document (546 KB) | BibTeX

    Graph Balancing with Orientation Costs
    Authors: Schwartz, Roy ; Yeheskel, Ran

    Abstract | Document (595 KB) | BibTeX

    FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees
    Authors: Farahbakhsh Touli, Elena ; Wang, Yusu

    Abstract | Document (845 KB) | BibTeX

    		  



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