DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2026.12

Fast Select Queries Using Hybrid Bitvectors

Authors: Eric Chiu and Dominik Kempa

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract

One of the central problems in the design of compressed data structures is the efficient support for rank and select queries on bitvectors. These two operations form the backbone of more complex data structures used for the compact representation of texts, trees, graphs, or grids. One effective solution is the so-called hybrid bitvector implementation, which partitions the input bitvector into blocks and adaptively selects an encoding method - such as run-length, plain, or minority encoding - based on local redundancy. Experiments have shown that hybrid bitvectors achieve excellent all-around performance on repetitive and non-repetitive inputs. Current hybrid bitvector implementations, however, support only rank queries (i.e., counting the number of ones up to a given position) and lack support for select queries (which ask for the position of a given occurrence of a given bit), which limits their applicability. In this paper, we propose a method to add support for select queries to hybrid bitvectors, and we evaluate the resulting implementation on repetitive and non-repetitive inputs. Our results show that hybrid bitvectors offer very strong all-around performance, combining high query speed with space efficiency and remaining consistently on or near the Pareto frontier.

Cite as

Eric Chiu and Dominik Kempa. Fast Select Queries Using Hybrid Bitvectors. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 12:1-12:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.SEA.2026.12,
  author =	{Chiu, Eric and Kempa, Dominik},
  title =	{{Fast Select Queries Using Hybrid Bitvectors}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{12:1--12:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.12},
  URN =		{urn:nbn:de:0030-drops-260168},
  doi =		{10.4230/LIPIcs.SEA.2026.12},
  annote =	{Keywords: compressed bitvectors, hybrid bitvector, select queries}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.4

Improved Bounds for Online TSP on the Half-Line

Authors: Júlia Baligács, Yann Disser, and Linda Thelen

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

In the open online traveling salesperson problem, requests appear over time at different positions of a metric space. A single agent traveling at unit speed must serve all requests, by visiting their positions, with the objective of minimizing the completion time. We propose online algorithms for this problem for the case that the metric space is the half-line. First, we present a 2-competitive algorithm in which the server always either moves at unit speed or remains stationary, which improves on the previously best-known ratio of 2.04. We further observe that algorithms must sometimes move slower than unit speed to achieve competitive ratios below 2. We introduce a second algorithm that beats the barrier of 2 by carefully modulating its speed, and prove a tight bound of 1.75 on its competitive ratio. Finally, we slightly strengthen a known lower bound on the best-possible competitive ratio on the half-line from 1.627 to 1.646.

Cite as

Júlia Baligács, Yann Disser, and Linda Thelen. Improved Bounds for Online TSP on the Half-Line. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.SWAT.2026.4,
  author =	{Balig\'{a}cs, J\'{u}lia and Disser, Yann and Thelen, Linda},
  title =	{{Improved Bounds for Online TSP on the Half-Line}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.4},
  URN =		{urn:nbn:de:0030-drops-260402},
  doi =		{10.4230/LIPIcs.SWAT.2026.4},
  annote =	{Keywords: online algorithms, competitive analysis, server problems, online TSP}
}

Document

DOI: 10.4230/OASIcs.NG-RES.2026.2

Schedulability Analysis of OpenMP Applications Under Heuristic Task-To-Thread Mapping

Authors: Mohammad Samadi, Tiago Carvalho, Luís Miguel Pinho, and Sara Royuela

Published in: OASIcs, Volume 140, 7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026)

Abstract

Task-to-thread mapping is a key process in parallel applications to achieve the best possible performance. This process is even more challenging when it is required to meet the schedulability and timing requirements of critical systems. In these systems, mapping tasks to threads is usually carried out using static scheduling (i.e., offline mapping) to improve system schedulability, with several approaches being presented in the literature. Nevertheless, there has been little analysis on the impact that these static mapping approaches have on the schedulability of applications exploiting OpenMP, a model increasingly seen as a suitable mechanism to leverage the potential of parallel and heterogeneous processor architectures. This paper, therefore, performs a throughout evaluation of the recently presented heuristic task-to-thread mapping working with different heuristics through allocation and dispatching phases, compared with state-of-the-art, in terms of schedulability. This process is performed using a state-of-the-art schedulability analysis methodology through an integration of our simulator and an existing schedulability toolset. This evaluation allows for identifying the static heuristic mapping approaches that achieve tighter schedulability analysis than other methods in the literature.

Cite as

Mohammad Samadi, Tiago Carvalho, Luís Miguel Pinho, and Sara Royuela. Schedulability Analysis of OpenMP Applications Under Heuristic Task-To-Thread Mapping. In 7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026). Open Access Series in Informatics (OASIcs), Volume 140, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{samadi_et_al:OASIcs.NG-RES.2026.2,
  author =	{Samadi, Mohammad and Carvalho, Tiago and Pinho, Lu{\'\i}s Miguel and Royuela, Sara},
  title =	{{Schedulability Analysis of OpenMP Applications Under Heuristic Task-To-Thread Mapping}},
  booktitle =	{7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026)},
  pages =	{2:1--2:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-415-4},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{140},
  editor =	{Ali, Hazem Ismail and Kurunathan, Harrison},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2026.2},
  URN =		{urn:nbn:de:0030-drops-254204},
  doi =		{10.4230/OASIcs.NG-RES.2026.2},
  annote =	{Keywords: OpenMP, task-to-thread mapping, heuristics, response time, schedulability}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.45

Fairness in the k-Server Problem

Authors: Mohammadreza Daneshvaramoli, Mohammad Hajiesmaili, Shahin Kamali, Helia Karisani, and Cameron Musco

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We initiate a formal study of fairness for the k-server problem, where the objective is not only to minimize the total movement cost, but also to distribute the cost equitably among servers. We first define a general notion of (α,β)-fairness, where, for parameters α ≥ 1 and β ≥ 0, no server incurs more than an α/k-fraction of the total cost plus an additive term β. We then show that fairness can be achieved without a loss in competitiveness in both the offline and online settings. In the offline setting, we give a deterministic algorithm that, for any ε > 0, transforms any optimal solution into an (α,β)-fair solution for α = 1 + ε and β = O(diam ⋅ log k / ε), while increasing the cost of the solution by just an additive O(diam ⋅ k log k / ε) term. Here diam is the diameter of the underlying metric space. We give a similar result in the online setting, showing that any competitive algorithm can be transformed into a randomized online algorithm that is fair with high probability against an oblivious adversary and still competitive up to a small loss. The above results leave open a significant question: can fairness be achieved in the online setting, either with a deterministic algorithm or a randomized algorithm, against a fully adaptive adversary? We make progress towards answering this question, showing that the classic deterministic Double Coverage Algorithm (DCA) is fair on line metrics and on tree metrics when k = 2. However, we also show a negative result: DCA fails to be fair for any non-vacuous parameters on general tree metrics. We further show that on uniform metrics (i.e., the paging problem), the deterministic First-In First-Out (FIFO) algorithm is fair. We show that any "marking algorithm", including the Least Recently Used (LRU) algorithm, also satisfies a weaker, but still meaningful notion of fairness.

Cite as

Mohammadreza Daneshvaramoli, Mohammad Hajiesmaili, Shahin Kamali, Helia Karisani, and Cameron Musco. Fairness in the k-Server Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{daneshvaramoli_et_al:LIPIcs.ITCS.2026.45,
  author =	{Daneshvaramoli, Mohammadreza and Hajiesmaili, Mohammad and Kamali, Shahin and Karisani, Helia and Musco, Cameron},
  title =	{{Fairness in the k-Server Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{45:1--45:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.45},
  URN =		{urn:nbn:de:0030-drops-253328},
  doi =		{10.4230/LIPIcs.ITCS.2026.45},
  annote =	{Keywords: k-server problem, online algorithms, fairness, competitive analysis}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2025.4

How Pinball Wizards Simulate a Turing Machine

Authors: Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract

We introduce and investigate the computational complexity of a novel physical problem known as the Pinball Wizard problem. It involves an idealized pinball moving through a maze composed of one-way gates (outswing doors), plane walls, parabolic walls, moving plane walls, and bumpers that cause acceleration or deceleration. Given the initial position and velocity of the pinball, the task is to decide whether it will hit a specified target point. By simulating a two-stack pushdown automaton, we show that the problem is Turing-complete - even in two-dimensional space. In our construction, each step of the automaton corresponds to a constant number of reflections. Thus, deciding the Pinball Wizard problem is at least as hard as the Halting problem. Furthermore, our construction allows bumpers to be replaced with moving walls. In this case, even a ball moving at constant speed - a so-called ray particle - can be used, demonstrating that the Ray Particle Tracing problem is also Turing-complete.

Cite as

Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer. How Pinball Wizards Simulate a Turing Machine. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{adejoh_et_al:LIPIcs.FSTTCS.2025.4,
  author =	{Adejoh, Rosemary U. and Jakoby, Andreas and Mohanty, Sneha and Schindelhauer, Christian},
  title =	{{How Pinball Wizards Simulate a Turing Machine}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.4},
  URN =		{urn:nbn:de:0030-drops-250832},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.4},
  annote =	{Keywords: Pinball Wizard problem, Halting problem, Turing-complete}
}

Document

DOI: 10.4230/LIPIcs.WADS.2025.41

Scheduling on Identical Machines with Setup Time and Unknown Execution Time

Authors: Yasushi Kawase, Kazuhisa Makino, Vinh Long Phan, and Hanna Sumita

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

In this study, we investigate a scheduling problem on identical machines in which jobs require initial setup before execution. We assume that an algorithm can dynamically form a batch (i.e., a collection of jobs to be processed together) from the remaining jobs. The setup time is modeled as a known monotone function of the set of jobs within a batch, while the execution time of each job remains unknown until completion. This uncertainty poses significant challenges for minimizing the makespan. We address these challenges by considering two scenarios: each job batch must be assigned to a single machine, or a batch may be distributed across multiple machines. For both scenarios, we analyze settings with and without preemption. Across these four settings, we design online algorithms that achieve asymptotically optimal competitive ratios with respect to both the number of jobs and the number of machines.

Cite as

Yasushi Kawase, Kazuhisa Makino, Vinh Long Phan, and Hanna Sumita. Scheduling on Identical Machines with Setup Time and Unknown Execution Time. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.WADS.2025.41,
  author =	{Kawase, Yasushi and Makino, Kazuhisa and Phan, Vinh Long and Sumita, Hanna},
  title =	{{Scheduling on Identical Machines with Setup Time and Unknown Execution Time}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.41},
  URN =		{urn:nbn:de:0030-drops-242728},
  doi =		{10.4230/LIPIcs.WADS.2025.41},
  annote =	{Keywords: Online scheduling, Competitive analysis, Makespan minimization, Identical machines scheduling}
}

Document

DOI: 10.4230/LIPIcs.SEA.2025.23

Elias-Fano Compression for Space-Efficient Rank and Select Structures

Authors: Lannie Dalton Hough and Abhinav Bhatele

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract

Bit vectors are an important component in many data structures. Such data structures are used in a variety of applications and domains including databases, search engines, and computational biology. Many use cases depend on being able to perform rank and/or select queries on the bit vector. No existing rank and select structure enabling these queries is most efficient both for space and for time; there is a tradeoff between the two. In practice, the smallest rank and select data structures, cs-poppy and pasta-flat, impose a space overhead of 3.51%, or 3.125% if only rank needs to be supported. In this paper, we present a new data structure, orzo, which reduces the overhead of the rank component by a further 26.5%. We preserve desirable cache-centric design decisions made in prior work, which allows us to minimize the performance penalty of creating a smaller data structure.

Cite as

Lannie Dalton Hough and Abhinav Bhatele. Elias-Fano Compression for Space-Efficient Rank and Select Structures. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hough_et_al:LIPIcs.SEA.2025.23,
  author =	{Hough, Lannie Dalton and Bhatele, Abhinav},
  title =	{{Elias-Fano Compression for Space-Efficient Rank and Select Structures}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.23},
  URN =		{urn:nbn:de:0030-drops-232617},
  doi =		{10.4230/LIPIcs.SEA.2025.23},
  annote =	{Keywords: rank and select, cache-aware, succinct data structures, bit vector}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.50

New Results on a General Class of Minimum Norm Optimization Problems

Authors: Kuowen Chen, Jian Li, Yuval Rabani, and Yiran Zhang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We study the general norm optimization for combinatorial problems, initiated by Chakrabarty and Swamy (STOC 2019). We propose a general formulation that captures a large class of combinatorial structures: we are given a set 𝒰 of n weighted elements and a family of feasible subsets ℱ. Each subset S ∈ ℱ is called a feasible solution/set of the problem. We denote the value vector by v = {v_i}_{i ∈ [n]}, where v_i ≥ 0 is the value of element i. For any subset S ⊆ 𝒰, we use v[S] to denote the n-dimensional vector {v_e⋅ 𝟏[e ∈ S]}_{e ∈ 𝒰} (i.e., we zero out all entries that are not in S). Let f: ℝⁿ → ℝ_+ be a symmetric monotone norm function. Our goal is to minimize the norm objective f(v[S]) over feasible subset S ∈ ℱ. The problem significantly generalizes the corresponding min-sum and min-max problems. We present a general equivalent reduction of the norm minimization problem to a multi-criteria optimization problem with logarithmic budget constraints, up to a constant approximation factor. Leveraging this reduction, we obtain constant factor approximation algorithms for the norm minimization versions of several covering problems, such as interval cover, multi-dimensional knapsack cover, and logarithmic factor approximation for set cover. We also study the norm minimization versions for perfect matching, s-t path and s-t cut. We show the natural linear programming relaxations for these problems have a large integrality gap. To complement the negative result, we show that, for perfect matching, it is possible to obtain a bi-criteria result: for any constant ε,δ > 0, we can find in polynomial time a nearly perfect matching (i.e., a matching that matches at least 1-ε proportion of vertices) and its cost is at most (8+δ) times of the optimum for perfect matching. Moreover, we establish the existence of a polynomial-time O(log log n)-approximation algorithm for the norm minimization variant of the s-t path problem. Specifically, our algorithm achieves an α-approximation with a time complexity of n^{O(log log n / α)}, where 9 ≤ α ≤ log log n.

Cite as

Kuowen Chen, Jian Li, Yuval Rabani, and Yiran Zhang. New Results on a General Class of Minimum Norm Optimization Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2025.50,
  author =	{Chen, Kuowen and Li, Jian and Rabani, Yuval and Zhang, Yiran},
  title =	{{New Results on a General Class of Minimum Norm Optimization Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{50:1--50:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.50},
  URN =		{urn:nbn:de:0030-drops-234276},
  doi =		{10.4230/LIPIcs.ICALP.2025.50},
  annote =	{Keywords: Approximation Algorithms, Minimum Norm Optimization, Linear Programming}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.112

Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns

Authors: Alexandra Lassota and Koen Ligthart

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We study integer linear programs (ILP) of the form min{c^⊤ x | Ax = b,l ≤ x ≤ u,x ∈ ℤⁿ} and analyze their parameterized complexity with respect to their distance to the generalized matching problem, following the well-established approach of capturing the hardness of a problem by the distance to triviality. The generalized matching problem is an ILP where each column of the constraint matrix has 1-norm of at most 2. It captures several well-known polynomial time solvable problems such as matching and flow problems. We parameterize by the size of variable and constraint backdoors, which measure the least number of columns or rows that must be deleted to obtain a generalized matching ILP. This extends generalized matching problems by allowing a parameterized number of additional arbitrary variables or constraints, yielding a novel parameter. We present the following results: (i) a fixed-parameter tractable (FPT) algorithm for ILPs parameterized by the size p of a minimum variable backdoor to generalized matching; (ii) a randomized slice-wise polynomial (XP) time algorithm for ILPs parameterized by the size h of a minimum constraint backdoor to generalized matching as long as c and A are encoded in unary; (iii) we complement (ii) by proving that solving an ILP is W[1]-hard when parameterized by h even when c,A,l,u have coefficients of constant size. To obtain (i), we prove a variant of lattice-convexity of the degree sequences of weighted b-matchings, which we study in the light of SBO jump M-convex functions. This allows us to model the matching part as a polyhedral constraint on the integer backdoor variables. The resulting ILP is solved in FPT time using an integer programming algorithm. For (ii), the randomized XP time algorithm is obtained by pseudo-polynomially reducing the problem to the exact matching problem. To prevent an exponential blowup in terms of the encoding length of b, we bound the Graver complexity of the constraint matrix and employ a Graver augmentation local search framework. The hardness result (iii) is obtained through a parameterized reduction from ILP with h constraints and coefficients encoded in unary.

Cite as

Alexandra Lassota and Koen Ligthart. Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 112:1-112:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lassota_et_al:LIPIcs.ICALP.2025.112,
  author =	{Lassota, Alexandra and Ligthart, Koen},
  title =	{{Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{112:1--112:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.112},
  URN =		{urn:nbn:de:0030-drops-234895},
  doi =		{10.4230/LIPIcs.ICALP.2025.112},
  annote =	{Keywords: Integer Programming, fixed-parameter Tractability, polyhedral Optimization, Matchings}
}

Document

DOI: 10.4230/LIPIcs.CPM.2025.5

Covers in Optimal Space

Authors: Itai Boneh and Shay Golan

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract

A cover of a string S is a string C such that every index of S is contained in some occurrence of C. First introduced by Apostolico and Ehrenfeucht [TCS'93] over 30 years ago, covers have since received significant attention in the string algorithms community. In this work, we present a space-efficient algorithm for computing a compact representation of all covers of a given string. Our algorithm requires only O(log n) additional memory while accessing the input string of length n in a read-only manner. Moreover, it runs in O(n) time, matching the best-known time complexity for this problem while achieving an exponential improvement in space usage.

Cite as

Itai Boneh and Shay Golan. Covers in Optimal Space. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{boneh_et_al:LIPIcs.CPM.2025.5,
  author =	{Boneh, Itai and Golan, Shay},
  title =	{{Covers in Optimal Space}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.5},
  URN =		{urn:nbn:de:0030-drops-230993},
  doi =		{10.4230/LIPIcs.CPM.2025.5},
  annote =	{Keywords: Cover, Read-only random access, small space}
}

Document

DOI: 10.4230/LITES-v006-i001-a005

Elastic Scheduling for Parallel Real-Time Systems

Authors: James Orr, Chris Gill, Kunal Agrawal, Jing Li, and Sanjoy Baruah

Published in: LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1

Abstract

The elastic task model was introduced by Buttazzo et al.~in order to represent recurrent real-time workloads executing upon uniprocessor platforms that are somewhat flexible with regards to timing constraints. In this work, we propose an extension of this model and apply it to represent recurrent real-time workloads that exhibit internal parallelism and are executed on multiprocessor platforms. In our proposed extension, the elasticity coefficient - the quantitative measure of a task's elasticity that was introduced in the model proposed by Buttazzo et al. - is interpreted in the same manner as in the original (sequential) model. Hence, system developers who are familiar with the elastic task model in the uniprocessor context may use our more general model as they had previously done, now for real-time tasks whose computational demands require them to utilize more than one processor.

Cite as

James Orr, Chris Gill, Kunal Agrawal, Jing Li, and Sanjoy Baruah. Elastic Scheduling for Parallel Real-Time Systems. In LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1, pp. 05:1-05:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{orr_et_al:LITES-v006-i001-a005,
  author =	{Orr, James and Gill, Chris and Agrawal, Kunal and Li, Jing and Baruah, Sanjoy},
  title =	{{Elastic Scheduling for Parallel Real-Time Systems}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{05:1--05:14},
  ISSN =	{2199-2002},
  year =	{2019},
  volume =	{6},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v006-i001-a005},
  URN =		{urn:nbn:de:0030-drops-192819},
  doi =		{10.4230/LITES-v006-i001-a005},
  annote =	{Keywords: Parallel real-time tasks, multiprocessor federated scheduling, elasticity coefficient}
}

Document

DOI: 10.4230/LITES-v005-i001-a001

Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions

Authors: Bader Naim Alahmad and Sathish Gopalakrishnan

Published in: LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1

Abstract

We pose the problem of scheduling Mixed Criticality (MC) job systems when there are only two criticality levels, Lo and Hi -referred to as Dual Criticality job systems- on a single processing platform, when job demands are probabilistic and their distributions are known. The current MC models require that the scheduling policy allocate as little execution time as possible to Lo-criticality jobs if the scenario of execution is of Hi criticality, and drop Lo-criticality jobs entirely as soon as the execution scenario's criticality level can be inferred and is Hi. The work incurred by "incorrectly" scheduling Lo-criticality jobs in cases of Hi realized scenarios might affect the feasibility of Hi criticality jobs; we quantify this work and call it Work Threatening Feasibility (WTF). Our objective is to construct online scheduling policies that minimize the expected WTF for the given instance, and under which the instance is feasible in a probabilistic sense that is consistent with the traditional deterministic definition of MC feasibility. We develop a probabilistic framework for MC scheduling, where feasibility is defined in terms of (chance) constraints on the probabilities that Lo and Hi jobs meet their deadlines. The probabilities are computed over the set of sample paths, or trajectories, induced by executing the policy, and those paths are dependent upon the set of execution scenarios and the given demand distributions. Our goal is to exploit the information provided by job distributions to compute the minimum expected WTF below which the given instance is not feasible in probability, and to compute a (randomized) "efficiently implementable" scheduling policy that realizes the latter quantity. We model the problem as a Constrained Markov Decision Process (CMDP) over a suitable state space and a finite planning horizon, and show that an optimal (non-stationary) Markov randomized scheduling policy exists. We derive an optimal policy by solving a Linear Program (LP). We also carry out quantitative evaluations on select probabilistic MC instances to demonstrate that our approach potentially outperforms current MC scheduling policies.

Cite as

Bader Naim Alahmad and Sathish Gopalakrishnan. Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions. In LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1, pp. 01:1-01:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{alahmad_et_al:LITES-v005-i001-a001,
  author =	{Alahmad, Bader Naim and Gopalakrishnan, Sathish},
  title =	{{Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:30},
  ISSN =	{2199-2002},
  year =	{2018},
  volume =	{5},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v005-i001-a001},
  URN =		{urn:nbn:de:0030-drops-192720},
  doi =		{10.4230/LITES-v005-i001-a001},
  annote =	{Keywords: Mixed criticalities, Probability distribution, Real time systems, Scheduling, Chance constrained Markov decision process, Linear programming, Randomized policy}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.17

On the Convergence Time of a Natural Dynamics for Linear Programming

Authors: Vincenzo Bonifaci

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

We consider a system of nonlinear ordinary differential equations for the solution of linear programming (LP) problems that was first proposed in the mathematical biology literature as a model for the foraging behavior of acellular slime mold Physarum polycephalum, and more recently considered as a method to solve LP instances. We study the convergence time of the continuous Physarum dynamics in the context of the linear programming problem, and derive a new time bound to approximate optimality that depends on the relative entropy between projected versions of the optimal point and of the initial point. The bound scales logarithmically with the LP cost coefficients and linearly with the inverse of the relative accuracy, establishing the efficiency of the dynamics for arbitrary LP instances with positive costs.

Cite as

Vincenzo Bonifaci. On the Convergence Time of a Natural Dynamics for Linear Programming. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bonifaci:LIPIcs.ISAAC.2017.17,
  author =	{Bonifaci, Vincenzo},
  title =	{{On the Convergence Time of a Natural Dynamics for Linear Programming}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.17},
  URN =		{urn:nbn:de:0030-drops-82274},
  doi =		{10.4230/LIPIcs.ISAAC.2017.17},
  annote =	{Keywords: linear programming, natural algorithm, Physarum polycephalum, relative entropy, Mirror Descent}
}

Document

DOI: 10.4230/LITES-v003-i001-a004

Optimal Scheduling of Periodic Gang Tasks

Authors: Joël Goossens and Pascal Richard

Published in: LITES, Volume 3, Issue 1 (2016). Leibniz Transactions on Embedded Systems, Volume 3, Issue 1

Abstract

The gang scheduling of parallel implicit-deadline periodic task systems upon identical multiprocessor platforms is considered. In this scheduling problem, parallel tasks use several processors simultaneously. We propose two DPFAIR (deadline partitioning) algorithms that schedule all jobs in every interval of time delimited by two subsequent deadlines. These algorithms define a static schedule pattern that is stretched at run-time in every interval of the DPFAIR schedule. The first algorithm is based on linear programming and is the first one to be proved optimal for the considered gang scheduling problem. Furthermore, it runs in polynomial time for a fixed number m of processors and an efficient implementation is fully detailed. The second algorithm is an approximation algorithm based on a fixed-priority rule that is competitive under resource augmentation analysis in order to compute an optimal schedule pattern. Precisely, its speedup factor is bounded by (2-1/m). Both algorithms are also evaluated through intensive numerical experiments.

Cite as

Joël Goossens and Pascal Richard. Optimal Scheduling of Periodic Gang Tasks. In LITES, Volume 3, Issue 1 (2016). Leibniz Transactions on Embedded Systems, Volume 3, Issue 1, pp. 04:1-04:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{goossens_et_al:LITES-v003-i001-a004,
  author =	{Goossens, Jo\"{e}l and Richard, Pascal},
  title =	{{Optimal Scheduling of Periodic Gang Tasks}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{04:1--04:18},
  ISSN =	{2199-2002},
  year =	{2016},
  volume =	{3},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v003-i001-a004},
  URN =		{urn:nbn:de:0030-drops-192593},
  doi =		{10.4230/LITES-v003-i001-a004},
  annote =	{Keywords: Real-time systems, Scheduling, Parallel tasks}
}

Document

DOI: 10.4230/LITES-v001-i002-a003

Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor

Authors: Zhishan Guo and Sanjoy K. Baruah

Published in: LITES, Volume 1, Issue 2 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 2

Abstract

A mixed criticality (MC) workload consists of components of varying degrees of importance (or "criticalities"); the more critical components typically need to have their correctness validated to greater levels of assurance than the less critical ones. The problem of executing such a MC workload upon a preemptive processor whose effective speed may vary during run-time, in a manner that is not completely known prior to run-time, is considered.Such a processor is modeled as being characterized by several execution speeds: a normal speed and several levels of degraded speed. Under normal circumstances it will execute at or above its normal speed; conditions during run-time may cause it to execute slower. It is desired that all components of the MC workload execute correctly under normal circumstances. If the processor speed degrades, it should nevertheless remain the case that the more critical components execute correctly (although the less critical ones need not do so).In this work, we derive an optimal algorithm for scheduling MC workloads upon such platforms; achieving optimality does not require that the processor be able to monitor its own run-time speed. For the sub-case of the general problem where there are only two criticality levels defined, we additionally provide an implementation that is asymptotically optimal in terms of run-time efficiency.

Cite as

Zhishan Guo and Sanjoy K. Baruah. Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor. In LITES, Volume 1, Issue 2 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 2, pp. 03:1-03:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{guo_et_al:LITES-v001-i002-a003,
  author =	{Guo, Zhishan and Baruah, Sanjoy K.},
  title =	{{Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{03:1--03:19},
  ISSN =	{2199-2002},
  year =	{2014},
  volume =	{1},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v001-i002-a003},
  URN =		{urn:nbn:de:0030-drops-192498},
  doi =		{10.4230/LITES-v001-i002-a003},
  annote =	{Keywords: Mixed criticalities, Varying-speed processor, Preemptive uniprocessor scheduling, }
}

17 Search Results for "Bonifaci, Vincenzo"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message