3 Search Results for "Laurent, Arnaud"

Document
DOI: 10.4230/LIPIcs.SAND.2023.7
When Should You Wait Before Updating? - Toward a Robustness Refinement

Authors: Swan Dubois, Laurent Feuilloley, Franck Petit, and Mikaël Rabie

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
Consider a dynamic network and a given distributed problem. At any point in time, there might exist several solutions that are equally good with respect to the problem specification, but that are different from an algorithmic perspective, because some could be easier to update than others when the network changes. In other words, one would prefer to have a solution that is more robust to topological changes in the network; and in this direction the best scenario would be that the solution remains correct despite the dynamic of the network. In [Arnaud Casteigts et al., 2020], the authors introduced a very strong robustness criterion: they required that for any removal of edges that maintain the network connected, the solution remains valid. They focus on the maximal independent set problem, and their approach consists in characterizing the graphs in which there exists a robust solution (the existential problem), or even stronger, where any solution is robust (the universal problem). As the robustness criteria is very demanding, few graphs have a robust solution, and even fewer are such that all of their solutions are robust. In this paper, we ask the following question: Can we have robustness for a larger class of networks, if we bound the number k of edge removals allowed? To answer this question, we consider three classic problems: maximal independent set, minimal dominating set and maximal matching. For the universal problem, the answers for the three cases are surprisingly different. For minimal dominating set, the class does not depend on the number of edges removed. For maximal matching, removing only one edge defines a robust class related to perfect matchings, but for all other bounds k, the class is the same as for an arbitrary number of edge removals. Finally, for maximal independent set, there is a strict hierarchy of classes: the class for the bound k is strictly larger than the class for bound k+1. For the robustness notion of [Arnaud Casteigts et al., 2020], no characterization of the class for the existential problem is known, only a polynomial-time recognition algorithm. We show that the situation is even worse for bounded k: even for k = 1, it is NP-hard to decide whether a graph has a robust maximal independent set.
Cite as

Swan Dubois, Laurent Feuilloley, Franck Petit, and Mikaël Rabie. When Should You Wait Before Updating? - Toward a Robustness Refinement. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dubois_et_al:LIPIcs.SAND.2023.7,
  author =	{Dubois, Swan and Feuilloley, Laurent and Petit, Franck and Rabie, Mika\"{e}l},
  title =	{{When Should You Wait Before Updating? - Toward a Robustness Refinement}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.7},
  URN =		{urn:nbn:de:0030-drops-179435},
  doi =		{10.4230/LIPIcs.SAND.2023.7},
  annote =	{Keywords: Robustness, dynamic network, temporal graphs, edge removal, connectivity, footprint, packing/covering problems, maximal independent set, maximal matching, minimum dominating set, perfect matching, NP-hardness}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2022.5
A Bilevel Model for the Frequency Setting Problem

Authors: Hector Gatt, Jean-Marie Freche, Arnaud Laurent, and Fabien Lehuédé

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract
Based on a partnership between IMT Atlantique and the French company Lumiplan, this work is part of a process of strengthening the Heurès software currently offered by Lumiplan to public transport operators to support their bus and driver scheduling operations. This work addresses the frequency setting problem which aims at defining the frequencies of the bus lines of a network for different time periods of a day. This operation complements a study on line planning with more accurate estimations of the demand, necessary bus types and passengers behaviors. In this paper, the operator’s exploitation costs are minimized while respecting service-levels constraints, based on the predictions of the path choice made by the passengers. The problem is solved by an easily implementable process and a case study based on a real network is presented to show the efficiency of our method.
Cite as

Hector Gatt, Jean-Marie Freche, Arnaud Laurent, and Fabien Lehuédé. A Bilevel Model for the Frequency Setting Problem. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 5:1-5:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gatt_et_al:OASIcs.ATMOS.2022.5,
  author =	{Gatt, Hector and Freche, Jean-Marie and Laurent, Arnaud and Lehu\'{e}d\'{e}, Fabien},
  title =	{{A Bilevel Model for the Frequency Setting Problem}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{5:1--5:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.5},
  URN =		{urn:nbn:de:0030-drops-171091},
  doi =		{10.4230/OASIcs.ATMOS.2022.5},
  annote =	{Keywords: Frequency Setting, Service Performance, Bilevel, Passenger Assignment}
}
Document
DOI: 10.4230/LIPIcs.CSL.2016.20
Descriptive Complexity of #AC^0 Functions

Authors: Arnaud Durand, Anselm Haak, Juha Kontinen, and Heribert Vollmer

Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Abstract
We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC^0 appear as classes of this hierarchy. In this way, we unconditionally place #AC^0 properly in a strict hierarchy of arithmetic classes within #P. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. We argue that our approach is better suited to study arithmetic circuit classes such as #AC^0 which can be descriptively characterized as a class in our framework.
Cite as

Arnaud Durand, Anselm Haak, Juha Kontinen, and Heribert Vollmer. Descriptive Complexity of #AC^0 Functions. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{durand_et_al:LIPIcs.CSL.2016.20,
  author =	{Durand, Arnaud and Haak, Anselm and Kontinen, Juha and Vollmer, Heribert},
  title =	{{Descriptive Complexity of #AC^0 Functions}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Talbot, Jean-Marc and Regnier, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.20},
  URN =		{urn:nbn:de:0030-drops-65601},
  doi =		{10.4230/LIPIcs.CSL.2016.20},
  annote =	{Keywords: finite model theory, Fagin's theorem, arithmetic circuits, counting classes, Skolem function}
}
  • Refine by Author
  • 1 Dubois, Swan
  • 1 Durand, Arnaud
  • 1 Feuilloley, Laurent
  • 1 Freche, Jean-Marie
  • 1 Gatt, Hector
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Networks → Network design and planning algorithms
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Bilevel
  • 1 Fagin's theorem
  • 1 Frequency Setting
  • 1 NP-hardness
  • 1 Passenger Assignment
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2016
  • 1 2022
  • 1 2023

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