Skip to main content

Theory of Computing Systems OnlineFirst articles

22.11.2021 Open Access

The Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems

We determine the power of the weighted sum scalarization with respect to the computation of approximations for general multiobjective minimization and maximization problems. Additionally, we introduce a new multi-factor notion of approximation …

Cristina Bazgan, Stefan Ruzika, Clemens Thielen, Daniel Vanderpooten


On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences

We study the three-dimensional stable matching problem with cyclic preferences. This model involves three types of agents, with an equal number of agents of each type. The types form a cyclic order such that each agent has a complete preference …

Chi-Kit Lam, C. Gregory Plaxton


Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

We consider maximizing a monotone submodular function under a cardinality constraint or a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access to only a …

Chien-Chung Huang, Naonori Kakimura

28.10.2021 Open Access

On the structure of solution-sets to regular word equations

For quadratic word equations, there exists an algorithm based on rewriting rules which generates a directed graph describing all solutions to the equation. For regular word equations – those for which each variable occurs at most once on each side …

Joel D. Day, Florin Manea

28.10.2021 Open Access

Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs

The computational complexity of the VertexCover problem has been studied extensively. Most notably, it is NP-complete to find an optimal solution and typically NP-hard to find an approximation with reasonable factors. In contrast, recent …

Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, Maximilian Katzmann

28.10.2021 Open Access

Decidability and Periodicity of Low Complexity Tilings

In this paper we study colorings (or tilings) of the two-dimensional grid ℤ 2 ${\mathbb {Z}}^{2}$ . A coloring is said to be valid with respect to a set P of n × m rectangular patterns if all n × m sub-patterns of the coloring are in P. A coloring …

Jarkko Kari, Etienne Moutot

28.10.2021 Open Access

Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata

We show that the finite sequentiality problem is decidable for finitely ambiguous max-plus tree automata. A max-plus tree automaton is a weighted tree automaton over the max-plus semiring. A max-plus tree automaton is called finitely ambiguous if …

Erik Paul

26.10.2021 Open Access

Stable Multi-Level Monotonic Eroders

Eroders are monotonic cellular automata with a linearly ordered state set that eventually wipe out any finite island of nonzero states. One-dimensional eroders were studied by Gal’perin in the 1970s, who presented a simple combinatorial …

Péter Gács, Ilkka Törmä


The Complexity of Counting CSPd

Counting CSPd is the counting constraint satisfaction problem (# CSP in short) restricted to the instances where every variable occurs a multiple of d times. This paper revisits tractable structures in # CSP and gives a complexity classification …

Jiabao Lin

09.08.2021 Open Access

FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints

We prove a complexity classification for Holant problems defined by an arbitrary set of complex-valued symmetric constraint functions on Boolean variables. This is to specifically answer the question: Is the Fisher-Kasteleyn-Temperley (FKT) …

Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams


Risk-Robust Mechanism Design for a Prospect-Theoretic Buyer

Consider the revenue maximization problem of a risk-neutral seller with m heterogeneous items for sale to a single additive buyer, whose values for the items are drawn from known distributions. If the buyer is also risk-neutral, it is known that a …

Siqi Liu, J. Benjamin Miller, Alexandros Psomas


Radio k-chromatic Number of Full m-ary Trees

For a simple connected graph G = (V (G),E(G)) and a positive integer k, a radio k-labelling of G is a mapping f : V ( G ) → { 0 , 1 , 2 , … } $f \colon V(G)\rightarrow \{0,1,2,\ldots \}$ such that | f ( u ) − f ( v ) | ≥ k + 1 − d ( u , v ) …

Laxman Saha, Alamgir R. Basunia, Satyabrata Das, Kalishankar Tiwary


Exact Multi-Covering Problems with Geometric Sets

The b-Exact Multicover problem takes a universe U of n elements, a family F $\mathcal {F}$ of m subsets of U, a function dem : U → { 1 , … , b } ${\textsf {dem}}: U \rightarrow \{1,\ldots ,b\}$ and a positive integer k, and decides whether there …

Pradeesha Ashok, Sudeshna Kolay, Neeldhara Misra, Saket Saurabh


Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators

Let F [ X ] ${\mathbb {F}}[X]$ be the polynomial ring in the variables X = {x1,x2,…,xn} over a field F ${\mathbb {F}}$ . An ideal I = 〈p1(x1),…,pn(xn)〉 generated by univariate polynomials { p i ( x i ) } i = 1 n $\{p_{i}(x_{i})\}_{i=1}^{n}$ is a …

V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay


An Alternating Algorithm for Finding Linear Arrow-Debreu Market Equilibria

Motivated by the convergence result of mirror-descent algorithms to market equilibria in linear Fisher markets, it is natural for one to consider designing dynamics (specifically, iterative algorithms) for agents to arrive at linear Arrow-Debreu …

Po-An Chen, Chi-Jen Lu, Yu-Sin Lu


Fixed-Parameter Algorithms for Unsplittable Flow Cover

The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a …

Andrés Cristi, Mathieu Mari, Andreas Wiese


Generating Visual Invariants −a New Approach to Invariant Recognition

This paper is devoted to a new paradigm for the invariant recognition of visual objects through introducing ‘the generating invariant’ of the underlying visual geometry which allows to numerically calculate differential signature curves in a fully …

Reza Aghayan

02.06.2021 Open Access

On Polynomial Recursive Sequences

We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where …

Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, Géraud Sénizergues

26.03.2021 Open Access

Typical Sequences Revisited — Computing Width Parameters of Graphs

In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth …

Hans L. Bodlaender, Lars Jaffke, Jan Arne Telle

15.03.2021 | OBITUARY

In Memoriam - Alan Selman (1941 - 2021)