ARCO (Algorithmic Research Cooperation around Øresund) is a network for promoting collaboration in research within algorithms around the Øresund Region. The idea is to meet twice per year for a one-day workshop.
On April 21st 2023, ARCO will be hosted by KU.
Location: HCØ (Universitetsparken 5, i.e. next to DIKU) -- Auditorium 1
09:30 - 10:00 Arrivals and welcome (Coffee served)
10:00 - 10:20 Riko Jacob -- Universal Sorting: Finding a DAG using Priced Comparisons
10:20 - 10:40 Niv Dayan -- Scaling Database Storage Engines
10:40 - 11:00 Tamalika Mukherjee -- Differentially Private L2-Heavy Hitters in the Sliding Window Model
11:00 - 11:20 Coffee break
11:20 - 11:40 Magnus Berg -- Online Minimum Spanning Trees with Weight Predictions
11:40 - 12:00 Bengt J. Nilsson -- Online Bin Covering of Vectors with a Little Advice
12:00 - 13:00 Lunch
13:00 - 13:20 Mikkel Abrahamsen -- Partitioning a Polygon Into Small Pieces
13:20 - 13:40 Aniket Basu Roy -- Covering Orthogonal Polygons with Rectangles
13:40 - 14:00 Coffee break
14:00 - 14:20 Hanwen Zhang -- Minimum Star Partitions of Simple Polygons in Polynomial Time
14:20 - 14:40 Marcin Pilipczuk -- On metric embeddings of planar graphs
14:40 - 15:00 Coffee break
15:00 - 15:20 Mingmou Liu -- Lower Bounds for Sparse Oblivious Subspace Embeddings
15:20 - 15:40 Zhile Jiang -- Computing better approximate pure Nash equilibria in cut games via semidefinite programming
16:30 - Pizza and Open Problems
Riko Jacob -- Universal Sorting: Finding a DAG using Priced Comparisons
We resolve two open problems in sorting with priced information, introduced by [Charikar, Fagin, Guruswami, Kleinberg, Raghavan, Sahai (CFGKRS), STOC 2000]. In this setting, different comparisons have different (potentially infinite) costs. The goal is to sort with small competitive ratio (algorithmic cost divided by cheapest proof). 1) When all costs are in {0,1,n,∞}, we give an algorithm that has O˜(n^3/4) competitive ratio. Our algorithm generalizes the algorithms for generalized sorting (all costs are either 1 or ∞), a version initiated by [Huang, Kannan, Khanna, FOCS 2011] and addressed recently by [Kuszmaul, Narayanan, FOCS 2021]. 2) We answer the problem of bichromatic sorting posed by [CFGKRS]: The input is split into A and B, and A−A and B−B comparisons are more expensive than an A−B comparisons. We give a randomized algorithm with a O(polylog n) competitive ratio. These results are obtained by introducing the universal sorting problem, which generalizes the existing framework in two important ways. We remove the promise of a directed Hamiltonian path in the DAG of all comparisons. Instead, we require that an algorithm outputs the transitive reduction of the DAG. For bichromatic sorting, when A−A and B−B comparisons cost ∞, this generalizes the well-known nuts and bolts problem. We initiate an instance-based study of the universal sorting problem. Our definition of instance-optimality is inherently more algorithmic than that of the competitive ratio in that we compare the cost of a candidate algorithm to the cost of the optimal instance-aware algorithm. This unifies existing lower bounds, and opens up the possibility of an O(1)-instance optimal algorithm for the bichromatic version.
Niv Dayan -- Scaling Database Storage Engines
Our society is generating data at an exponential rate. Storage engines, such as Google’s Bigtable, Amazon’s DynamoDB, and Facebook’s RocksDB, are the software components that maintain this data and facilitate the extraction of information from it. But exponential data growth exacts a toll on these engines: as the data grows, performance deteriorates. In turn, the applications that run on top must spend disproportionately more time, energy and hardware to, say, complete a transaction on a blockchain, train a deep learning model, or upload a photo to the cloud. This talk will rethink the architecture of modern storage engines and their underlying data structures to confront the reality of exponential data growth. We will explore new designs that are more scalable and how to generalize them into a universal, tunable data structure that can optimize for diverse applications.
Tamalika Mukherjee -- Differentially Private L2-Heavy Hitters in the Sliding Window Model
The data management of large companies often prioritize more recent data, as a source of higher accuracy prediction than outdated data. For example, the Facebook data policy retains user search histories for 6 months while the Google data retention policy states that browser information may be stored for up to 9 months. These policies are captured by the sliding window model, in which only the most recent W statistics form the underlying dataset. In this paper, we consider the problem of privately releasing the L2-heavy hitters in the sliding window model, which include Lp-heavy hitters for p<=2 and in some sense are the strongest possible guarantees that can be achieved using polylogarithmic space, but cannot be handled by existing techniques due to the sub-additivity of the L2 norm. Moreover, existing non-private sliding window algorithms use the smooth histogram framework, which has high sensitivity. To overcome these barriers, we introduce the first differentially private algorithm for L2-heavy hitters in the sliding window model by initiating a number of L2-heavy hitter algorithms across the stream with significantly lower threshold. Similarly, we augment the algorithms with an approximate frequency tracking algorithm with significantly higher accuracy. We then use smooth sensitivity and statistical distance arguments to show that we can add noise proportional to an estimation of the L2 norm. To the best of our knowledge, our techniques are the first to privately release statistics that are related to a sub-additive function in the sliding window model and may be of independent interest to future differentially private algorithmic design in the sliding window model.
Magnus Berg -- Online Minimum Spanning Trees with Weight Predictions
We consider the minimum spanning tree problem with predictions, using the weight-arrival model, i.e., the graph is given, together with predictions for the weights of all edges. Then the actual weights arrive one at a time and an irrevocable decision must be made regarding whether or not the edge should be included into the spanning tree. In order to assess the quality of our algorithms, we define an appropriate error measure and analyze the performance of the algorithms as a function of the error. We prove that, according to competitive analysis, the simplest algorithm, Follow-the-Predictions, is optimal. However, intuitively, one should be able to do better, and we present a greedy variant of Follow-the-Predictions. In analyzing that algorithm, we believe we present the first random order analysis of a non-trivial online algorithm with predictions, by which we obtain an algorithmic separation. This may be useful for distinguishing between algorithms for other problems when Follow-the-Predictions is optimal according to competitive analysis.
Bengt J. Nilsson -- Online Bin Covering of Vectors with a Little Advice
We investigate the bin covering problem in one and two dimensions in the framework of online computation with advice. Bin covering is a dual problem to bin packing where, given an input sequence of vectors, the objective is to maximize the number of bins packed with vectors to above a given threshold value, usually set to 1.
In particular, for the one dimensional case, we show a 2/3-competitive strategy using O(b+log n) bits of advice, where b is the number of bits used to encode a rational value and n is the length of the input sequence. We also give a 5/9-competitive strategy using O(loglog n) bits of advice in this case.
For the two-dimensional case, we obtain a 1/3-competitive strategy using O(loglog n) bits of advice.
Mikkel Abrahamsen -- Partitioning a Polygon Into Small Pieces
We study the problem of partitioning a given simple polygon $P$ into a minimum number of connected polygonal pieces, each of bounded size. We describe a general technique for constructing such partitions which works for several notions of `bounded size,' namely that each piece must be contained in a unit square or unit disk, or that each piece has bounded perimeter, straight-line diameter or geodesic diameter. It seems out of reach to compute optimal partitions; even in extremely restricted cases such as when $P$ is a square. Our main result is to develop $O(1)$-approximation algorithms, which means that the number of pieces in the produced partition is at most a constant factor larger than the cardinality of a minimum partition. Existing algorithms~[Damian and Pemmaraju, 2004] do not allow Steiner points, which means that all corners of the produced pieces must also be corners of $P$. This has the disappointing consequence that a partition does often not exist, whereas our algorithms always produce useful partitions. Furthermore, an optimal partition without Steiner points may require $\Omega(n)$ pieces for polygons where a partition consisting of just $2$ pieces exists when Steiner points are allowed. The problems are motivated by practical settings in manufacturing, finite element analysis, collision detection and vehicle routing.
Aniket Basu Roy -- Covering Orthogonal Polygons with Rectangles
We survey the problem of Covering Orthogonal Polygons with Rectangles. For the general problem, the best-known approximation factor achieved in polynomial time is O(\sqrt{\log n}) [Kumar and Ramesh '99], whereas, when the polygons do not have holes, there is a 2-approximation algorithm [Franzblau '89]. Furthermore, we discuss a conjecture by Paul Erdős on a related problem [Chaiken et al. '81]. The problem is also studied when we are only interested in covering the boundary of the polygons. For the general polygons, the best-known approximation factor is 4, and the problem is also known to be APX-hard [Berman and DasGupta '97]; and for hole-free polygons, it is only known to be NP-hard [Culberson and Reckhow '94]. We prove that a simple Local Search algorithm yields a PTAS for the Boundary Cover problem for simple polygons. We do this by proving the existence of planar support graphs for the hypergraphs defined on the area-maximal rectangles contained in the polygons where every critical point on its boundary induces a hyperedge.
Hanwen Zhang -- Minimum Star Partitions of Simple Polygons in Polynomial Time
We devise a polynomial-time algorithm for partitioning a simple polygon $P$ with $n$ corners into a minimum number of star-shaped polygons. The complexity of this problem has been open for more than four decades since Avis and Toussaint [Pattern Recognit., 1981] gave an algorithm for constructing a partition of size at most $\lfloor n/3\rfloor$.
Marcin Pilipczuk -- On metric embeddings of planar graphs (https://arxiv.org/abs/2304.07268)
We prove that there is a randomized polynomial-time algorithm that given an edge-weighted graph G excluding a fixed-minor Q on n vertices and an accuracy parameter ε > 0, constructs an edge-weighted graph H and an embedding η : V (G) → V (H) with the following properties:
• For any constant size Q, the treewidth of H is polynomial in 1/ε , log n, and the logarithm of the stretch of the distance metric in G.
• The expected multiplicative distortion between any pair of vertices of G is (1 + ε).
Our embedding is the first to achieve polylogarithmic treewidth of the host graph and comes close to the lower bound by Carroll and Goel, who showed that any embedding of a planar graph with O(1) expected distortion requires the host graph to have treewidth Ω(log n). It also provides a unified framework for obtaining randomized quasi-polynomial-time approximation schemes for a variety of problems including network design, clustering or routing problems, in minor-free metrics where the optimization goal is the sum of selected distances. Applications include the capacitated vehicle routing problem, and capacitated clustering problems.
Joint work with Vincent Cohen-Addad, Hung Le, and Michał Pilipczuk
Mingmou Liu -- Lower Bounds for Sparse Oblivious Subspace Embeddings
For a random matrix Π which satisfies Pr [∀𝑥∈𝑇,(1−ϵ)\|𝑥\|_2≤\|Π𝑥\|_2≤(1+ϵ)\|𝑥\|_2 ]≥1−δ for any 𝑑-dimensional subspace 𝑇⊆𝑅^𝑛 with at most 1/9𝜖 nonzero entries in each column, we show Π must have Ω(𝑑^2/ϵ^(1−𝑂(δ) ) ) rows.
Zhile Jiang -- Computing better approximate pure Nash equilibria in cut games via semidefinite programming
Cut games are among the most fundamental strategic games in algorithmic game theory. It is well-known that computing an exact pure Nash equilibrium in these games is PLS-hard, so research has focused on computing approximate equilibria. We present a polynomial-time algorithm that computes 2.7371-approximate pure Nash equilibria in cut games. This is the first improvement to the previously best-known bound of 3, due to the work of Bhalgat, Chakraborty, and Khanna from EC 2010. Our algorithm is based on a general recipe proposed by Caragiannis, Fanelli, Gravin, and Skopalik from FOCS 2011 and applied on several potential games since then. The first novelty of our work is the introduction of a phase that can identify subsets of players who can simultaneously improve their utilities considerably. This is done via semidefinite programming and randomized rounding. In particular, a negative objective value to the semidefinite program guarantees that no such considerable improvement is possible for a given set of players. Otherwise, randomized rounding of the SDP solution is used to identify a set of players who can simultaneously improve their strategies considerably and allows the algorithm to make progress. The way rounding is performed is another important novelty of our work. Here, we exploit an idea that dates back to a paper by Feige and Goemans from 1995, but we take it to an extreme that has not been analyzed before.
Jacob Holm and Joel Andersson
{jaho, jda} [at] di.ku.dk
DIKU
Universitetsparken 1
2100 København Ø