ICALP 2023

Session

Track A-1

Jul 11, 2023, 10:30 AM

Seminar Room 1+2 (HNF)

Conveners

Track A-1: Efficient algorithms (+ parameterized complexity)

• Hans Bodlaender (Session Chair)

Track A-1: AGT/Social choice

• Anna Karlin (Session Chair)

Track A-1: Approximation Algorithms

• Fabrizio Grandoni (Session Chair)

Track A-1: Quantum computing

• Alexandru Gheorghiu (Session Chair)

Track A-1: Dynamic algorithms

• Thatchaphol Saranurak (Session Chair)

Track A-1: Efficient algorithms

• Rasmus Kyng (Session Chair)

4. Approximating Long Cycle Above Dirac’s Guarantee

Kirill Simonov

7/11/23, 10:30 AM

Fedor Fomin, Petr Golovach, Danil Sagunov and Kirill Simonov

Abstract: Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit “natural” guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF...

5. Breaking the All Subsets Barrier for Min $k$-Cut

Vaishali Surianarayanan

7/11/23, 10:55 AM

Vaishali Surianarayanan, Daniel Lokshtanov and Saket Saurabh

Abstract: In the {\sc Min $k$-Cut} problem, the input is a graph $G$ and an integer $k$. The task is to find a partition of the vertex set of $G$ into $k$ parts, while minimizing the number of edges that go between different parts of the partition. The problem is NP-complete, and admits a simple $3^n \cdot n^{O(1)}$ time dynamic...

6. Compound Logics for Modification Problems

Giannos Stamoulis

7/11/23, 11:20 AM

Fedor Fomin, Petr Golovach, Ignasi Sau, Giannos Stamoulis and Dimitrios M. Thilikos

Abstract: We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator...

7. Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems

Shi Li

7/11/23, 11:45 AM

Shi Li

Abstract: We study nearly-linear time approximation algorithms for non-preemptive scheduling problems in two settings: the unrelated machine setting, and the identical machine with job precedence constraints setting, under the well-studied objectives such as makespan and weighted completion time. For many problems, we develop nearly-linear time approximation algorithms with...

11. New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling

Spencer Compton

7/11/23, 12:10 PM

Spencer Compton, Slobodan Mitrović and Ronitt Rubinfeld

Abstract: Interval scheduling is a basic problem in the theory of algorithms and a classical task in combinatorial optimization.
We develop a set of techniques for partitioning and grouping jobs based on their starting and ending times, that enable us to view an instance of interval scheduling on \emph{many}
jobs as a union...

32. Low Sample Complexity Participatory Budgeting

Sahasrajit Sarmasarkar

7/11/23, 3:30 PM

Mohak Goyal, Sukolsak Sakshuwong, Sahasrajit Sarmasarkar and Ashish Goel

Abstract: We study low sample complexity mechanisms in participatory budgeting (PB), where each voter votes for a preferred allocation of funds to various projects, subject to project costs and total spending constraints. We analyze the distortion that PB mechanisms introduce relative to the minimum-social-cost outcome...

33. Approximation Algorithms for Envy-Free Cake Division with Connected Pieces

Pooja Kulkarni

7/11/23, 3:55 PM

Siddharth Barman and Pooja Kulkarni

Abstract: Cake cutting is a classic model for studying fair division of a heterogeneous, divisible resource among agents with individual preferences. Addressing cake division under a typical requirement that each agent must receive a connected piece of the cake, we develop approximation algorithms for finding envy-free (fair) cake divisions. In...

34. Truthful Matching with Online Items and Offline Agents

Simon Mauras

7/11/23, 4:20 PM

Michal Feldman, Federico Fusco, Simon Mauras and Rebecca Reiffenhäuser

Abstract: We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multi-parameter) setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where...

35. Stable Matching: Choosing Which Proposals to Make

Ishan Agarwal

7/11/23, 4:45 PM

Ishan Agarwal and Richard Cole

Abstract: To guarantee all agents are matched, the classic Deferred Acceptance algorithm needs complete preference lists. In practice, preference lists are short, yet stable matching still works well. This raises two questions:

Why does it work well?
Which proposals should agents include in their preference lists?

We study these questions in a model,...

52. Finding Almost Tight Witness Trees

Dylan Hyatt-Denesik

7/12/23, 10:30 AM

Dylan Hyatt-Denesik, Afrouz Ameli and Laura Sanita

Abstract: This paper addresses a graph optimization problem, called the Witness Tree problem, which seeks a spanning tree of a graph minimizing a certain non-linear objective function. This problem is of interest because it plays a crucial role in the analysis of the best approximation algorithms for two fundamental network design problems:...

53. Matching Augmentation via Simultaneous Contractions

Felix Hommelsheim

7/12/23, 10:55 AM

Mohit Garg, Felix Hommelsheim and Nicole Megow

Abstract: We consider the matching augmentation problem (MAP), where a matching of a graph needs to be extended into a $2$-edge-connected spanning subgraph by adding the minimum number of edges to it. We present a polynomial-time algorithm with an approximation ratio of $13/8 = 1.625$ improving upon an earlier $5/3$-approximation. The...

54. Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions

Ishan Bansal

7/12/23, 11:20 AM

Ishan Bansal, Joe Cheriyan, Logan Grout and Sharat Ibrahimpur

Abstract: We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Combinatorica 15(3):435-454, 1995). Williamson, et al., prove an approximation guarantee of two for connectivity...

55. An $O(\log k)$-Approximation for Directed Steiner Tree in Planar Graphs

Ramin Mousavi

7/12/23, 11:45 AM

Zachary Friggstad and Ramin Mousavi

Abstract: We present an $O(\log k)$-approximation for both the edge-weighted and node-weighted versions of \DST in planar graphs where $k$ is the number of terminals. We extend our approach to \MDST\footnote{In general graphs \MDST and \DST are easily seen to be equivalent but in planar graphs this is not the case necessarily.}, in which we get a...

56. A Tight $(1.5+\epsilon)$-Approximation for Unsplittable Capacitated Vehicle Routing on Trees

Hang Zhou

7/12/23, 12:10 PM

Claire Mathieu and Hang Zhou

Abstract: In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the root of the tree such that...

77. Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

Ronald de Wolf

7/13/23, 10:30 AM

Yanlin Chen and Ronald de Wolf

Abstract: Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector $\theta\in\mathbb{R}^d$ of coefficients is constrained in either $\ell_1$-norm (for Lasso) or in $\ell_2$-norm (for Ridge). We study the complexity of quantum algorithms for finding...

78. Simulating Markovian open quantum systems using higher-order series expansion

Chunhao Wang

7/13/23, 10:55 AM

Xiantao Li and Chunhao Wang

Abstract: We present an efficient quantum algorithm for simulating the dynamics of Markovian open quantum systems. The performance of our algorithm is similar to the previous state-of-the-art quantum algorithm, i.e., it scales linearly in evolution time and poly-logarithmically in inverse precision. However, our algorithm is conceptually cleaner, and it only uses...

79. Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians

Thiago Bergamaschi

7/13/23, 11:20 AM

Thiago Bergamaschi

Abstract: The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum $k$-Local Hamiltonians....

80. Improved Hardness Results for the Guided Local Hamiltonian Problem

Ryu Hayakawa

7/13/23, 11:45 AM

Ryu Hayakawa, Jordi Weggemans, Tomoyuki Morimae, Chris Cade, Marten Folkertsma, Sevag Gharibian and Francois Le Gall

Abstract: Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced...

81. Cumulative Memory Lower Bounds for Randomized and Quantum Computation

Niels Kornerup

7/13/23, 12:10 PM

Paul Beame and Niels Kornerup

Abstract: Cumulative memory---the sum of space used over the steps of a computation---is a fine-grained measure of time-space complexity that was introduced to analyze cryptographic applications more precisely. It is a more accurate cost measure for algorithms with infrequent spikes in memory usage in the context of technologies such as cloud computing that...

102. Optimal Decremental Connectivity in Non-Sparse Graphs

Adam Karczmarz

7/13/23, 4:00 PM

Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis, Peter Rasmussen and Mikkel Thorup

Abstract: We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomized and processes any sequence of edge deletions in $O(m + n~poly(\log n))$ total time. Interspersed with...

103. Dynamic Averaging Load Balancing on Arbitrary Graphs

Lukas Hintze

7/13/23, 4:25 PM

Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour, Dominik Kaaser and Malin Rau

Abstract: In this paper we study dynamic averaging load balancing on general graphs.
We consider infinite time and dynamic processes, where in every step new load items are assigned to randomly chosen nodes.
A matching is chosen, and the load is averaged over the edges of that matching.
We analyze the...

104. Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs

Adam Karczmarz

7/13/23, 4:50 PM

Adam Karczmarz and Piotr Sankowski

Abstract: We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with O~(mn^{4/5}) worst-case update time processing arbitrary s,t-distance queries in O~(n^{4/5}) time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of...

114. Fast approximation of search trees on trees with centroid trees

Benjamin Aram Berendsohn, Laszlo Kozma

7/14/23, 10:30 AM

Benjamin Aram Berendsohn, Ishay Golinsky, Haim Kaplan and Laszlo Kozma

Abstract: Search trees on trees (STTs) generalize the fundamental binary search tree (BST) data structure: in STTs the underlying search space is an arbitrary tree, whereas in BSTs it is a path. An optimal BST of size $n$ can be computed for a given distribution of queries in $O(n^2)$ time [Knuth, Acta Inf. 1971] and...

115. Faster Matroid Partition Algorithms

Tatsuya Terao

7/14/23, 10:55 AM

Tatsuya Terao

Abstract: In the matroid partitioning problem, we are given $k$ matroids $\mathcal{M}_1 = (V, \mathcal{I}_1), \dots , \mathcal{M}_k = (V, \mathcal{I}_k)$ defined over a common ground set $V$ of $n$ elements, and we need to find a partitionable set $S \subseteq V$ of largest possible cardinality, denoted by $p$. Here, a set $S \subseteq V$ is called partitionable if there...

116. Faster submodular maximization for several classes of matroids

Da Wei Zheng

7/14/23, 11:20 AM

Monika Henzinger, Paul Liu, Jan Vondrák and Da Wei Zheng

Abstract: The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been investigated extensively due to its algorithmic properties and expressive...

117. On computing the vertex connectivity of 1-plane graphs

Karthik Murali

7/14/23, 11:45 AM

Karthik Murali and Therese Biedl

Abstract: A graph is called 1-plane if it has an embedding in the plane where each edge is crossed at most once by another edge. A crossing of a 1-plane graph is called an X-crossing if the endpoints of the crossing pair of edges induce a matching. In this paper, we show how to compute the vertex connectivity of a 1-plane graph G without X-crossings in...

118. An Efficient Algorithm for All-Pairs Bounded Edge Connectivity

Shyan Akmal

7/14/23, 12:10 PM

Shyan Akmal and Ce Jin

Abstract: Our work concerns algorithms for a variant of \textsf{Maximum Flow} in unweighted graphs. In the All-Pairs Connectivity (APC) problem, we are given a graph G on n vertices and m edges, and are tasked with computing the size of a minimum st-cut in G for all pairs of vertices (s,t). Significant algorithmic breakthroughs have recently shows that over undirected...