The clever shopper problem. (English) Zbl 1434.68192
Summary: We investigate a variant of the so-called Internet Shopping problem introduced by
J. Błażewicz et al. [Int. J. Appl. Math. Comput. Sci. 20, No. 2, 385–390 (2010; Zbl 1230.90207)],
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.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 68W05 | Nonnumerical algorithms |
| 68W25 | Approximation algorithms |
| 90C27 | Combinatorial optimization |
Citations:
Zbl 1230.90207References:
| [1] | Altmanová, Kateřina; Knop, Dušan; Koutecký, Martin, Evaluating and Tuning n-fold Integer Programming, Journal of Experimental Algorithmics, 24, 1, 1-22 (2019) · Zbl 1496.90036 · doi:10.1145/3330137 |
| [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) · Zbl 0556.68011 · doi:10.1016/0196-6774(84)90004-X |
| [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, My; Musial, J.; Urbanski, Ap; Wojciechowski, A., Internet shopping optimization problem, Appl. Math. Comput. Sci., 20, 385-390 (2010) · Zbl 1230.90207 |
| [5] | Blazewicz, J.; Bouvry, P.; Kovalyov, My; Musial, J., Internet shopping with price sensitive discounts, 4OR, 12, 35-48 (2014) · Zbl 1297.90183 · doi:10.1007/s10288-013-0230-7 |
| [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) · Zbl 1347.90033 · doi:10.1007/s10951-014-0390-0 |
| [7] | Bodlaender, Hl; Jansen, Bmp; Kratsch, S., Kernelization lower bounds by cross-composition, SIAM J. Discrete Math., 28, 277-305 (2014) · Zbl 1295.05222 · doi:10.1137/120880240 |
| [8] | Bulteau, Laurent; Hermelin, Danny; Labarre, Anthony; Vialette, Stéphane, The Clever Shopper Problem, Computer Science - Theory and Applications, 53-64 (2018), Cham: Springer International Publishing, Cham · Zbl 1434.68193 |
| [9] | Cesati, M., Perfect code is W[1]-complete, Inf. Process. Lett., 81, 163-168 (2002) · Zbl 1032.68085 · doi:10.1016/S0020-0190(01)00207-1 |
| [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) · Zbl 1392.68012 |
| [11] | Edmonds, Jack, Paths, Trees, and Flowers, Canadian Journal of Mathematics, 17, 449-467 (1965) · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4 |
| [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 · Zbl 1503.90075 |
| [13] | Gabow, Hn, A note on degree-constrained star subgraphs of bipartite graphs, Inf. Process. Lett., 5, 165-167 (1976) · Zbl 0346.68023 · doi:10.1016/0020-0190(76)90012-0 |
| [14] | Gonzalez, Tf, Clustering to minimize the maximum intercluster distance, Theor, Comput. Sci., 38, 293-306 (1985) · Zbl 0567.62048 |
| [15] | Hemmecke, R.; Onn, S.; Romanchuk, L., N-fold integer programming in cubic time, Math. Program., 137, 325-341 (2013) · Zbl 1262.90104 · doi:10.1007/s10107-011-0490-y |
| [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) · Zbl 1261.68065 · doi:10.1016/j.jcss.2012.04.004 |
| [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) · Zbl 1467.68065 |
| [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) · Zbl 1442.90129 |
| [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 · Zbl 1499.68153 |
| [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) · Zbl 1386.68076 · doi:10.1016/j.artint.2016.08.001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
