2.8k citations
- Max Planck SocietyDE261 papers
- Saarland UniversityDE124 papers
- Technische Universität BerlinDE55 papers
- Centre National de la Recherche ScientifiqueFR41 papers
- Korea UniversityKR41 papers
- Stanford UniversityUS25 papers
- Institut national de recherche en sciences et technologies du numériqueFR24 papers
- ETH ZurichCH21 papers
- Helmholtz Center for Information SecurityDE20 papers
- Technical University of MunichDE20 papers
- Université de LorraineFR17 papers
- University of LuxembourgLU16 papers
132 papers · 1 filter
Faster Exponential Algorithms for Multi-Machine Scheduling Problems
Anubhav Dhar, Anita Dürr, Ahmed Ghazy +2
Minimizing the weighted completion times () and weighted number of tardy jobs () on multiple identical machines are two classical NP-har…
On the Hardness Hierarchy for the Complexity in the Word RAM
Dominik Kempa, Tomasz Kociumaka
In this work, we study the relative hardness of fundamental problems with state-of-the-art word RAM algorithms that take time for instances described in …
Lempel-Ziv (LZ77) Factorization in Sublinear Time
Dominik Kempa, Tomasz Kociumaka
Lempel-Ziv (LZ77) factorization is a fundamental problem in string processing: Greedily partition a given string from left to right into blocks (called phrases) so that each ph…
Online Matching on -Uniform Hypergraphs
Sander Borst, Danish Kashaev, Zhuan Khye Koh
The online matching problem was introduced by Karp, Vazirani and Vazirani (STOC 1990) on bipartite graphs with vertex arrivals. It is well-known that the optimal competitive ratio…
Parameterized algorithms for block-structured integer programs with large entries
Jana Cslovjecsek, Martin Koutecký, Alexandra Lassota +2
We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form $\{A_i \mathbf{x} + D_i \mathbf{y}_i = \mathbf…
A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
Sophia Saller, Jana Koehler, Andreas Karrenbauer
The traveling salesman (or salesperson) problem, short TSP, is a problem of strong interest to many researchers from mathematics, economics, and computer science. Manifold TSP vari…