30 Search Results for "Caprara, Alberto"

Volume

OASIcs, Volume 20

11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems

ATMOS 2011, September 8, 2011, Saarbrücken, Germany

Editors: Alberto Caprara and Spyros Kontogiannis

Document
DOI: 10.4230/LIPIcs.ITCS.2026.50
On the PTAS Complexity of Multidimensional Knapsack

Authors: Ilan Doron-Arad, Ariel Kulik, and Pasin Manurangsi

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

Abstract
We study the d-dimensional knapsack problem. We are given a set of items, each with a d-dimensional cost vector and a profit, along with a d-dimensional budget vector. The goal is to select a set of items that do not exceed the budget in all dimensions and maximize the total profit. A polynomial-time approximation scheme (PTAS) with running time n^{Θ(d/{ε})} has long been known for this problem, where {ε} is the error parameter and n is the encoding size. Despite decades of active research, the best running time of a PTAS has remained O(n^{⌈ d/{ε} ⌉ - d}). Unfortunately, existing lower bounds only cover the special case with two dimensions d = 2, and do not answer whether there is a n^{o(d/({ε)})}-time PTAS for larger values of d. In this work, we show that the running times of the best-known PTAS cannot be improved up to a polylogarithmic factor assuming the Exponential Time Hypothesis (ETH). Our techniques are based on a robust reduction from 2-CSP, which embeds 2-CSP constraints into a desired number of dimensions. Then, using a recent result of [Bafna Karthik and Minzer, STOC'25], we succeed in exhibiting tight trade-off between d and {ε} for all regimes of the parameters assuming d is sufficiently large. Informally, our result also shows that under ETH, for any function f there is no f(d/({ε)}) ⋅ n^{õ(d/({ε)})}-time (1-{ε})-approximation for d-dimensional knapsack, where n is the number of items and õ hides polylogarithmic factors in d/({ε)}.
Cite as

Ilan Doron-Arad, Ariel Kulik, and Pasin Manurangsi. On the PTAS Complexity of Multidimensional Knapsack. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 50:1-50:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{doronarad_et_al:LIPIcs.ITCS.2026.50,
  author =	{Doron-Arad, Ilan and Kulik, Ariel and Manurangsi, Pasin},
  title =	{{On the PTAS Complexity of Multidimensional Knapsack}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{50:1--50:22},
  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.50},
  URN =		{urn:nbn:de:0030-drops-253377},
  doi =		{10.4230/LIPIcs.ITCS.2026.50},
  annote =	{Keywords: d-dimensional Knapsack, Multidimensional Knapsack, PTAS, CSP}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.34
On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem

Authors: Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, and Laura Vargas Koch

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In train routing, the headway is the minimum distance that must be maintained between successive trains for safety and robustness. We introduce a model for train routing that requires a fixed headway to be maintained between trains, and study the problem of minimizing the makespan, i.e., the arrival time of the last train, in a single-source single-sink network. For this problem, we first show that there exists an optimal solution where trains move in convoys - that is, the optimal paths for any two trains are either the same or are arc-disjoint. Via this insight, we are able to reduce the approximability of our train routing problem to that of the min-max disjoint paths problem, which asks for a collection of disjoint paths where the maximum length of any path in the collection is as small as possible. While min-max disjoint paths inherits a strong inapproximability result on directed acyclic graphs from the multi-level bottleneck assignment problem, we show that a natural greedy composition approach yields a logarithmic approximation in the number of disjoint paths for series-parallel graphs. We also present an alternative analysis of this approach that yields a guarantee depending on how often the decomposition tree of the series-parallel graph alternates between series and parallel compositions on any root-leaf path.
Cite as

Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, and Laura Vargas Koch. On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.ESA.2025.34,
  author =	{Bhaskar, Umang and Eickhoff, Katharina and Kauther, Lennart and Matuschke, Jannik and Peis, Britta and Vargas Koch, Laura},
  title =	{{On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.34},
  URN =		{urn:nbn:de:0030-drops-245029},
  doi =		{10.4230/LIPIcs.ESA.2025.34},
  annote =	{Keywords: Train Routing, Scheduling, Approximation Algorithms, Flows over Time, Min-Max Disjoint Paths}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.10
Improved Approximation Guarantees for Advertisement Placement

Authors: Waldo Gálvez, Roberto Oliva, and Victor Verdugo

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
The advertisement placement problem involves selecting and scheduling ads within a timeline that has capacity constraints to maximize profit. Each task is characterized by its height, width, and profit, and must be fully scheduled across multiple time slots. This problem models practical scenarios such as internet advertising and energy management, and it also generalizes classical combinatorial optimization problems like the knapsack and bin packing problems. We present a simple (2+ε)-approximation algorithm for any ε > 0, which improves upon the state-of-the-art 3+ε factor established by Freund and Naor twenty years ago. Our approach combines rounding techniques with dynamic programming and an efficient extension of list scheduling. Furthermore, we enhance this method with linear programming techniques to provide an almost optimal (1+ε)-approximation algorithm under resource augmentation, which allows for a slight increase in time slot capacities.
Cite as

Waldo Gálvez, Roberto Oliva, and Victor Verdugo. Improved Approximation Guarantees for Advertisement Placement. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.APPROX/RANDOM.2025.10,
  author =	{G\'{a}lvez, Waldo and Oliva, Roberto and Verdugo, Victor},
  title =	{{Improved Approximation Guarantees for Advertisement Placement}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.10},
  URN =		{urn:nbn:de:0030-drops-243762},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.10},
  annote =	{Keywords: Advertisement Placement, Two-dimensional Packing, Geometric Knapsack, Resource Allocation}
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.18
Identifying Breakpoint Median Genomes: A Branching Algorithm Approach

Authors: Poly H. da Silva, Arash Jamshidpey, and David Sankoff

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Genome comparison often involves quantifying dissimilarities between genomes with identical gene sets, commonly using breakpoints - points where adjacent genes in one genome are not adjacent in another. The concept of a median genome, used for comparison of multiple genomes, aims to find a genome that minimizes the total distance to all genomes in a given set. While median genomes are useful for extracting common genomic information and estimating ancestral traits, the existence of multiple divergent medians raises concerns about their accuracy in reflecting the true ancestor. The median problem is known to be NP-hard, particularly for unichromosomal genomes, and solving it becomes increasingly challenging under different genome distance models. In this work, we introduce a novel branching algorithm to efficiently find all breakpoint medians of k linear unichromosomal genomes, represented as unsigned permutations. This algorithm constructs a rooted labeled tree, where the sequence of labels along each complete ray defines a genome, providing a structured and efficient way to explore the space of candidate medians by narrowing the search to a well-defined and significantly smaller subset of the permutation space. We validate our approach with experiments on randomly generated sets of three permutations. The results show that our method successfully finds the exact medians and also identifies many near-optimal approximations. Our experiments further show that most medians lie relatively close to the input permutations, in agreement with prior theoretical results.
Cite as

Poly H. da Silva, Arash Jamshidpey, and David Sankoff. Identifying Breakpoint Median Genomes: A Branching Algorithm Approach. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dasilva_et_al:LIPIcs.WABI.2025.18,
  author =	{da Silva, Poly H. and Jamshidpey, Arash and Sankoff, David},
  title =	{{Identifying Breakpoint Median Genomes: A Branching Algorithm Approach}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.18},
  URN =		{urn:nbn:de:0030-drops-239447},
  doi =		{10.4230/LIPIcs.WABI.2025.18},
  annote =	{Keywords: Breakpoint distance, median genomes, phylogeny reconstruction, random permutations}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.33
Constraint-Based In-Station Train Dispatching

Authors: Andreas Schutt, Matteo Cardellini, Jip J. Dekker, Daniel Harabor, Marco Maratea, and Mauro Vallati

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
In-station dispatching is the problem of planning the movements of scheduled trains inside a railway station. Effective solutions for in-station dispatching are important for maximising the utilisation of railway infrastructure and for mitigating the impact of incidents and delays in the broader network. In this paper, we explore a constraint-based approach to perform in-station train dispatching. Our extensive empirical analysis of multiple modelling, search strategy, and solver choices, performed over synthetically generated, yet realistic, data, shows that our method outperforms the existing planning-based state-of-the-art approach. In addition, we present different optimisation criteria, which can be effortless defined thanks to the constraint-based approach.
Cite as

Andreas Schutt, Matteo Cardellini, Jip J. Dekker, Daniel Harabor, Marco Maratea, and Mauro Vallati. Constraint-Based In-Station Train Dispatching. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 33:1-33:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schutt_et_al:LIPIcs.CP.2025.33,
  author =	{Schutt, Andreas and Cardellini, Matteo and Dekker, Jip J. and Harabor, Daniel and Maratea, Marco and Vallati, Mauro},
  title =	{{Constraint-Based In-Station Train Dispatching}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{33:1--33:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.33},
  URN =		{urn:nbn:de:0030-drops-238941},
  doi =		{10.4230/LIPIcs.CP.2025.33},
  annote =	{Keywords: in-station train dispatching, train scheduling, railway scheduling, constraint programming, mixed-integer programming}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.27
Sparsity-Driven Aggregation of Mixed Integer Programs

Authors: Liding Xu, Gioni Mexi, and Ksenia Bestuzheva

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

Abstract
Cutting planes are crucial for the performance of branch-and-cut algorithms for solving mixed-integer programming (MIP) problems, and linear row aggregation has been successfully applied to better leverage the potential of several major families of MIP cutting planes. This paper formulates the problem of finding good quality aggregations as an 𝓁₀-norm minimization problem and employs a combination of the lasso method and iterative reweighting to efficiently find sparse solutions corresponding to good aggregations. A comparative analysis of the proposed algorithm and the state-of-the-art greedy heuristic approach is presented, showing that the greedy heuristic implements a stepwise selection algorithm for the 𝓁₀-norm minimization problem. Further, we present an example where our approach succeeds, whereas the standard heuristic fails to find an aggregation with desired properties. The algorithm is implemented within the constraint integer programming solver SCIP, and computational experiments on the MIPLIB 2017 benchmark show that although the algorithm leads to slowdowns on relatively "easier" instances, our aggregation approach decreases the mean running time on a subset of challenging instances and leads to smaller branch-and-bound trees.
Cite as

Liding Xu, Gioni Mexi, and Ksenia Bestuzheva. Sparsity-Driven Aggregation of Mixed Integer Programs. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{xu_et_al:LIPIcs.SEA.2025.27,
  author =	{Xu, Liding and Mexi, Gioni and Bestuzheva, Ksenia},
  title =	{{Sparsity-Driven Aggregation of Mixed Integer Programs}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{27:1--27: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.27},
  URN =		{urn:nbn:de:0030-drops-232652},
  doi =		{10.4230/LIPIcs.SEA.2025.27},
  annote =	{Keywords: mixed integer linear programming, cutting plane, valid inequality, separation, aggregation, projection, sparse optimization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.104
Improved Approximation Algorithms for Three-Dimensional Bin Packing

Authors: Debajyoti Kar, Arindam Khan, and Malin Rau

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

Abstract
We study three fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3D-BP), 3D Strip Packing (3D-SP), and Minimum Volume Bounding Box (3D-MVBB), where given a set of 3D (rectangular) cuboids, the goal is to find an axis-aligned nonoverlapping packing of all cuboids. In 3D-BP, we need to pack the given cuboids into the minimum number of unit cube bins. In 3D-SP, we need to pack them into a 3D cuboid with a unit square base and minimum height. Finally, in 3D-MVBB, the goal is to pack into a cuboid box of minimum volume. It is NP-hard to even decide whether a set of rectangles can be packed into a unit square bin - giving an (absolute) approximation hardness of 2 for 3D-BP and 3D-SP. The previous best (absolute) approximation for all three problems is by Li and Cheng (SICOMP, 1990), who gave algorithms with approximation ratios of 13, 46/7, and 46/7+ε, respectively, for 3D-BP, 3D-SP, and 3D-MVBB. We provide improved approximation ratios of 6, 6, and 3+ε, respectively, for the three problems, for any constant ε > 0. For 3D-BP, in the asymptotic regime, Bansal, Correa, Kenyon, and Sviridenko (Math. Oper. Res., 2006) showed that there is no asymptotic polynomial-time approximation scheme (APTAS) even when all items have the same height. Caprara (Math. Oper. Res., 2008) gave an asymptotic approximation ratio of T_{∞}² + ε ≈ 2.86, where T_{∞} is the well-known Harmonic constant in Bin Packing. We provide an algorithm with an improved asymptotic approximation ratio of 3 T_{∞}/2 + ε ≈ 2.54. Further, we show that unlike 3D-BP (and 3D-SP), 3D-MVBB admits an APTAS.
Cite as

Debajyoti Kar, Arindam Khan, and Malin Rau. Improved Approximation Algorithms for Three-Dimensional Bin Packing. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 104:1-104:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kar_et_al:LIPIcs.ICALP.2025.104,
  author =	{Kar, Debajyoti and Khan, Arindam and Rau, Malin},
  title =	{{Improved Approximation Algorithms for Three-Dimensional Bin Packing}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{104:1--104: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.104},
  URN =		{urn:nbn:de:0030-drops-234814},
  doi =		{10.4230/LIPIcs.ICALP.2025.104},
  annote =	{Keywords: Approximation Algorithms, Geometric Packing, Multidimensional Packing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.60
Improved Approximation Algorithms for Three-Dimensional Knapsack

Authors: Klaus Jansen, Debajyoti Kar, Arindam Khan, K. V. N. Sreenivas, and Malte Tutas

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective is to find a non-overlapping axis-aligned packing (by translation) of the maximum profit subset of cuboids into the cube. The previous best approximation algorithm is due to Diedrich, Harren, Jansen, Thöle, and Thomas (2008), who gave a (7+ε)-approximation algorithm for 3DK and a (5+ε)-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant ε > 0. Chlebík and Chlebíková (2009) showed that the problem does not admit an asymptotic polynomial-time approximation scheme. We provide an improved polynomial-time (139/29+ε) ≈ 4.794-approximation algorithm for 3DK and (30/7+ε) ≈ 4.286-approximation when rotations by 90 degrees are allowed. We also provide improved approximation algorithms for several variants such as the cardinality case (when all items have the same profit) and uniform profit-density case (when the profit of an item is equal to its volume). Our key technical contribution is container packing - a structured packing in 3D such that all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. We first show the existence of highly profitable container packings. Thereafter, we show that one can find near-optimal container packing efficiently using a variant of the Generalized Assignment Problem (GAP).
Cite as

Klaus Jansen, Debajyoti Kar, Arindam Khan, K. V. N. Sreenivas, and Malte Tutas. Improved Approximation Algorithms for Three-Dimensional Knapsack. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.SoCG.2025.60,
  author =	{Jansen, Klaus and Kar, Debajyoti and Khan, Arindam and Sreenivas, K. V. N. and Tutas, Malte},
  title =	{{Improved Approximation Algorithms for Three-Dimensional Knapsack}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{60:1--60:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.60},
  URN =		{urn:nbn:de:0030-drops-232126},
  doi =		{10.4230/LIPIcs.SoCG.2025.60},
  annote =	{Keywords: Approximation Algorithms, Hyperrectangle Packing, Multidimensional Knapsack, Three-dimensional Packing}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.1
A Fast Heuristic Algorithm for the Train Unit Assignment Problem

Authors: Valentina Cacchiani, Alberto Caprara, and Paolo Toth

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
In this paper we study a railway optimization problem known as the Train Unit Assignment Problem. A train unit consists of a self-contained train with an engine and a set of wagons with passenger seats. Given a set of timetabled train trips, each with a required number of passenger seats, and a set of train units, each with a given number of available seats, the problem calls for the best assignment of the train units to the trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. We propose a heuristic algorithm based on the computation of a lower bound obtained by solving an Integer Linear Programming model that gives the optimal solution in a "peak period" of the day. The performance of the heuristic algorithm is computationally evaluated on real-world instances provided by a regional Italian Train Operator. The results are compared with those of existing methods from the literature, showing that the new method is able to obtain solutions of good quality in much shorter computing times.
Cite as

Valentina Cacchiani, Alberto Caprara, and Paolo Toth. A Fast Heuristic Algorithm for the Train Unit Assignment Problem. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{cacchiani_et_al:OASIcs.ATMOS.2012.1,
  author =	{Cacchiani, Valentina and Caprara, Alberto and Toth, Paolo},
  title =	{{A Fast Heuristic Algorithm for the Train Unit Assignment Problem}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.1},
  URN =		{urn:nbn:de:0030-drops-36971},
  doi =		{10.4230/OASIcs.ATMOS.2012.1},
  annote =	{Keywords: Train Unit Assignment, Heuristic Algorithm, ILP model, Real-world instances}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2011
OASIcs, Volume 20, ATMOS'11, Complete Volume

Authors: Alberto Caprara and Spyros Kontogiannis

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
OASIcs, Volume 20, ATMOS'11, Complete Volume
Cite as

11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{caprara_et_al:OASIcs.ATMOS.2011,
  title =	{{OASIcs, Volume 20, ATMOS'11, Complete Volume}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011},
  URN =		{urn:nbn:de:0030-drops-35824},
  doi =		{10.4230/OASIcs.ATMOS.2011},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2011.i
Frontmatter, Table of Contents, Preface, Workshop Organization

Authors: Alberto Caprara and Spyros Kontogiannis

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Frontmatter, Table of contents, Preface, Workshop Organization
Cite as

11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. i-ix, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{caprara_et_al:OASIcs.ATMOS.2011.i,
  author =	{Caprara, Alberto and Kontogiannis, Spyros},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{i--ix},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.i},
  URN =		{urn:nbn:de:0030-drops-32618},
  doi =		{10.4230/OASIcs.ATMOS.2011.i},
  annote =	{Keywords: Frontmatter, Table of contents, Preface, Workshop Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.1
Real-time traffic control in railway systems

Authors: Carlo Mannino

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Despite the constantly increasing demand of passengers and goods transport in Europe, the share of railway traffic is decreasing. One major reason appears to be congestion, which in turn results in frequent delays and in a general unreliability of the system. This fact has triggered the study of efficient ways to manage railway traffic, both off-line and real-time, by means of optimization and mathematical programming techniques. And yet, to our knowledge, there are only a few fully automated real-time traffic control systems which are actually in operation in the European railway system; in most cases such systems only control very simple lines and actually they only support the activity of human dispatchers. We describe here two recent optimization based applications to real-time traffic control which have actually been put into operation in the Italian railways. One such system has been able to fully control the trains in the terminal stations of Milano metro system. The other one will be fully operative by the end of 2012, when it will control the trains on several Italian single-track railways. Both systems heavily rely on mixed integer programming techniques to elaborate good quality timetables in real time.
Cite as

Carlo Mannino. Real-time traffic control in railway systems. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{mannino:OASIcs.ATMOS.2011.1,
  author =	{Mannino, Carlo},
  title =	{{Real-time traffic control in railway systems}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.1},
  URN =		{urn:nbn:de:0030-drops-32623},
  doi =		{10.4230/OASIcs.ATMOS.2011.1},
  annote =	{Keywords: Railway systems, traffic control}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.15
A bilevel rescheduling framework for optimal inter-area train coordination

Authors: Francesco Corman, Andrea D'Ariano, Dario Pacciarelli, and Marco Pranzo

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Railway dispatchers reschedule trains in real-time in order to limit the propagation of disturbances and to regulate traffic in their respective dispatching areas by minimizing the deviation from the off-line timetable. However, the decisions taken in one area may influence the quality and even the feasibility of train schedules in the other areas. Regional control centers coordinate the dispatchers' work for multiple areas in order to regulate traffic at the global level and to avoid situations of global infeasibility. Differently from the dispatcher problem, the coordination activity of regional control centers is still underinvestigated, even if this activity is a key factor for effective traffic management. This paper studies the problem of coordinating several dispatchers with the objective of driving their behavior towards globally optimal solutions. With our model, a coordinator may impose constraints at the border of each dispatching area. Each dispatcher must then schedule trains in its area by producing a locally feasible solution compliant with the border constraints imposed by the coordinator. The problem faced by the coordinator is therefore a bilevel programming problem in which the variables controlled by the coordinator are the border constraints. We demonstrate that the coordinator problem can be solved to optimality with a branch and bound procedure. The coordination algorithm has been tested on a large real railway network in the Netherlands with busy traffic conditions. Our experimental results show that a proven optimal solution is frequently found for various network divisions within computation times compatible with real-time operations.
Cite as

Francesco Corman, Andrea D'Ariano, Dario Pacciarelli, and Marco Pranzo. A bilevel rescheduling framework for optimal inter-area train coordination. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 15-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{corman_et_al:OASIcs.ATMOS.2011.15,
  author =	{Corman, Francesco and D'Ariano, Andrea and Pacciarelli, Dario and Pranzo, Marco},
  title =	{{A bilevel rescheduling framework for optimal inter-area train coordination}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{15--26},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.15},
  URN =		{urn:nbn:de:0030-drops-32636},
  doi =		{10.4230/OASIcs.ATMOS.2011.15},
  annote =	{Keywords: Train Delay Minimization, Schedule Coordination, Bilevel Programming}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.27
The Lockmaster's problem

Authors: Sofie Coene and Frits C. R. Spieksma

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Inland waterways form a natural network that is an existing, congestion free infrastructure with capacity for more traffic. The European commission promotes the transportation of goods by ship as it is a reliable, efficient and environmental friendly way of transport. A bottleneck for transportation over water are the locks that manage the water level. The lockmaster's problem concerns the optimal strategy for operating such a lock. In the lockmaster's problem we are given a lock, a set of ships coming from downstream that want to go upstream, and another set of ships coming from upstream that want to go downstream. We are given the arrival times of the ships and a constant lockage time; the goal is to minimize total waiting time of the ships. In this paper a dynamic programming algorithm (DP) is proposed that solves the lockmaster's problem in polynomial time. We extend this DP to different generalizations that consider weights, water usage, capacity, and (a fixed number of) multiple chambers. Finally, we prove that the problem becomes strongly NP-hard when the number of chambers is part of the input.
Cite as

Sofie Coene and Frits C. R. Spieksma. The Lockmaster's problem. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 27-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{coene_et_al:OASIcs.ATMOS.2011.27,
  author =	{Coene, Sofie and Spieksma, Frits C. R.},
  title =	{{The Lockmaster's problem}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{27--37},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.27},
  URN =		{urn:nbn:de:0030-drops-32647},
  doi =		{10.4230/OASIcs.ATMOS.2011.27},
  annote =	{Keywords: lock scheduling, batch scheduling, dynamic programming, complexity}
}
  • Refine by Type
  • 29 Document/PDF
  • 8 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 1 2026
  • 7 2025
  • 2 2012
  • 15 2011
  • 2 2010
  • Show More...

  • Refine by Author
  • 8 Caprara, Alberto
  • 4 Toth, Paolo
  • 3 Cacchiani, Valentina
  • 3 Galli, Laura
  • 2 Kar, Debajyoti
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs
  • 21 OASIcs

  • Refine by Classification
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Packing and covering problems
  • 1 Applied computing → Computational genomics
  • 1 Applied computing → Operations research
  • 1 Computing methodologies → Planning and scheduling
  • Show More...

  • Refine by Keyword
  • 3 Approximation Algorithms
  • 2 Column Generation
  • 2 Multidimensional Knapsack
  • 2 Train Routing
  • 2 complexity
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact