Publikation:

Algorithms for Average Regret Minimization

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2019

Autor:innen

Funke, Stefan

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

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

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2019, pp. 1600-1607. ISSN 2159-5399. eISSN 2374-3468. ISBN 978-1-57735-809-1

Zusammenfassung

In this paper, we study a problem from the realm of multicriteria decision making in which the goal is to select from a given set S of d-dimensional objects a minimum sized subset S0 with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set S but now can only select their favorite object from the subset S0. Previous work focused on bounding the maximum regret which is determined by the most unhappy user. We propose to consider the average regret instead which is determined by the sum of (un)happiness of all possible users. We show that this regret measure comes with desirable properties as supermodularity which allows to construct approximation algorithms. Furthermore, we introduce the regret minimizing permutation problem and discuss extensions of our algorithms to the recently proposed k-regret measure. Our theoretical results are accompanied with experiments on a variety of inputs with d up to 7.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19), 27. Jan. 2019 - 1. Feb. 2019, Honolulu
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690STORANDT, Sabine, Stefan FUNKE, 2019. Algorithms for Average Regret Minimization. The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). Honolulu, 27. Jan. 2019 - 1. Feb. 2019. In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2019, pp. 1600-1607. ISSN 2159-5399. eISSN 2374-3468. ISBN 978-1-57735-809-1
BibTex
@inproceedings{Storandt2019Algor-46796,
  year={2019},
  title={Algorithms for Average Regret Minimization},
  isbn={978-1-57735-809-1},
  issn={2159-5399},
  publisher={AAAI Press},
  address={Palo Alto},
  booktitle={Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence},
  pages={1600--1607},
  author={Storandt, Sabine and Funke, Stefan}
}
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/46796">
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-09-05T10:51:51Z</dcterms:available>
    <dcterms:issued>2019</dcterms:issued>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/46796"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:title>Algorithms for Average Regret Minimization</dcterms:title>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:language>eng</dc:language>
    <dcterms:abstract xml:lang="eng">In this paper, we study a problem from the realm of multicriteria decision making in which the goal is to select from a given set S of d-dimensional objects a minimum sized subset S&lt;sup&gt;0&lt;/sup&gt; with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set S but now can only select their favorite object from the subset S&lt;sup&gt;0&lt;/sup&gt;. Previous work focused on bounding the maximum regret which is determined by the most unhappy user. We propose to consider the average regret instead which is determined by the sum of (un)happiness of all possible users. We show that this regret measure comes with desirable properties as supermodularity which allows to construct approximation algorithms. Furthermore, we introduce the regret minimizing permutation problem and discuss extensions of our algorithms to the recently proposed k-regret measure. Our theoretical results are accompanied with experiments on a variety of inputs with d up to 7.</dcterms:abstract>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-09-05T10:51:51Z</dc:date>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dc:contributor>Funke, Stefan</dc:contributor>
    <dc:creator>Funke, Stefan</dc:creator>
  </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