Ett stort antal Internetbutiker gör det svårt för en kund att manuellt granska alla tillgängliga erbjudanden och välja optimala butiker för shopping. En partiell lösning på problemet är prisjämförelser som producerar prisrankningar från insamlade erbjudanden. Deras möjligheter är dock begränsade till en jämförelse av erbjudanden för en enda produkt som kunden begär. Frågan vi undersöker i detta papper är en multipel-punkt multi-shop optimering problem, där totala kostnader för en kund att köpa en viss uppsättning objekt bör minimeras över alla tillgängliga erbjudanden. I detta dokument, Internet Shopping Optimization Problem (ISOP) definieras på ett formellt sätt och ett bevis på sin starka NP-hårdhet tillhandahålls. Vi beskriver även polynomalgoritmer för speciella fall av problemet.
Dessutom är det bevisat att problemet inte är ungefärlig i polynom tid REF.
Internet shopping optimization problem
{'venue': 'Int. J. Appl. Math. Comput. Sci.', 'journal': 'Int. J. Appl. Math. Comput. Sci.', 'mag_field_of_study': ['Computer Science']}