Skip to main content
main-content
Top

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 …

16-11-2021

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 …

09-11-2021

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 …

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 …

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 …

Current Publications

About this journal

Statement of Scope

TOCS is devoted to publishing original research from all areas of theoretical computer science, ranging from foundational areas such as computational complexity, to fundamental areas such as algorithms and data structures, to focused areas such as parallel and distributed algorithms and architectures.

Additional information

Premium Partner

    Image Credits