[Lowerbounds, Upperbounds]

It’s All Text! is one of my most-used Firefox add-ons and recently it’s been upgraded to run on 3.0b4.

Edit textareas using an external editor, because it’s all text!

Right click on a textarea, select “It’s All Text!” and edit the text in the editor of your choice.

Alternatively, click on the edit buttons added for your convenience. Right click on the edit buttons for even more options, including preferences.

There are good reasons why you want to use your own favorite text editor to do text editing, and this add-on makes the process extremely easy (no cut and paste needed). But my initial reason was to avoid the “back” button: on my ThinkPad, it’s right next to the arrow keys and if you happen to hit it by mistake, whoosh, all your text is gone…

Highly recommended.

P.S. Of course this post and many others are written using it.

Title:Intersection Cuts in 2 Dimensions
Speaker: Francois Margot, CMU
When: March 27, 12:30-13:30
Where: Porter Hall 125B

Abstract:

When solving Mixed Integer Linear Programs (MILP) with branch-and-cut algorithms a variety of cuts can be generated. The best known cuts are probably Gomory mixed integer cuts, obtained from a single row of the optimal simplex tableau for the linear relaxation of the MILP. Recently, results on generating cuts using information from two rows of the tableau have appeared. In particular, Andersen, Louveaux, Wolsey and Weismantel (2007) investigate the facets of a particular relaxation of the MILP to a problem with two integer variables and two constraints. They show that all facets are then split inequalities or intersection cuts obtained from triangles or quadrilaterals. We give the converse, determining which of these splits, triangles and quadrilaterals actually give facets. We also give the corresponding characterization for an infinite-dimensional relaxation of the relaxation of Andersen et al., similarly to the relaxation used by Gomory and Johnson in their study of the group problem. Joint work with Gerard Cornuejols.

Via Punk Rock OR, I wish you will 133.1% agree with this post.

When: 2008-03-25 12:00
Where: NSH 1507
Speaker: Aaron Roth
Title: The Price of Malice in Linear Congestion Games
Abstract:

The price of anarchy has proven to be a useful measure for quantifying the degradation of performance in a system that is populated by selfish agents. However, it is a brittle measure, because it assumes that all users of the system are perfectly rational and adeptly seek to minimize their own cost. In actual networks, this is not always the case! Users may be oblivious to congestion, may be unable to calculate optimal routes, or may be explicitly malicious (consider, for example, denial of service attacks and worms). In this talk, we study the price of malice in traffic routing games, in which users must choose paths on a network to route their flow, and incur traffic dependent latency costs. We quantify by how much Byzantine (possibly malicious) users can degrade social cost. We provide bounds on two measures of the price of malice that have been proposed in the literature, by bounding the price of total anarchy. Bounding the price of malice using the price of total anarchy has the advantage that our bounds on social cost can be plausibly achieved by computationally efficient, decentralized agents who may only be aware of their own costs.

Where: 1507 NSH
When: 2008-03-19 Noon
Speaker: Abe Othman
Title: Beyond the Revelation Principle: Manipulation-Optimal Mechanisms
Abstract:

Rational, self-interested agents will lie to a mechanism if it benefits them. Despite this, the revelation principle states that any outcome a mechanism implements can also be implemented by a mechanism where agents are motivated to tell the truth. In this paper, we introduce the concept of manipulation-optimal mechanisms: non-truthful mechanisms that always do as well as the best truthful mechanism, and strictly better if any agent fails to find/play its best manipulation (lie).

Though the existence of such a mechanism has been shown previously in an artificial context, we study how broadly the paradigm applies in general. We curtail it with an impossibility result: in a manipulation-optimal mechanism, each agent can have at most one manipulable type. For such settings, we show that manipulation-optimal mechanisms can exist if the goal is social welfare maximization, but not when agents are symmetric and the mechanism is anonymous. We also show that there exist anonymous manipulation-optimal mechanisms with the goal of affine welfare maximization, even with symmetric players.

We then explore a way around our impossibility result: natural restrictions on the agents’ strategies. We study the Generalized Second-Price auction used by Google, Yahoo!, and MSN to auction billions of dollars of search keywords annually. This mechanism has been criticized because it is manipulable. Under two common assumptions, however, we show that it is manipulation optimal. Thus, switching to a truthful mechanism could only be deleterious to profits.

Joint work with Tuomas Sandholm.

Name: R. Ravi, Tepper School of Business and Russell Schwartz, Computer Science Department
University: Carnegie Mellon University
Date: Friday, March 7, 2008
Time: 1:30 to 3:00 pm
Location: Room 151 Posner Hall

Title: Mathematical Programming Methods for Phylogeny Reconstruction from Genetic Variation Data

Abstract:

Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny inference will be required if we are to be able to continue to make effective use of the rapidly growing stores of variation data now being gathered. We present two integer linear programming (ILP) formulations to find the most parsimonious phylogenetic tree from a set of binary variation data. One method uses a flow-based formulation that can produce exponential numbers of variables and constraints in the worst case. The method has, however, proven extremely efficient in practice on datasets that are well beyond the reach of the available provably efficient methods, solving several large mtDNA and Y-chromosome instances within a few seconds and giving provably optimal results in times competitive with fast heuristics than cannot guarantee optimality. An alternative formulation establishes that the problem can be solved with a polynomial-sized ILP.

The above methods are applicable for reconstruction of maximum parsimony trees from haplotype data, but such data are difficult to determine directly for autosomal DNA. Data more commonly is available in the form of genotypes, which consist of conflated combinations of pairs of haplotypes from homologous chromosomes. Currently, there are no general algorithms for the direct reconstruction of maximum parsimony phylogenies from genotype data. Hence phylogenetic applications for autosomal data must therefore rely on other methods for first computationally inferring haplotypes from genotypes. We extend our previous methods for computing maximum parsimony phylogenies directly from genotype data. We show that the standard practice of first inferring haplotypes from genotypes and then reconstructing a phylogeny on the haplotypes often substantially overestimates phylogeny size. As an immediate application, our method can be used to determine the minimum number of mutations required to explain a given set of observed genotypes.

Joint work with Srinath Sridhar, Fumei Lam and Guy E. Blelloch.

Time: 2008-03-05 12:00
Place: NSH 1507
Speaker: Deeparnab Chakrabarty
Title: Steiner Trees - Geometry, Linear Programs and Algorithms

Abstract:

In this talk, we investigate the bidirected cut LP relaxation for the Minimum Steiner Tree problem. We use geometry to devise a new lower bound on the cost of any Steiner tree. The lower bound is captured via an LP which we call the simplex-embedding LP. A short description of it is that it is an l_1-embedding of the graph on a simplex, maximizing a certain linear objective function. Interestingly, the dual of the LP turns out to be equivalent to the bi-directed cut relaxation.

For quasi-bipartite graphs, graphs which have no Steiner-Steiner edges, we will show how we improve the upper bound on the integrality gap of our LP relaxation (and hence as well as the bidirected cut LP relaxation). In this talk, we will show an upper bound of $\sqrt{2}$ which improves upon the known 3/2. We will also indicate how this can be further improved to 4/3. In contrast, the best lower bound known is 8/7 by Martin Skutella.

This is joint work with Nikhil R. Devanur and Vijay V. Vazirani.