Anta att något arbete måste göras under en period av ospecificerad varaktighet. Marknaden erbjuder ett urval av enheter som kan göra detta jobb, var och en kännetecknas av inköp och driftskostnader. Vilken av dem ska vi köpa vid vilka tidpunkter, för att minimera de totala kostnaderna? Som vanligt i konkurrensanalysen jämförs kostnaden för en on-line-lösning med de optimala kostnader som betalas av en tydlig köpare. Detta problem som generaliserar det grundläggande hyres-till-köp problemet har införts av Y. Azar et al. I det s.k. konvexa fallet där lägre löpande kostnader alltid medför högre priser har en strategi med konkurrensförhållande 4 + 2 2  och 6.83 föreslagits. Här tar vi hänsyn till två naturliga delfall av konvex fall i en kontinuerlig tid modell där nya enheter kan köpas när som helst. För statiska fall där alla enheter finns tillgängliga i början, ger vi en enkel 4-konkurrenskraftig deterministisk algoritm, och vi visar att 3.618 är en lägre gräns. (Detta är också den första icke-triviala nedre gränsen för konvexa fall, både för diskret och kontinuerlig tid.) Dessutom ger vi en 2.88-kompetitiv randomiserad algoritm. I det fall att alla enheter har lika priser men inte alla finns tillgängliga i början, visar vi att en mycket enkel algoritm är 2-konkurrenskraftig, och vi härleder en 1.618 lägre gräns.
I REF gav de en 4-kompetitiv deterministisk algoritm och en 3.618 lägre gräns, tillsammans med en 2.88-kompetitiv randomiserad algoritm.
Nearly optimal strategies for special cases of on-line capital investment
{'venue': 'Theoretical Computer Science', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}