10 Search Results for "Mar�n, Angel"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.7
Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets

Authors: Ángel Javier Alonso and Michael Kerber

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We study the decomposition of zero-dimensional persistence modules, viewed as functors valued in the category of vector spaces factorizing through sets. Instead of working directly at the level of vector spaces, we take a step back and first study the decomposition problem at the level of sets. This approach allows us to define the combinatorial notion of rooted subsets. In the case of a filtered metric space M, rooted subsets relate the clustering behavior of the points of M with the decomposition of the associated persistence module. In particular, we can identify intervals in such a decomposition quickly. In addition, rooted subsets can be understood as a generalization of the elder rule, and are also related to the notion of constant conqueror of Cai, Kim, Mémoli and Wang. As an application, we give a lower bound on the number of intervals that we can expect in the decomposition of zero-dimensional persistence modules of a density-Rips filtration in Euclidean space: in the limit, and under very general circumstances, we can expect that at least 25% of the indecomposable summands are interval modules.
Cite as

Ángel Javier Alonso and Michael Kerber. Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alonso_et_al:LIPIcs.SoCG.2023.7,
  author =	{Alonso, \'{A}ngel Javier and Kerber, Michael},
  title =	{{Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.7},
  URN =		{urn:nbn:de:0030-drops-178570},
  doi =		{10.4230/LIPIcs.SoCG.2023.7},
  annote =	{Keywords: Multiparameter persistent homology, Clustering, Decomposition of persistence modules, Elder Rule}
}
Document
DOI: 10.4230/OASIcs.FMBC.2022.3
Automatic Generation of Attacker Contracts in Solidity

Authors: Ignacio Ballesteros, Clara Benac-Earle, Luis Eduardo Bueso de Barrio, Lars-Åke Fredlund, Ángel Herranz, and Julio Mariño

Published in: OASIcs, Volume 105, 4th International Workshop on Formal Methods for Blockchains (FMBC 2022)

Abstract
Smart contracts on the Ethereum blockchain continue to suffer from well-published problems. A particular example is the well-known smart contract reentrancy vulnerability, which continues to be exploited. In this article, we present preliminary work on a method which, given a smart contract that may be vulnerable to such a reentrancy attack, proceeds to attempt to automatically derive an "attacker" contract which can be used to successfully attack the vulnerable contract. The method uses property-based testing to generate, semi-randomly, large numbers of potential attacker contracts, and then proceeds to check whether any of them is a successful attacker. The method is illustrated using a case study where an attack is derived for a vulnerable contract.
Cite as

Ignacio Ballesteros, Clara Benac-Earle, Luis Eduardo Bueso de Barrio, Lars-Åke Fredlund, Ángel Herranz, and Julio Mariño. Automatic Generation of Attacker Contracts in Solidity. In 4th International Workshop on Formal Methods for Blockchains (FMBC 2022). Open Access Series in Informatics (OASIcs), Volume 105, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ballesteros_et_al:OASIcs.FMBC.2022.3,
  author =	{Ballesteros, Ignacio and Benac-Earle, Clara and de Barrio, Luis Eduardo Bueso and Fredlund, Lars-\r{A}ke and Herranz, \'{A}ngel and Mari\~{n}o, Julio},
  title =	{{Automatic Generation of Attacker Contracts in Solidity}},
  booktitle =	{4th International Workshop on Formal Methods for Blockchains (FMBC 2022)},
  pages =	{3:1--3:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-250-1},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{105},
  editor =	{Dargaye, Zaynah and Schneidewind, Clara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.FMBC.2022.3},
  URN =		{urn:nbn:de:0030-drops-171840},
  doi =		{10.4230/OASIcs.FMBC.2022.3},
  annote =	{Keywords: Property-Based Testing, Smart Contracts, Reentrancy Attack}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.28
Improved Black-Box Constructions of Composable Secure Computation

Authors: Rohit Chatterjee, Xiao Liang, and Omkant Pandey

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We close the gap between black-box and non-black-box constructions of composable secure multiparty computation in the plain model under the minimal assumption of semi-honest oblivious transfer. The notion of protocol composition we target is angel-based security, or more precisely, security with super-polynomial helpers. In this notion, both the simulator and the adversary are given access to an oracle called an angel that can perform some predefined super-polynomial time task. Angel-based security maintains the attractive properties of the universal composition framework while providing meaningful security guarantees in complex environments without having to trust anyone. Angel-based security can be achieved using non-black-box constructions in max(R_OT,Õ(log n)) rounds where R_OT is the round-complexity of semi-honest oblivious transfer. However, current best known black-box constructions under the same assumption require max(R_OT,Õ(log² n)) rounds. If R_OT is a constant, the gap between non-black-box and black-box constructions can be a multiplicative factor log n. We close this gap by presenting a max(R_OT,Õ(log n)) round black-box construction. We achieve this result by constructing constant-round 1-1 CCA-secure commitments assuming only black-box access to one-way functions.
Cite as

Rohit Chatterjee, Xiao Liang, and Omkant Pandey. Improved Black-Box Constructions of Composable Secure Computation. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.ICALP.2020.28,
  author =	{Chatterjee, Rohit and Liang, Xiao and Pandey, Omkant},
  title =	{{Improved Black-Box Constructions of Composable Secure Computation}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.28},
  URN =		{urn:nbn:de:0030-drops-124351},
  doi =		{10.4230/LIPIcs.ICALP.2020.28},
  annote =	{Keywords: Secure Multi-Party Computation, Black-Box, Composable, Non-Malleable}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.65
Dense Graphs Have Rigid Parts

Authors: Orit E. Raz and József Solymosi

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
While the problem of determining whether an embedding of a graph G in ℝ² is infinitesimally rigid is well understood, specifying whether a given embedding of G is rigid or not is still a hard task that usually requires ad hoc arguments. In this paper, we show that every embedding (not necessarily generic) of a dense enough graph (concretely, a graph with at least C₀n^{3/2}(log n)^β edges, for some absolute constants C₀>0 and β), which satisfies some very mild general position requirements (no three vertices of G are embedded to a common line), must have a subframework of size at least three which is rigid. For the proof we use a connection, established in Raz [Discrete Comput. Geom., 2017], between the notion of graph rigidity and configurations of lines in ℝ³. This connection allows us to use properties of line configurations established in Guth and Katz [Annals Math., 2015]. In fact, our proof requires an extended version of Guth and Katz result; the extension we need is proved by János Kollár in an Appendix to our paper. We do not know whether our assumption on the number of edges being Ω(n^{3/2}log n) is tight, and we provide a construction that shows that requiring Ω(n log n) edges is necessary.
Cite as

Orit E. Raz and József Solymosi. Dense Graphs Have Rigid Parts. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.SoCG.2020.65,
  author =	{Raz, Orit E. and Solymosi, J\'{o}zsef},
  title =	{{Dense Graphs Have Rigid Parts}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.65},
  URN =		{urn:nbn:de:0030-drops-122236},
  doi =		{10.4230/LIPIcs.SoCG.2020.65},
  annote =	{Keywords: Graph rigidity, line configurations in 3D}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.73
Smoothed Efficient Algorithms and Reductions for Network Coordination Games

Authors: Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We study the smoothed complexity of finding pure Nash equilibria in Network Coordination Games, a PLS-complete problem in the worst case, even when each player has two strategies. This is a potential game where the sequential-better-response algorithm is known to converge to a pure NE, albeit in exponential time. First, we prove polynomial (respectively, quasi-polynomial) smoothed complexity when the underlying game graph is complete (resp. arbitrary), and every player has constantly many strategies. The complete graph assumption is reminiscent of perturbing all parameters, a common assumption in most known polynomial smoothed complexity results. We develop techniques to bound the probability that an (adversarial) better-response sequence makes slow improvements to the potential. Our approach combines and generalizes the local-max-cut approaches of Etscheid and Röglin (SODA `14; ACM TALG, `17) and Angel, Bubeck, Peres, and Wei (STOC `17), to handle the multi-strategy case. We believe that the approach and notions developed herein could be of interest in addressing the smoothed complexity of other potential games. Further, we define a notion of a smoothness-preserving reduction among search problems, and obtain reductions from 2-strategy network coordination games to local-max-cut, and from k-strategy games (k arbitrary) to local-max-bisection. The former, with the recent result of Bibak, Chandrasekaran, and Carlson (SODA `18) gives an alternate O(n^8)-time smoothed algorithm when k=2. These reductions extend smoothed efficient algorithms from one problem to another.
Cite as

Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. Smoothed Efficient Algorithms and Reductions for Network Coordination Games. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{boodaghians_et_al:LIPIcs.ITCS.2020.73,
  author =	{Boodaghians, Shant and Kulkarni, Rucha and Mehta, Ruta},
  title =	{{Smoothed Efficient Algorithms and Reductions for Network Coordination Games}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{73:1--73:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.73},
  URN =		{urn:nbn:de:0030-drops-117581},
  doi =		{10.4230/LIPIcs.ITCS.2020.73},
  annote =	{Keywords: Network Coordination Games, Smoothed Analysis}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.26
The String of Diamonds Is Tight for Rumor Spreading

Authors: Omer Angel, Abbas Mehrabian, and Yuval Peres

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

Abstract
For a rumor spreading protocol, the spread time is defined as the first time that everyone learns the rumor. We compare the synchronous push&pull rumor spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by O(n^{1/3} log^{2/3} n). This improves the O(sqrt n) upper bound of Giakkoupis, Nazari, and Woelfel (in Proceedings of ACM Symposium on Principles of Distributed Computing, 2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph.
Cite as

Omer Angel, Abbas Mehrabian, and Yuval Peres. The String of Diamonds Is Tight for Rumor Spreading. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 26:1-26:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{angel_et_al:LIPIcs.APPROX-RANDOM.2017.26,
  author =	{Angel, Omer and Mehrabian, Abbas and Peres, Yuval},
  title =	{{The String of Diamonds Is Tight for Rumor Spreading}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{26:1--26:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.26},
  URN =		{urn:nbn:de:0030-drops-75754},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.26},
  annote =	{Keywords: randomized rumor spreading, push\&pull protocol, asynchronous time model, string of diamonds}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.53
Throughput Maximization in the Speed-Scaling Setting

Authors: Eric Angel, Evripidis Bampis, and Vincent Chau

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We are given a set of n jobs and a single processor that can vary its speed dynamically. Each job J_j is characterized by its processing requirement (work) p_j, its release date r_j and its deadline d_j. We are also given a budget of energy E and we study the scheduling problem of maximizing the throughput (i.e. the number of jobs that are completed on time). While the preemptive energy minimization problem has been solved in polynomial time [Yao et al., FOCS'95], the complexity of the problem of maximizing the throughput remained open until now. We answer partially this question by providing a dynamic programming algorithm that solves the problem in pseudo-polynomial time. While our result shows that the problem is not strongly NP-hard, the question of whether the problem can be solved in polynomial time remains a challenging open question. Our algorithm can also be adapted for solving the weighted version of the problem where every job is associated with a weight w_j and the objective is the maximization of the sum of the weights of the jobs that are completed on time.
Cite as

Eric Angel, Evripidis Bampis, and Vincent Chau. Throughput Maximization in the Speed-Scaling Setting. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 53-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{angel_et_al:LIPIcs.STACS.2014.53,
  author =	{Angel, Eric and Bampis, Evripidis and Chau, Vincent},
  title =	{{Throughput Maximization in the Speed-Scaling Setting}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{53--62},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.53},
  URN =		{urn:nbn:de:0030-drops-44469},
  doi =		{10.4230/LIPIcs.STACS.2014.53},
  annote =	{Keywords: energy efficiency, dynamic speed scaling, offline algorithm, throughput, dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2011.95
Synthesis of Logic Programs from Object-Oriented Formal Specifications

Authors: Ángel Herranz and Julio Mariño

Published in: LIPIcs, Volume 11, Technical Communications of the 27th International Conference on Logic Programming (ICLP'11) (2011)

Abstract
Early validation of requirements is crucial for the rigorous development of software. Without it, even the most formal of the methodologies will produce the wrong outcome. One successful approach, popularised by some of the so-called lightweight formal methods, consists in generating (finite, small) models of the specifications. Another possibility is to build a running prototype from those specifications. In this paper we show how to obtain executable prototypes from formal specifications written in an object oriented notation by translating them into logic programs. This has some advantages over other lightweight methodologies. For instance, we recover the possibility of dealing with recursive data types as specifications that use them often lack finite models.
Cite as

Ángel Herranz and Julio Mariño. Synthesis of Logic Programs from Object-Oriented Formal Specifications. In Technical Communications of the 27th International Conference on Logic Programming (ICLP'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 11, pp. 95-105, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{herranz_et_al:LIPIcs.ICLP.2011.95,
  author =	{Herranz, \'{A}ngel and Mari\~{n}o, Julio},
  title =	{{Synthesis of Logic Programs from Object-Oriented Formal Specifications}},
  booktitle =	{Technical Communications of the 27th International Conference on Logic Programming (ICLP'11)},
  pages =	{95--105},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-31-6},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{11},
  editor =	{Gallagher, John P. and Gelfond, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2011.95},
  URN =		{urn:nbn:de:0030-drops-31810},
  doi =		{10.4230/LIPIcs.ICLP.2011.95},
  annote =	{Keywords: Formal Methods, Logic Program Synthesis, Object-Oriented, Executable Specifications, Correct-by-Construction}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2007.1177
01. A new concept of robustness

Authors: Ricardo García, Ángel Marín, Juan A. Mesa, Federico Perea, and Doroteo Verastegui

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract
In this paper a new concept of robustness is introduced and the corresponding optimization problem is stated. This new concept is applied to transportation network designs in which the set of scenarios arising from the uncertainty of the parameters follows a probability distribution. The $p$-robustness concept is aimed to problems where the feasibility of the solutions is not affected by the uncertainty of the parameters. In order to compare the solution with those of other already known concepts of robustness, some computational experiments with real data are included.
Cite as

Ricardo García, Ángel Marín, Juan A. Mesa, Federico Perea, and Doroteo Verastegui. 01. A new concept of robustness. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{garcia_et_al:OASIcs.ATMOS.2007.1177,
  author =	{Garc{\'\i}a, Ricardo and Mar{\'\i}n, \'{A}ngel and Mesa, Juan A. and Perea, Federico and Verastegui, Doroteo},
  title =	{{01. A new concept of robustness}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{1--14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1177},
  URN =		{urn:nbn:de:0030-drops-11779},
  doi =		{10.4230/OASIcs.ATMOS.2007.1177},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/OASIcs.ATMOS.2005.658
Analysis of the Parameters of Transfers in Rapid Transit Network Design

Authors: Ricardo García, Armando Garzón-Astolfi, Angel Marín, Juan A. Mesa, and Francisco A. Ortega

Published in: OASIcs, Volume 2, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05) (2006)

Abstract
The rapid transit network design problem consists of the location of train alignments and stations in an urban traffic context. The originality of our study is to incorporate into the location model the decisions about the transportation mode and the route, to be chosen for urban trips. This paper proposes a new design model which includes transfers between train lines. The objective of the model is to maximize the number of expected users in the transit network taking limited budgets into consideration, in addition to location and allocation constraints. Furthermore, the transfer costs are considered in the generalized public costs when the users change lines. Waiting time to take the metro and walking time to transfer is included in the formulation of the costs. The analysis of transfer parameters is carried out using a test network. Some computational experience is included in the paper.
Cite as

Ricardo García, Armando Garzón-Astolfi, Angel Marín, Juan A. Mesa, and Francisco A. Ortega. Analysis of the Parameters of Transfers in Rapid Transit Network Design. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{garcia_et_al:OASIcs.ATMOS.2005.658,
  author =	{Garc{\'\i}a, Ricardo and Garz\'{o}n-Astolfi, Armando and Mar{\'\i}n, Angel and Mesa, Juan A. and Ortega, Francisco A.},
  title =	{{Analysis of the Parameters of Transfers in Rapid Transit Network Design}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{1--15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-00-2},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{2},
  editor =	{Kroon, Leo G. and M\"{o}hring, Rolf H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.658},
  URN =		{urn:nbn:de:0030-drops-6583},
  doi =		{10.4230/OASIcs.ATMOS.2005.658},
  annote =	{Keywords: Parameter analysis, rapid transit network design, trip choice in urban traffic}
}
  • Refine by Author
  • 2 García, Ricardo
  • 2 Herranz, Ángel
  • 2 Mariño, Julio
  • 2 Mesa, Juan A.
  • 1 Alonso, Ángel Javier
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Topology
  • 1 Security and privacy → Mathematical foundations of cryptography
  • 1 Software and its engineering → Dynamic analysis
  • Show More...

  • Refine by Keyword
  • 1 Black-Box
  • 1 Clustering
  • 1 Composable
  • 1 Correct-by-Construction
  • 1 Decomposition of persistence modules
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 3 2020
  • 1 2006
  • 1 2007
  • 1 2011
  • 1 2014
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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