Seminář z aproximačních a online algoritmů

Petr Kolman, Jiří Sgall

Doba a místo konání

UMLUVENO: v LS 2015 se koná v pondělí od 10:40 v S8

Oznámení o seminářích se distribuuje pomocí mailing listu, do kterého se můžete zapsat na adrese http://list.math.cas.cz/listinfo/algo-seminar.

Kontakt

http://kam.mff.cuni.cz/~kolman/, tel. 951 554 155;
http://iuuk.mff.cuni.cz/~sgall/, tel. 951 554 293.

Nejbližší program semináře [Next program]

27. 4. 2015 (Pondělí [Monday], 10:40, MFF UK Malá Strana S8)

(joint work with Hossein Esfandiari, MohammadTaghi Hajiaghayi, and Vahid Liaghat)

Abstract: Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of 0.5. On the other hand, for the basic secretary problem, the optimal strategy is to ignore the first n/e elements of the sequence while using the maximum of the first n/e elements as the threshold for the rest of sequence. This strategy achieves the optimal competitive ratio of 1/e=0.36.

In this paper, we introduce prophet secretary, a natural combination of the prophet inequality problem and the secretary problem. An example of motivations for our problem is as follows. Consider a seller that has an item to sell on the market to a set of arriving customers. The seller knows the types of customers that may be interested in the item and he has a price distribution for each type: the price offered by a customer of a type is anticipated to be drawn from the corresponding distribution. However, the customers arrive in a random order. Upon the arrival of a customer, the seller makes an irrevocable decision to whether sell the item at the offered price. We address thequestion of finding a strategy for selling the item at a high price.

We show that by using a single uniform threshold one cannot break the 0.5 barrier of the prophet inequality for the prophet secretary problem. However, we show that

• using n distinct non-adaptive thresholds one can indeed obtain the competitive ratio of (1-1/e \approx 0.63); and
• no online algorithm can achieve a competitive ratio better than 0.73.

Our results improve the approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to (1-1/e) when the order of agents (customers) are chosen randomly.

We also consider the minimization variants of the prophet inequality problem. In particular, we show that, even for the simple case in which numbers are drawn from identical and independent distributions (i.i.d.),  there is no constant competitive online algorithm for the minimization variants of the prophet inequality and prophet secretary problems.

Předběžný další program [Preliminary future program]

Nikhil Bansal: Approximating independent sets in sparse graphs. SODA 2015.
(referuje Martin Böhm)

Další články pro ZS 2014 [More papers proposed for this semester]

Anupam Gupta and Amit Kumar: Greedy Algorithms for Steiner Forest. STOC 2015. Also http://arxiv.org/abs/1412.7693.

Chidambaram Annamalai, Christos Kalaitzis and Ola Svensson: Combinatorial Algorithm for Restricted Max-Min Fair Allocation. SODA 2015. Also http://arxiv.org/abs/1409.0607.

Guru Guruganesh, Laura Sanita, Chaitanya Swamy: Region-Growing and Combinatorial Algorithms for k-Route Cut Problems. (k dispozici mailem)

Deeparnab Chakrabarty, Sanjeev Khanna and Shi Li: On Restricted Assignment Makespan Minimization. SODA 2015. Also http://arxiv.org/abs/1410.7506.Anupam Gupta and Amit Kumar: Greedy Algorithms for Steiner Forest. STOC 2015. Also http://arxiv.org/abs/1412.7693.

Gábor Braun, Sebastian Pokutta, Daniel Zink: Inapproximability of combinatorial problems via small LPs and SDPs. STOC 2015.

Samozřejmě, jako vždy, jsou vítany jsou i další náměty, zejména pak prezentace vlastních výsledků účastníků semináře.

Další články, o kterých jsme uvažovali, zbylé z minulého semestru atd. [Additional proposed papers, leftovers from the last semester]

Lorenzo Orecchia, Zeyuan Allen Zhu: Flow-Based Algorithms for Local Graph Clustering. SODA 2014. Also http://arxiv.org/abs/1307.2855.
(referuje Martin Koutecký?)

Marcin Mucha and Maxim Sviridenko: No-Wait Flowshop Scheduling is as Hard as Asymmetric Traveling Salesman Problem. ICALP 2013. Also http://arxiv.org/abs/1302.2551.

Martin Aumuller and Martin Dietzfelbinger:  Optimal Partitioning for Dual Pivot Quicksort. ICALP 2013. Also http://arxiv.org/abs/1303.5217 and slides.

Susanne Albers, Matthias Hellwig: Semi-online scheduling revisited. Theor. Comput. Sci. 443: 1-9 (2012).

Chandra Chekuri, Alina Ene: Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion. SODA 2013.

Hyung-Chan An, Robert Kleinberg, David B. Shmoys: Improving Chrisofides' Algorithm for the s-t Path TSP. STOC 2012.

Subash Khot: On the Unique Games Conjecture. In Proc. 25th Complexity (CCC), 99-121, 2010.

Luca Trevisan: On Khot's unique games conjecture. Bull. Amer. Math. Soc. 49 (2012), 91-111.