Seminar on Nov. 11, 2011

Date: Friday, November 11, 2011.

Place: The 6th Building, Room 105, Xueyuan Road, No. 18, Zhejiang University of Finance and Economics (Xiasha campus), Hangzhou.

11:00 am - 11:40 am

Speaker: Deshi Ye (Zhejiang University)

Title: Efficiencies of competing schedulers in cloud computing

Abstract: We consider a two-sided game in cloud computing, where both the machines and the jobs are controlled by selfish agents. The jobs attempt to minimize their completion times, while the machines try to choose their scheduling policies to maximize their own gains (the total running time). The deterministic scheduling policies that a machine might choose are usually the Shortest-First, the Longest-First, and the Makespan. Ashlagi et al. (2010) showed that there always exists a Nash equilibrium that both the jobs and the machines do not have incentive to change their strategies, if the machines are restricted to only two deterministic and consistent policies. However, the independent and selfish behaviors of these two-sided setting might result in a high socially outcome. We consider two different kinds of social objectives. The natural one is minimizing the makespan. Another one is maximizing the minimization completion time of machines, by considering the fairness. We adopt the price of anarchy as a measure for the efficiency of an equilibrium.

1:30 pm - 2:20 pm

Speaker: Mordecai J. Golin (HKUST)

Title: Revisiting the Monge Property

Abstract: We revisit the “Monge” speedup for dynamic programming and show that not only time, but in many cases also space, can be reduced by an order of magnitude. We further show that it’s often possible to maintain the speedup in an online setting (the original Monge speedup assumed static input).

Joint work with Amotz Bar-Noy, Yi Feng, Larry Larmore, and Yan Zhang

2:30 pm - 3:20 pm

Speaker: Yitong Yin (Nanjing University)

Title: Approximate Counting via Correlation Decay in Spin Systems

Abstract: We give the fist deterministic fully polynomial-tome approximation scheme (FPTAS) for computing the partition function of a two-state spin system on an arbitrary graph, when the parameters of the system satisfy the uniqueness condition on infinite regular trees. This condition is of physical significance and is believed to be the right boundary between approximable and inapproximable.

The FPTAS is based on the correlation decay technique introduced by Bandyopadhyay and Gamarnik [SODA 06] and Weitz [STOC 06]. The classic correlation decay is defined with respect to graph distance. Although this definition has natural physical meanings, it does not directly support an FPTAS for systems on arbitrary graphs, because for graphs with unbounded degrees, the local computation that provides a desirable precision by correlation decay may take super-polynomial time. We introduce a notion of computationally efficient correlation decay, in which the correlation decay is measured in a refined metric instead of graph distance. We use a potential method to analyze the amortized behavior of this correlation decay and establish a correlation decay that guarantees an inverse-polynomial precision by polynomial-time local computation. This gives us an FPTAS for spin systems on arbitrary graphs. This new notion of correlation decay properly reflects the algorithmic aspect of the spin systems, and may be used for designing FPTAS for other counting problems.

Joint work with Liang Li and Pinyan Lu

3:30pm - 4:20pm

Speaker: Bingkai Li (Shanghai Jiaotong University)

Title: The parameterized complexity of k-edge induced subgraphs

Abstract: We prove that finding a k-edge induced subgraph is fixed-parameter tractable, thereby answering an open problem of Leizhen Cai. Our algorithm is based on several combinatorial observations, Gauss' famous Eureka theorem [Andrews, 86], and a generalization of the well-known FPT-algorithm for the model-checking problem for first-order logic on graphs with locally bounded tree-width due to Frick and Grohe [Frick and Grohe, 01]. On the other hand, we show that two natural counting versions of the problem are hard. Hence, the k-edge induced subgraph problem is one of the rare known examples in parameterized complexity that are easy for decision while hard for counting.

Joint work with Yijia Chen.