TY - GEN

T1 - Catch them if you can

T2 - 2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013

AU - Cygan, Marek

AU - Englert, Matthias

AU - Gupta, Anupam

AU - Mucha, Marcin

AU - Sankowski, Piotr

PY - 2013

Y1 - 2013

N2 - Consider the following problem of serving impatient users: we are given a set of customers we would like to serve. We can serve at most one customer in each time step (getting value vi for serving customer i). At the end of each time step, each as-yet-unserved customer i leaves the system independently with probability qi, never to return. What strategy should we use to serve customers to maximize the expected value collected? The standard model of competitive analysis can be applied to this problem: picking the customer with maximum value gives us half the value obtained by the optimal algorithm, and using a vertex weighted online matching algorithm gives us 1-1/e ≈ 0.632 fraction of the optimum. As is usual in competitive analysis, these approximations compare to the best value achievable by an clairvoyant adversary that knows all the coin tosses of the customers. Can we do better? We show an upper bound of ≈0.648 if we compare our performance to such an clairvoyant algorithm, suggesting we cannot improve our performance substantially. However, these are pessimistic comparisons to a much stronger adversary: what if we compare ourselves to the optimal strategy for this problem, which does not have an unfair advantage? In this case, we can do much better: in particular, we give an algorithm whose expected value is at least 0.7 of that achievable by the optimal algorithm. This improvement is achieved via a novel rounding algorithm, and a non-local analysis.

AB - Consider the following problem of serving impatient users: we are given a set of customers we would like to serve. We can serve at most one customer in each time step (getting value vi for serving customer i). At the end of each time step, each as-yet-unserved customer i leaves the system independently with probability qi, never to return. What strategy should we use to serve customers to maximize the expected value collected? The standard model of competitive analysis can be applied to this problem: picking the customer with maximum value gives us half the value obtained by the optimal algorithm, and using a vertex weighted online matching algorithm gives us 1-1/e ≈ 0.632 fraction of the optimum. As is usual in competitive analysis, these approximations compare to the best value achievable by an clairvoyant adversary that knows all the coin tosses of the customers. Can we do better? We show an upper bound of ≈0.648 if we compare our performance to such an clairvoyant algorithm, suggesting we cannot improve our performance substantially. However, these are pessimistic comparisons to a much stronger adversary: what if we compare ourselves to the optimal strategy for this problem, which does not have an unfair advantage? In this case, we can do much better: in particular, we give an algorithm whose expected value is at least 0.7 of that achievable by the optimal algorithm. This improvement is achieved via a novel rounding algorithm, and a non-local analysis.

KW - bipartite matching

KW - impatience

KW - online algorithms

KW - stochastic models

UR - http://www.scopus.com/inward/record.url?scp=84873393341&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873393341&partnerID=8YFLogxK

U2 - 10.1145/2422436.2422489

DO - 10.1145/2422436.2422489

M3 - Conference contribution

AN - SCOPUS:84873393341

SN - 9781450318594

T3 - ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science

SP - 485

EP - 493

BT - ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science

Y2 - 9 January 2013 through 12 January 2013

ER -