Publikation:

On the Multi-Kind BahnCard Problem

Vorschaubild

Dateien

Timm_2-805k5xro2u4a7.pdf
Timm_2-805k5xro2u4a7.pdfGröße: 510.69 KBDownloads: 222

Datum

2020

Autor:innen

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
http://nbn-resolving.de/urn:nbn:de:bsz:352-2-805k5xro2u4a7
DOI (zitierfähiger Link)
https://doi.org/10.4230/OASIcs.ATMOS.2020.2
ArXiv-ID

Internationale Patentnummer

Link zur Lizenz
Attribution 3.0 Unported

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Bookpart

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

HUISMAN, Dennis, ed., Christos D. ZAROLIAGIS, ed.. 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Saarbrücken/Wadern: Dagstuhl Publishing, 2020, 2. OpenAccess Series in Informatics (OASIcs). 85. eISSN 1868-8969. ISBN 978-3-95977-170-2. Available under: doi: 10.4230/OASIcs.ATMOS.2020.2

Zusammenfassung

The BahnCard problem is an important problem in the realm of online decision making. In its original form, there is one kind of BahnCard associated with a certain price, which upon purchase reduces the ticket price of train journeys for a certain factor over a certain period of time. The problem consists of deciding on which dates BahnCards should be purchased such that the overall cost, that is, BahnCard prices plus (reduced) ticket prices, is minimized without having knowledge about the number and prices of future journeys. In this paper, we extend the problem such that multiple kinds of BahnCards are available for purchase. We provide an optimal offline algorithm, as well as online strategies with provable competitiveness factors. Furthermore, we describe and implement several heuristic online strategies and compare their competitiveness in realistic scenarios.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

offline solution, competitiveness, traveller profiles

Konferenz

20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), 7. Sept. 2020 - 8. Sept. 2020, Pisa
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690TIMM, Mike, Sabine STORANDT, 2020. On the Multi-Kind BahnCard Problem. 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Pisa, 7. Sept. 2020 - 8. Sept. 2020. In: HUISMAN, Dennis, ed., Christos D. ZAROLIAGIS, ed.. 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Saarbrücken/Wadern: Dagstuhl Publishing, 2020, 2. OpenAccess Series in Informatics (OASIcs). 85. eISSN 1868-8969. ISBN 978-3-95977-170-2. Available under: doi: 10.4230/OASIcs.ATMOS.2020.2
BibTex
@inproceedings{Timm2020Multi-52930,
  year={2020},
  doi={10.4230/OASIcs.ATMOS.2020.2},
  title={On the Multi-Kind BahnCard Problem},
  number={85},
  isbn={978-3-95977-170-2},
  publisher={Dagstuhl Publishing},
  address={Saarbrücken/Wadern},
  series={OpenAccess Series in Informatics (OASIcs)},
  booktitle={20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  editor={Huisman, Dennis and Zaroliagis, Christos D.},
  author={Timm, Mike and Storandt, Sabine},
  note={Article Number: 2}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52930">
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:title>On the Multi-Kind BahnCard Problem</dcterms:title>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-02-19T09:54:12Z</dcterms:available>
    <dc:rights>Attribution 3.0 Unported</dc:rights>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>eng</dc:language>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:creator>Timm, Mike</dc:creator>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dcterms:abstract xml:lang="eng">The BahnCard problem is an important problem in the realm of online decision making. In its original form, there is one kind of BahnCard associated with a certain price, which upon purchase reduces the ticket price of train journeys for a certain factor over a certain period of time. The problem consists of deciding on which dates BahnCards should be purchased such that the overall cost, that is, BahnCard prices plus (reduced) ticket prices, is minimized without having knowledge about the number and prices of future journeys. In this paper, we extend the problem such that multiple kinds of BahnCards are available for purchase. We provide an optimal offline algorithm, as well as online strategies with provable competitiveness factors. Furthermore, we describe and implement several heuristic online strategies and compare their competitiveness in realistic scenarios.</dcterms:abstract>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/52930"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-02-19T09:54:12Z</dc:date>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/52930/1/Timm_2-805k5xro2u4a7.pdf"/>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by/3.0/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/52930/1/Timm_2-805k5xro2u4a7.pdf"/>
    <dcterms:issued>2020</dcterms:issued>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Timm, Mike</dc:contributor>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen