Seminar on February 22, 2011

Date: February 22, 2011

Venue: Room 402, State Key Lab of CAD&CG, Zi-Jin-Gang Campus, Zhejiang University, Hangzhou

Schedule of talks:


Speaker: Pinyan Lu (MSRA)

Title: Budget feasible mechanisms

Abstract: Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mechanism design problems to a realistic setting with a budget constraint. We consider the problem of designing truthful budget feasible mechanisms for general submodular functions: we give a randomized mechanism with approximation ratio 7.91 (improving the previous best-known result 112), and a deterministic mechanism with approximation ratio 8.34.

Further we study the knapsack problem, which is special submodular function, give a 2+\sqrt{2} approximation deterministic mechanism (improving the previous best-known result 6), and a 3 approximation randomized mechanism. We provide a similar result for an extended knapsack problem with heterogeneous items, where items are divided into groups and one can pick at most one item from each group.

Finally we show a lower bound of approximation ratio of $1+\sqrt{2}$ for deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general submodular functions. Our lower bounds are unconditional, which do not rely on any computational or complexity assumptions.

Joint work with Ning Chen and Nick Gravin.

12:20-13:30 Lunch


Speaker: Rudolf Fleischer (Fudan University)

Title: FPT algorithms and bioinformatics

Abstract: Solving NP-hard problems usually requires a running time exponential in the input size. The theory of FPT (fixed parameter tractable) algorithms tries by ways of a refined runtime analysis to identify special cases which can be solved in polynomial time. The trick is to identify some structural parameter in the problem instances that really causes the exponential running time if this parameter is a small constant in the applications we want to solve, we can solve the problem in polynomial time.

For example, we can computer a vertex cover of an undirected graph in time exponential in the size of the vertex cover but linear in the input size. In this talk, I will give a short introduction into the theory of FPT algorithms and then study in more details a computational problem in bioinformatics. Haplotyping is the problem of finding a small set of haplotypes that can explain a given set of genotypes. I will present some new FPT algorithms for this problem (with haplotype set size as parameter) that are exponentially faster than previous algorithms.


Speaker: Wei Yu (Zhejiang University)

Title: Improved approximation algorithms for routing shop scheduling

Abstract: We investigate a generalization of open shop and flow shop scheduling problems where n jobs are located at the vertices of a graph and m machines must travel between the vertices to process the jobs. The goal is to minimize the makespan. We develop improved approximation algorithms for the open shop and flow shop problems on a general graph. More precisely, we present an O(\log m\log\log m)-approximation algorithm for RO||C_{max}, improving the previous upper bound of O(\sqrt m). For RF||C_{\max} we reduce the bound from (m+1)/2 to O(m^{2/3}).

Joint work with Guochuan Zhang


Speaker: Guochuan Zhang (Zhejiang University)

Title: Parallel machine scheduling with speed-up resources

Abstract: We study the problem of parallel identical machine scheduling with a set of different renewable speed-up resources, and the aim is to minimize the makespan. The processing time of a job is resource dependent, i.e., it depends on which resource the job uses. Moreover, if one resource is currently used by a job, then it is not available for others until this job is completed. The problem is a natural generalization of the classical unrelated machine scheduling problem. We present a 2-approximation algorithm through an LP rounding. We also deal two special cases in which either the number of machines or the number of resources is a constant. (5/3+\epsilon)-approximation algorithms are presented.

Joint work with Lin Chen and Deshi Ye