Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2422436.2422489 | ITCS |
Keywords | Field | DocType |
maximum value,clairvoyant algorithm,customer i,expected value,optimal algorithm,as-yet-unserved customer,time step,competitive analysis,value vi,best value,impatient user,online algorithms,bipartite matching,stochastic models | Online algorithm,Mathematical optimization,Best value,Upper and lower bounds,Computer science,Bipartite graph,Rounding,Expected value,Blossom algorithm,Competitive analysis | Conference |
Citations | PageRank | References |
1 | 0.38 | 16 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marek Cygan | 1 | 556 | 40.52 |
| Matthias Englert | 2 | 266 | 18.69 |
| Anupam Gupta | 3 | 2989 | 210.44 |
| Marcin Mucha | 4 | 275 | 18.55 |
| Piotr Sankowski | 5 | 596 | 47.95 |