La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Approximation Preserving Reductions among Item Pricing Problems L’approximation préserve les réductions parmi les problèmes de prix des articles

Ryoso HAMANE, Toshiya ITOH, Kouhei TOMITA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Lorsqu'un magasin vend des articles à des clients, il souhaite déterminer les prix des articles afin de maximiser son profit. Intuitivement, si le magasin vend des articles à des prix bas (resp. élevés), les clients achètent plus (resp. moins) d’articles, ce qui génère moins de profit pour le magasin. Il serait donc difficile pour le magasin de décider des prix des articles. Supposons que le magasin dispose d'un ensemble V of n articles et il y a un ensemble E of m clients qui souhaitent acheter ces articles, et supposent également que chaque article iV a le coût de production di et chaque client ejE a la valorisation vj sur le paquet ejV d'articles. Quand le magasin vend un article iV au prix ri, le bénéfice pour l'article i is pi=ri-di. Le but du magasin est de décider du prix de chaque article afin de maximiser son profit total. Nous appelons ce problème de maximisation le prix des articles problème. Dans la plupart des travaux précédents, le problème de la tarification des articles a été considéré sous l'hypothèse que pi ≥ 0 pour chacun iV, cependant, Balcan et al. [Dans Proc. of WINE, LNCS 4858, 2007] a introduit la notion de « produit d'appel » et a montré que le vendeur peut obtenir un profit total plus important dans le cas où pi < 0 est autorisé que dans le cas où pi < 0 n'est pas autorisé. Dans cet article, nous dérivons des réductions préservant l'approximation parmi plusieurs problèmes de tarification d'articles et montrons que tous ont des algorithmes avec un bon rapport d'approximation.

Publication
IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.149-157
Date de publication
2009/02/01
Publicisé
ISSN en ligne
1745-1361
DOI
10.1587/transinf.E92.D.149
Type de manuscrit
Special Section PAPER (Special Section on Foundations of Computer Science)
Catégories

Auteurs

Mots-clés

Table des matières