Search Our Scientific Publications & Authors

Algorithmica 2022 30;84(5):1357-1384. Epub 2022 Jan 30.

University of Augsburg, Augsburg, Germany.

We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected competitive ratio implies the existence of a randomized online algorithm that has a competitive ratio of , measured with respect to the optimal profit or cost, respectively. The class of problems includes some of the well-studied online problems such as paging, -server, and metrical task systems on finite metric spaces. Read More

Algorithmica 2022 24;84(4):1007-1029. Epub 2021 Dec 24.

IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria.

We consider the following dynamic load-balancing process: given an underlying graph with nodes, in each step , a random edge is chosen, one unit of load is created, and placed at one of the endpoints. In the same step, assuming that loads are arbitrarily divisible, the two nodes their loads by averaging them. We are interested in the expected gap between the minimum and maximum loads at nodes as the process progresses, and its dependence on and on the graph structure. Read More

Algorithmica 2022 24;84(1):234-271. Epub 2021 Nov 24.

School of Computer Science and Electronic Engineering, University of Essex, Colchester, UK.

Social networks on the Internet have seen an enormous growth recently and play a crucial role in different aspects of today's life. They have facilitated information dissemination in ways that have been beneficial for their users but they are often used strategically in order to spread information that only serves the objectives of particular users. These properties have inspired a revision of classical opinion formation models from sociology using game-theoretic notions and tools. Read More

Algorithmica 2022 1;84(1):60-84. Epub 2021 Nov 1.

Department of Computer Science, ETH Zürich, Zürich, Switzerland.

We consider the problem in presence of . This problem asks to select one of the smallest elements in a linearly-ordered collection of elements by only performing pairwise comparisons: whenever two elements are compared, there is a small probability that the wrong comparison outcome is observed. We design a randomized algorithm that solves this problem with a success probability of at least for and any using comparisons in expectation (if or the problem becomes trivial). Read More

Algorithmica 2022 28;84(1):13-36. Epub 2021 Oct 28.

Department of Informatics, University of Bergen, Bergen, Norway.

The Non-Uniform -center (NUkC) problem has recently been formulated by Chakrabarty et al. [ICALP, 2016; ACM Trans Algorithms 16(4):46:1-46:19, 2020] as a generalization of the classical -center clustering problem. In NUkC, given a set of points in a metric space and non-negative numbers , the goal is to find the minimum dilation and to choose balls centered at the points of with radius for , such that all points of are contained in the union of the chosen balls. Read More

Algorithmica 2021 1;83(9):2833-2858. Epub 2021 Jul 1.

Department of Computer Science, Technial University of Munich, Boltzmannstr. 3, 85748 Garching, Germany.

Best Fit is a well known online algorithm for the bin packing problem, where a collection of one-dimensional items has to be packed into a minimum number of unit-sized bins. In a seminal work, Kenyon [SODA 1996] introduced the (asymptotic) as an alternative performance measure for online algorithms. Here, an adversary specifies the items, but the order of arrival is drawn uniformly at random. Read More

Algorithmica 2021 9;83(9):2803-2832. Epub 2021 Jun 9.

Lehrstuhl für Algorithmen und Komplexität, Institut für Informatik, Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany.

Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that is -competitive. Read More

Algorithmica 2021 31;83(8):2634-2650. Epub 2020 Jul 31.

Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland.

Let and be hereditary graph classes. Consider the following problem: given a graph , find a largest, in terms of the number of vertices, induced subgraph of that belongs to . We prove that it can be solved in time, where is the number of vertices of , if the following conditions are satisfied:the graphs in are sparse, i. Read More

Algorithmica 2021 22;83(8):2578-2605. Epub 2021 Feb 22.

Dipartimento di Informatica, Università Statale di Milano, Milan, Italy.

Given a -node pattern graph and an -node host graph , the subgraph counting problem asks to compute the number of copies of in . In this work we address the following question: can we count the copies of faster if is sparse? We answer in the affirmative by introducing a novel tree-like decomposition for directed acyclic graphs, inspired by the classic tree decomposition for undirected graphs. This decomposition gives a dynamic program for counting the homomorphisms of in by exploiting the degeneracy of , which allows us to beat the state-of-the-art subgraph counting algorithms when is sparse enough. Read More

Algorithmica 2021 17;83(6):1750-1785. Epub 2021 Feb 17.

Department of Computer Science, Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany.

The is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set. Read More

Algorithmica 2021 26;83(5):1559-1603. Epub 2021 Mar 26.

Budapest University of Technology and Economics, and Centre for Economic and Regional Studies, Institute of Economics, Budapest, Hungary.

We consider the following control problem on fair allocation of indivisible goods. Given a set of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. Read More

Algorithmica 2021 21;83(2):726-752. Epub 2020 Oct 21.

Algorithms Group, University of Sheffield, Sheffield, UK.

This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graph and a set of terminal pairs and asks whether contains a set of pairwise edge-disjoint paths connecting every terminal pair in . Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3. Read More

Algorithmica 2021 25;83(1):144-176. Epub 2020 Jul 25.

Département d'informatique, Université du Québec en Outaouais, Gatineau, Canada.

A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid . Some cells of the grid are full (contain a brick) and others are empty. Read More

Algorithmica 2021 27;83(1):116-143. Epub 2020 Jul 27.

TU Graz, Graz, Austria.

Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon. For some definition of a flip graph, a natural computational problem to consider is the flip distance: Given two objects, what is the minimum number of flips needed to transform one into the other? We consider flip graphs on orientations of simple graphs, where flips consist of reversing the direction of some edges. Read More

Algorithmica 2020 20;82(11):3306-3337. Epub 2020 Jun 20.

Helsinki Institute for Information Technology (HIIT), Espoo, Finland.

We derandomize Valiant's (J ACM 62, Article 13, 2015) subquadratic-time algorithm for finding outlier correlations in binary data. This demonstrates that it is possible to perform a deterministic subquadratic-time similarity join of high dimensionality. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same parameter range as Valiant's randomized algorithm, but the precise constants we save over quadratic scaling are more modest. Read More

Algorithmica 2020 22;82(8):2267-2291. Epub 2020 Jan 22.

ETH Zürich, Zurich, Switzerland.

We investigate the problem of counting all induced subgraphs of size  in a graph  that satisfy a given property . This continues the work of Jerrum and Meeks who proved the problem to be -hard for some families of properties which include (dis)connectedness [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Using the recent framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone properties  , the problem is hard for if the reduced Euler characteristic of the associated simplicial (graph) complex of is non-zero. Read More

Algorithmica 2020 14;82(5):1410-1433. Epub 2019 Nov 14.

7University of Southampton, Southampton, UK.

We consider the two-sided stable matching setting in which there may be uncertainty about the agents' preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model-for each agent, there is a probability distribution over linear preferences, (2) compact indifference model-for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model-there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. Read More

Algorithmica 2020 6;82(5):1136-1188. Epub 2020 Feb 6.

3Budapest University of Technology and Economics, Budapest, Hungary.

Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified; most such problems are -hard and also hard to approximate (Hamada et al. in Algorithmica 74(1):440-465, 2016). Read More

Algorithmica 2020 25;82(3):429-508. Epub 2019 Oct 25.

Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Universitätsstraße 65-67, 9020 Klagenfurt am Wörthersee, Austria.

In this article, -regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices contribute terms which grow faster than the error term. Read More

Algorithmica 2019 5;81(10):3993-4009. Epub 2018 Sep 5.

1Eindhoven University of Technology, Eindhoven, The Netherlands.

In this paper, we develop new tools and connections for . In this setting, we are given a problem instance and an integer , and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of for maximum independent set in time, for chromatic number in time, for minimum vertex cover in time, and for minimum -hypergraph vertex cover in time. Read More

Algorithmica 2019 25;81(5):1965-1987. Epub 2018 Sep 25.

2Department of Computer Science, University of Sheffield, Sheffield, UK.

In this paper we study graph problems in the dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require space, where is the number of vertices, existing works mainly focused on designing space algorithms. Although sublinear in the number of edges for dense graphs, it could still be too large for many applications (e. Read More

Algorithmica 2019 13;81(4):1699-1727. Epub 2018 Aug 13.

1University of Oxford, Oxford, UK.

Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Read More

Algorithmica 2019 4;81(4):1657-1683. Epub 2018 Sep 4.

4Department of Computer Science, University of Sheffield, Sheffield, UK.

We consider the -complete problem of counting the number of linear extensions of a poset ; a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e. Read More

Algorithmica 2019 30;81(2):497-518. Epub 2018 Jul 30.

Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Warsaw, Poland.

We introduce the non-commutative subset convolution-a convolution of functions useful when working with determinant-based algorithms. In order to compute it efficiently, we take advantage of Clifford algebras, a generalization of quaternions used mainly in the quantum field theory. We apply this tool to speed up algorithms counting subgraphs parameterized by the treewidth of a graph. Read More

Algorithmica 2019 7;81(1):317-342. Epub 2018 May 7.

6CSAIL, Massachusetts Institute of Technology, Cambridge, USA.

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. Read More

Algorithmica 2019 2;81(1):124-166. Epub 2018 Apr 2.

1University of Liverpool, Liverpool, UK.

The problem of pollution control has been mainly studied in the environmental economics literature where the methodology of game theory is applied for the pollution control. To the best of our knowledge this is the first time this problem is studied from the computational point of view. We introduce a new network model for pollution control and present two applications of this model. Read More

Algorithmica 2019 18;81(2):476-496. Epub 2018 Sep 18.

1Institut für Theoretische Informatik, Leibniz Universität Hannover, Appelstrasse 4, 30167 Hannover, Germany.

In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized by the size of the backdoor. We distinguish between backdoor detection and evaluation of backdoors into the fragments of Horn and Krom formulas. Read More

Algorithmica 2018 14;80(10):2909-2940. Epub 2017 Aug 14.

Institute of Information Systems 184/2, TU Wien, Favoritenstrasse 9-11, 1040 Vienna, Austria.

A secure set in a graph is defined as a set of vertices such that for any the majority of vertices in the neighborhood of belongs to . It is known that deciding whether a set is secure in a graph is -complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph and integer , a non-empty secure set for of size at most exists. Read More

Algorithmica 2018 13;80(2):742-771. Epub 2017 Feb 13.

Algorithms and Complexity Group, TU Wien, Vienna, Austria.

A modulator in a graph is a vertex set whose deletion places the considered graph into some specified graph class. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited to obtain fixed-parameter algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Read More

Algorithmica 2018 17;80(4):1115-1145. Epub 2017 Mar 17.

2Department of Computer Science, Oxford University, Oxford, UK.

We study the inefficiency of mixed Nash equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions where all-pay auctions run in parallel, one for each good. For fractionally subadditive valuations, we strengthen the upper bound from 2 (Syrgkanis and Tardos in Proceedings of the 45th symposium on theory of computing (STOC '13), 2013) to 1. Read More