Abstrakt. Vi anser att problemet med pris poster för att maximera vinsten från att sälja dessa objekt. Ett exempel ges av en uppsättning E av n poster och en uppsättning m kunder, där varje kund anges av en delmängd av E (den bunt av objekt hon / han vill köpa), och en budget (värdering), som är det högsta priset hon / han är villig att betala för den delmängd. Vi begränsar vår uppmärksamhet till modellen där undergrupperna kan ordnas så att de bildar intervaller av en linje graf. Om man antar en obegränsad leverans av något objekt, detta problem är känd som motorvägen problem och hittills bara en O (log n)-tillnärmning algoritm är känd. Vi visar att ett PTAS sannolikt kommer att existera genom att lägga fram ett kvasipolynomiskt tidsberäkningssystem. Vi kombinerar också våra idéer med ett nyligen utvecklat kvasi-PTAS för det osplitterbara flödesproblemet på linjediagram för att utvidga detta approximationssystem till den begränsade utbudsversionen av prisproblemet.
Slutligen, Elbassioni et al. I REF presenteras ett system för att approximera tiden i princip för både den kapacierade och den icke-kondenserade versionen av problemet, vilket tyder på att det sannolikt kommer att finnas ett PTAS.
A quasi-PTAS for profit-maximizing pricing on line graphs
{'venue': 'In Proc. 15th Ann. European Symp. on Algorithms (ESA’07), Lecture Notes in Computer Science', 'journal': None, 'mag_field_of_study': ['Computer Science']}