Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 1/2020

22.04.2019

The Clever Shopper Problem

verfasst von: Laurent Bulteau, Danny Hermelin, Dušan Knop, Anthony Labarre, Stéphane Vialette

Erschienen in: Theory of Computing Systems | Ausgabe 1/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We investigate a variant of the so-called Internet Shopping problem introduced by Blazewicz et al. (Appl. Math. Comput. Sci. 20, 385–390, 2010), where a customer wants to buy a list of products at the lowest possible total cost from shops which offer discounts when purchases exceed a certain threshold. Although the problem is NP-hard, we provide exact algorithms for several cases, e.g. when each shop sells only two items, and an FPT algorithm for the number of items, or for the number of shops when all prices are equal. We complement each result with hardness proofs in order to draw a tight boundary between tractable and intractable cases. Finally, we give an approximation algorithm and hardness results for the problem of maximising the sum of discounts
Vorheriger Artikel Recognizing Read-Once Functions from Depth-Three Formulas
Nächster Artikel Slopes of Multidimensional Subshifts

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Altmanová, K., Knop, D., Koutecký, M.: Evaluating and tuning n-fold integer programming. In: D’Angelo, G. (ed.) 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L’Aquila, Italy, vol. 103 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 10:1–10:14 (2018)MathSciNetCrossRef
2.
Assmann, S., Johnson, D., Kleitman, D., Leung, J.-T.: On a dual version of the one-dimensional bin packing problem. J. Algorithms 5, 502–525 (1984)MathSciNetCrossRef
3.
Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT electronic colloquium on computational complexity (ECCC) (2003)
4.
Blazewicz, J., Kovalyov, M.Y., Musial, J., Urbanski, A.P., Wojciechowski, A.: Internet shopping optimization problem. Appl. Math. Comput. Sci. 20, 385–390 (2010)MATH
5.
Blazewicz, J., Bouvry, P., Kovalyov, M.Y., Musial, J.: Internet shopping with price sensitive discounts. 4OR 12, 35–48 (2014)MathSciNetCrossRef
6.
Blazewicz, J., Cheriere, N., Dutot, P.-F., Musial, J., Trystram, D.: Novel dual discounting functions for the internet shopping optimization problem: new algorithms. J. Sched. 19, 245–255 (2016)MathSciNetCrossRef
7.
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28, 277–305 (2014)MathSciNetCrossRef
8.
Bulteau, L., Hermelin, D., Labarre, A., Vialette, S.: The clever shopper problem. In: Fomin, F.V., Podolskii, V.V. (eds.) Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, Proceedings, vol. 10846 of Lecture Notes in Computer Science, pp. 53–64. Springer, Berlin (2018)CrossRef
9.
10.
Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.): 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, vol. 107 of LIPIcs Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)
11.
12.
Eisenbrand, F., Hunkenschröder, C., Klein, K.: Faster algorithms for integer programs with block structure. In: Chatzigiannakis et al. [10], pp. 49:1–49:13
13.
Gabow, H.N.: A note on degree-constrained star subgraphs of bipartite graphs. Inf. Process. Lett. 5, 165–167 (1976)MathSciNetCrossRef
14.
Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance, Theor. Comput. Sci. 38, 293–306 (1985)MathSciNetMATH
15.
Hemmecke, R., Onn, S., Romanchuk, L.: N-fold integer programming in cubic time. Math. Program. 137, 325–341 (2013)MathSciNetCrossRef
16.
Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79, 39–49 (2013)MathSciNetCrossRef
17.
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85–103, Plenum Press (1972)
18.
Knop, D., Koutecký, M., Mnich, M.: Combinatorial n-fold integer programming and applications. In: Pruhs, K., Sohler, C. (eds.) 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, vol. 87 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 54:1–54:14 (2017)
19.
Koutecký, M, Levin, A, Onn, S: A parameterized strongly polynomial algorithm for block structured integer programs, In: Chatzigiannakis et al. [10], pp. 85:1–85:14
20.
van Bevern, R., Komusiewicz, C., Niedermeier, R., Sorge, M., Walsh, T.: H-index manipulation by merging articles: models, theory, and experiments. Artif. Intell. 240, 19–35 (2016)MathSciNetCrossRef
Metadaten
Titel
The Clever Shopper Problem
verfasst von
Laurent Bulteau
Danny Hermelin
Dušan Knop
Anthony Labarre
Stéphane Vialette
Publikationsdatum
22.04.2019
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 1/2020
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-019-09917-z

Weitere Artikel der Ausgabe 1/2020

Theory of Computing Systems 1/2020 Zur Ausgabe

OriginalPaper

Slopes of Multidimensional Subshifts

OriginalPaper

Fixed-Parameter Tractable Algorithm and Polynomial Kernel for Max-Cut Above Spanning Tree

OriginalPaper

Grammar-Based Compression of Unranked Trees

OriginalPaper

Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing

EditorialNotes

CSR 2018 Special Issue on TOCS

OriginalPaper

Recognizing Read-Once Functions from Depth-Three Formulas

Premium Partner

    Bildnachweise