Ola Svensson gave two talks about hardness of approximation for job shop and (unique games dependent) hardness of precedence-constrained scheduling on parallel machines. The reductions were simple and we had a black-board talk, so that we were able to follow (almost) everything. What a great pleasure! I love slow talks. Otherwise I cannot listen to 5 hours of talks a day. I showed off how to use a tablet - borrowing someone else's tablet and writing notes for the talk, that will be uploaded to the Dagstuhl website shortly, so that everyone can use them as if they were the slides for the talk.
Niv Buchbinder gave a linear-programming approach to the secretary problem and variants. Let pi be the probability that the ith arrival is hired, qi be the probability that he is hired given that he is the best of all, fi be the probability that he is hired given that he is best aong the first i. Since the problem is online, qi=fi. We can write a few constraints that must be satisfied, then a feasible solution suggests an algorithm, and exhibiting a matching dual feasible solution proves optimality. Simple and classic LP approach to online problems, that nicely unifies several s of the secretary problem. Elegant. Open: take that approach for the knapsack variant.
Before talking about the underlying LP, Niv started by showing an algorithm, then had to fight a rebellion from the room: he wanted to move on to the analysis, but instead was attacked by rapid-fire questions, all of which he answered with: "Wait, it'll come in a couple of slides!" - a good teaser talk. Fun!
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.