3 Search Results for "Ga�ner, Christine"

Document
DOI: 10.4230/LIPIcs.CP.2022.19
Sequence Variables for Routing Problems

Authors: Augustin Delecluse, Pierre Schaus, and Pascal Van Hentenryck

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Constraint Programming (CP) is one of the most flexible approaches for modeling and solving vehicle routing problems (VRP). This paper proposes the sequence variable domain, that is inspired by the insertion graph introduced in [Bent and Van Hentenryck, 2004] and the subset bound domain for set variables. This domain representation, which targets VRP applications, allows for an efficient insertion-based search on a partial tour and the implementation of simple, yet efficient filtering algorithms for constraints that enforce time-windows on the visits and capacities on the vehicles. Experiment results demonstrate the efficiency and flexibility of this CP domain for solving some hard VRP problems, including the Dial-A-Ride, the Patient Transportation, and the asymmetric TSP with time windows.
Cite as

Augustin Delecluse, Pierre Schaus, and Pascal Van Hentenryck. Sequence Variables for Routing Problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{delecluse_et_al:LIPIcs.CP.2022.19,
  author =	{Delecluse, Augustin and Schaus, Pierre and Van Hentenryck, Pascal},
  title =	{{Sequence Variables for Routing Problems}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.19},
  URN =		{urn:nbn:de:0030-drops-166485},
  doi =		{10.4230/LIPIcs.CP.2022.19},
  annote =	{Keywords: Constraint Programming, Dial-A-Ride, Patient Transportation, TSPTW, Vehicle Routing, Sequence Variables, Insertion Variables}
}
Document
DOI: 10.4230/LIPIcs.CSL.2021.22
Computing Measure as a Primitive Operation in Real Number Computation

Authors: Christine Gaßner, Arno Pauly, and Florian Steinberg

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)

Abstract
We study the power of BSS-machines enhanced with abilities such as computing the measure of a BSS-decidable set or computing limits of BSS-computable converging sequences. Our variations coalesce into just two equivalence classes, each of which also can be described as a lower cone in the Weihrauch degrees. We then classify computational tasks such as computing the measure of Δ⁰₂-set of reals, integrating piece-wise continuous functions and recovering a continuous function from an L₁([0, 1])-description. All these share the Weihrauch degree lim.
Cite as

Christine Gaßner, Arno Pauly, and Florian Steinberg. Computing Measure as a Primitive Operation in Real Number Computation. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganer_et_al:LIPIcs.CSL.2021.22,
  author =	{Ga{\ss}ner, Christine and Pauly, Arno and Steinberg, Florian},
  title =	{{Computing Measure as a Primitive Operation in Real Number Computation}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{22:1--22:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.22},
  URN =		{urn:nbn:de:0030-drops-134564},
  doi =		{10.4230/LIPIcs.CSL.2021.22},
  annote =	{Keywords: BSS-machine, Weihrauch reducibility, integrable function, Lebesgue measure, computable analysis}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2266
Relativizations of the P =? DNP Question for the BSS Model

Authors: Christine Gaßner

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
We consider the uniform BSS model of computation where the machines can perform additions, multiplications, and tests of the form $x\geq 0$. The oracle machines can also check whether a tuple of real numbers belongs to a given oracle set ${\cal O}$ or not. We construct oracles such that the classes P and DNP relative to these oracles are equal or not equal.
Cite as

Christine Gaßner. Relativizations of the P =? DNP Question for the BSS Model. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 141-148, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ganer:OASIcs.CCA.2009.2266,
  author =	{Ga{\ss}ner, Christine},
  title =	{{Relativizations  of the   P =? DNP Question for the BSS Model}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{141--148},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2266},
  URN =		{urn:nbn:de:0030-drops-22667},
  doi =		{10.4230/OASIcs.CCA.2009.2266},
  annote =	{Keywords: BSS machines, oracle machines, relativizations, P-DNP problem, real knapsack problem}
}
  • Refine by Author
  • 2 Gaßner, Christine
  • 1 Delecluse, Augustin
  • 1 Pauly, Arno
  • 1 Schaus, Pierre
  • 1 Steinberg, Florian
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Integral calculus
  • 1 Mathematics of computing → Point-set topology
  • 1 Theory of computation → Abstract machines
  • 1 Theory of computation → Constraint and logic programming
  • 1 Theory of computation → Turing machines

  • Refine by Keyword
  • 1 BSS machines
  • 1 BSS-machine
  • 1 Constraint Programming
  • 1 Dial-A-Ride
  • 1 Insertion Variables
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2009
  • 1 2021
  • 1 2022

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