theoryseminar2001

Theory Seminar: Schedule for Spring 2001

Claire Kenyon
Date: January 12, 2001.
Time: 12:00-1:00pm.
Room: CoC 354

Better Approximation Algorithms for Bin Covering

Bin covering takes as input a list of items with size in (0,1) and places them in bins of unit demand so as to maximize the number of bins whose demand is satisfied. This is in a sense a dual problem to the classical one-dimensional bin packing problem, but has for many years lagged behind the latter in terms of the best approximation algorithms. We design algorithms for the problem that close the gap both in terms of worst case and average case results. This talk will be about the first asymptotic approximation scheme for the offline version. Joint work with Janos Csirik and David Johnson.

Jeremy Barbay
Date: January 19, 2001.
Time: 11:30-12:30pm.
Room: CoC 354

On the Discrete Bak-Sneppen Model of Self-organized Criticality

Joint work with Claire Kenyon.

Dick Lipton
Date: February 2, 2001.
Time: 11:30-12:30pm.
Room: CoC 354

DNA Computing I

Dick Lipton
Date: February 9, 2001.
Time: 11:30-12:30pm.
Room: CoC 165

DNA Computing II

No Seminar

Kamal Jain
Date: February 23, 2001.
Time: 4:00-5:00pm.
Room: Skiles 255

Theory Seminar: Schedule for Fall 2001

Howard Karloff, AT&T Labs
Date: September 7, 2001.
Time: 10:00-11:00am.
Room: CoC 52

Approximating Directed Multicuts

Given an arc-weighted directed graph G, and a set of ordered pairs (s1,t1),...,(sk,tk) of vertices, a *multicut* is a collection of arcs the deletion of which leaves no si->ti path for any i. DIRECTED MULTICUT is the problem of finding a multicut of minimum total weight. No nontrivial approximation algorithms were known for DIRECTED MULTICUT (unlike the corresponding problem on undirected graphs, which is easy). I will present the first nontrivial approximation algorithm for DIRECTED MULTICUT; it produces a multicut of cost O(sqrt (n log k)) times the optimal cost, n being the number of vertices. In fact, I will also prove (under weak hypotheses) that one can bound the cost of a multicut above by a function of the maximum multiflow in the same network, independently of k and n. This is joint work with Joseph Cheriyan and Yuval Rabani.

Howard Karloff, AT&T Labs
Date: September 7, 2001.
Time: 3:00-4:00pm.
Room: CoC 101

What I Learned About Auctions Last Fall

Last fall AT&T Labs participated in a project to help AT&T decide how to bid in the then-upcoming FCC spectrum auction, on which, in the end, AT&T spent approximately $2.9 billion. I will present some of the interesting and humorous facts and anecdotes I learned about real auctions, and why auction theory sometimes is, and sometimes isn't, applicable in the real world. This talk is definitely not intended for experts in auction theory.

Brady Hunsaker, IsYE
Date: September 21, 2001.
Time: 3:00-4:00pm.
Room: CoC 101

Fractional Matching Polytopes

The matching problem is polynomially solvable, as proven by Edmonds' blossom algorithm. The usual linear programming formulation consists of degree requirements (one for each node) and odd-set constraints, which are exponential in number. Removing the odd-set constraints yields the Fractional Matching Polytope, which is also polynomially solvable (it only has a polynomial number of constraints). Its solutions are all 1/2-integral, consisting of matched pairs and odd cycles of 1/2-edges. In this talk we consider intermediate problems, in which some subset of the odd-set constraints are imposed. In between the two nice extremes, things can get messy. Some problems are NP-complete, while most can have optimal solutions with arbitrary fractions. On the other hand, an adaptation of the blossom algorithm works for one case, and there is a large class of problems that are in P.

Dana Randall
Date: October 5, 2001.
Time: 3:00-4:00pm.
Room: CoC 101

Simulated Tempering: Fast or Slow?

Simulated tempering is a sampling method used by practitioners to overcome obstacles that make various simple Markov chains converge slowly. Like simulated annealing, tempering algorithms add a temperature parameter which changes during runtime. The hope is that using this more complicated chain we can sample at low temperature, the distribution of interest, by capitalizing on the rapid convergence at high temperature. Madras and Zheng recently showed that tempering is rapidly mixing on the mean-field Ising model at any temperature. We generalize their results to asymmetric models, including the mean-field Ising model with an external field and the Potts model. First, we show that a new variant of tempering is also rapidly mixing on these models. Second, and more significantly, we demonstrate that the convergence rate of the traditional tempering algorithm can be exponentially slow on both of these models. (Joint work with Claire Kenyon.)

Nikhil Devanur
Date: October 12, 2001.
Time: 3:00-4:00pm.
Room: CoC 101

Prisoner's Dilemma

Individuals have a knack for falling into the trap of their own rational thinking. One of the most frequently discussed problems when referring to rationality of individual behaviors is the Prisoners Dilemma. This game takes its name from an allegory used to depict its configuration. Two suspects are taken into custody. The district attorney is convinced that they are guilty of a particular felony but does not have enough proof to convince a jury. Therefore, he separates the suspects and tells each one that he has two choices: either to confess (D) or not to confess (C) the crime. The suspects are told that if both confess neither will receive special regard and will therefore receive a jail sentence of five years. If none of them confesses both will probably be convicted to some minor charge and will have to spend one year in jail. Yet if one confesses and the other does not, the suspect who confesses will be set free for cooperation with the state while the suspect that does not confess will receive a ten-years sentence. Since the one-shot version of the Prisoner's Dilemma is not very interesting (the most rational choice is to defect), the game is repeated an unknown number of times. The game is said iterated. The final score of a payer is the sum of score across all rounds. Since no player knows when the game will be ended, it is possible to study each agent's strategy, to look, for instance, how each player tries to cooperate in the game. In this talk I will address this classical problem and discuss strategies for the prisoners.

W. Fernandez de la Vega, Universite de Paris Sud
Date: October 16, 2001.
Time: 2:00-3:00pm.
Room: CoC 101

Polynomial Time Approximation Schemes for Dense Instances of MIN-2 SAT and other Minimum Constraint Problems

Kamal Jain, Microsoft Research.
Date: Nov 5, 2001.
Time: 4:30-5:30pm.
Room: CoC 342.

Equitable, Group Strategyproof Cost Allocations via Primal-Dual-Type Algorithms

We build on the well-studied egalitarian cost-sharing method of Dutta and Ray [1987] as follows. Using a primal-dual-type algorithm, we show how to construct a class of cost-sharing methods for a submodular cost function, parametrized by $n$ functions, one for each user. All methods in our class are cross-monotone and therefore lead to group strategyproof mechanisms. Our class contains cost-sharing methods satisfying a wide range of fairness criteria, hence the name ``equitable''. For instance, if the $n$ functions are identical, we get the egalitarian method, which attempts to equalize the amounts charged from the users. If they are probability distributions from which users pick their utilities, we get a method that attempts to equalize the probabilities of users getting sevice. (This is a joint work with Vijay Vazirani.)

Amin Saberi
Date: Nov 16, 2001.
Time: 3-4pm.
Room: CoC 101.

Facility Location

Parikshit Gopalan
Date: Nov 30, 2001.
Time: 3-4pm.
Room: CoC 101.

Adversaries, Codes and Information.

In this talk we describe simple techniques called Code Scrambling that allow us to relate the average performance of a code to the worst-case performance of its scrambled version C'. The performance of a scrambled code against any adversary (even a computationally unbounded one), equals the performance of the unscrambled code against a symmetric channel. A symmetric channel is a Markov chain that makes random changes to random positions. Scrambled versions of some codes can correct errors beyond the classical error correction distance with negligible probability of failure. We will show that Scrambled Reed Solomon codes of low rate can correct nearly twice the number of errors that conventional Reed Solomon codes can. We discuss other codes whose performance is likely to improve with scrambling. We discuss some open questions that this work raises. Joint work with Richard J. Lipton and Yan Zong Ding.