[Lowerbounds, Upperbounds]

In the last month I have seen two PowerPoint talks with slides that did not fit in the projector resolution (*). Before telling you the cause of the problem, let me first tell you the solution to avoid this problem “most” of the time (the order of events is important):

1. Plug the video cable first.
2. Start feeding video signal to the projector. (On ThinkPads, use Fn-F7.)
3. Start the slide-show in PowerPoint.

The problem seems to be a combination of several factors. First, more and more laptop displays have a resolution that is higher than XGA (1024×768). Then, the speaker, for one reason or another, started the slide-show before she plugs in the video cable. At this point, the slide-show is already running at a super-XGA resolution. The rest can be attributed to a “bug” of PowerPoint’s slide-show module or a “feature” of the display driver, or whatever. Details omitted.

(*) These days, 1024×768 is standard, and my bet is that in 5 years it will still be standard due to the price of LCD projectors.

Speaker: Abie Flaxman

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Expansion and lack thereof in perturbed random graphs

Abstract:

Whenever the CMU Theory Lunch has a talk about “real-world” random graphs, someone in the audience asks if the graphs under consideration are expanders. This talk will address the question directly with respect to perturbed random graphs, which are formed by starting with an arbitrary base graph and adding a sparse random graph. The techniques used also reveal a suprising fact about the small-world graphs studied by Jon Kleinberg [Proc. of 32nd ACM STOC (2000), 163–170]: the expansion undergoes a phase transition exactly at the point where the graph is efficiently navigable by a decentralized algorithm.

Recently I have started a research project that requires quite a bit of Excel. Now if you don’t use Excel for research, maybe you still use it for keeping class grades once in a while?

The first thing I do on every Excel installation is to change it to the R1C1 style. In Excel, each cell can be referenced in two styles: A1 and R1C1. (See a bit of history here.)

The former is the default (as of Version 2003). Each cell is referenced by its column name and then row number. So the first cell is called A1.

The latter is my preferred style. Each cell is referenced by its row number and column number. So the first cell is called R1C1.

Now some people may think that “E3″ is more intuitive than “R3C5″, and I can probably agree with them when the spreadsheet is small. But when the spreadsheet gets big and spans a couple hundred columns, I cannot contemplate seeing “BK439″…

To switch to the R1C1 style, go to tools->Options->General->R1C1 Reference Style.

The two styles are equivalent in power (if you use them right), but I will show you later why R1C1 has an advantage when it comes to formula editing.

My recent harddrive crashes (four times in three months) forced me to reinstall a lot of softwares on several machines. As a side-benefit, I get to upgrade all my softwares to the the latest versions. For the most part, this is a good thing. For example, Vim is now in version 7; WinMerge has seen a lot of improvement in its user interface; and Ipe 6pre26 actually works very nicely. I have also upgraded Miranda, FreeMind, TortoiseSVN and 7-zip. I thank the authors/contributors of these softwares and many others that I do not have the time to list. I know how much effort it takes. Thank you!

But then, there are also other “developments”. The most notable one is TexPoint. I think version 2.0.3 is the one I had and is the last free version. I also notice that GSView now has a “nag screen”. But its licence suggests that no payment is required. In any case, I still want to thank the authors of these softwares. They have indeed made my life better.

FRIDAY MAY 12th, 2006 - WEAN HALL 7220 - 3:30pm

Towards model checking of biological phenomena

Christopher Langmead
Carnegie Mellon University

The emerging fields of systems and synthetic biology develop and utilize mathematical models of various phenomena. While these models are generally used to drive simulation studies, there is a growing body of literature devoted to the formal analysis of the models themselves. In this talk, I will survey some recent applications of formal methods to biological models. I will also present some preliminary results from our application of model checking to an instance of the 2D HP model of protein folding.

Date: Friday, May 19, 2006
Time: 1:30 to 3:00 pm
Place: 388 Posner Hall

Abstracts:

Sam Hoda
Tepper School of Business
Algorithms for Approximately Solving Large Linear Programs Arising from Extensive Form Games

One of the central problems in computational game theory is finding Nash equilibria of extensive form games. It is well known that a zero-sum two-player game can be expressed as a linear program. For games such as a poker, however, the resulting linear programming problems are so large that there is little hope of solving them using traditional linear programming methods even on the best hardware. For example, the Cholesky factors in CPLEX’s barrier algorithm require over 20 Gbs of memory for a very restricted version of poker.

We are working on a new first-order method that can approximate Nash equilibria for large two-person zero-sum games within arbitrary accuracy. The method is based on the excessive gap technique (EGT) proposed by Nesterov. Our algorithm combines the smoothing technique for saddle-point problems from EGT with the combinatorial tree structure of the game. This is joint work with Dr. Javier Pena (Tepper) and Andrew Gilpin (SCS).

——————————————-

Viswanath Nagarajan
Tepper School of Business
Approximating the Dial-A-Ride Problem

The dial-a-ride problem is defined as follows: there is a metric space on n vertices, a collection of l objects each with a specified source and destination, and a vehicle of capacity k. The goal is to find a minimum length tour of the vehicle that moves every object from its source to its destination, while satisfying the constraint that there are at most k objects in the vehicle at any point of time. Two main variants of this problem have been studied in the literature: in the preemptive case, the objects can be parked at intermediate locations before reaching their destinations; in the non-preemptive case, once an object is picked up it stays in the vehicle until it is dropped at its destination.

While both versions are NP-hard, the preemptive version is known to have a much better approximation ratio than the non-preemptive version. The goal of this summer paper is to obtain improved approximation guarantees for the non-preemptive dial-a-ride problem, and also consider some extensions. In this talk, I will outline the previous results, and give some initial ideas for improvement.

——————————————-

Ben Peterson
Tepper School of Business
Optimization of Reactive Power Flow in Electrical Networks

Much like the resistance of a power transmission line causes losses in electrical energy, the inductance of a line can also causes energy loss. Inductance slows the sinusoidal current wave with respect to the voltage wave, causing the current to lag behind. When the electricity arrives at its destination, the two signals do not line up and so their product V · I = P which equals the power delivered is not maximized. This effect is counteracted at the power plant by generating an electric signal whose current leads its voltage so that the two signals are synchronized at the destination. Such a power plant is said to be producing reactive power,
the term for the imaginary component of an AC electric current phasor.

Production of reactive power at a power plant requires extra energy, and this lowers the plant’s ability to generate real power. Generators vary in the amount of reactive power they can produce and the amount of real power they must forfeit to produce it. Because reactive power is such a small component of the energy distributed in the electrical network, it is generally ignored in the optimization of power flow to simplify the calculation.

For my research I would like to explore this other dimension of the optimal power flow problem. I will determine how the electrical network structure effects reactive power flows and how to optimize its dispatch. Then I will explore how to price reactive power at network nodes in order to induce profit-maximizing power suppliers to produce the required reactive power in the network at minimum cost. I hope to create a solution to the reactive power optimization problem that can be easily solved and implemented.

——————————————-
Anand Sankaran
Tepper School of Business
TBA

——————————————-

John Turner
Tepper School of Business
Scheduling of Dynamic Advertising

In the last few years, a new form of advertising has been developed. Dynamic in-game advertising uses the Internet to serve ads directly to video game consoles. In this way, billboards on the side of the road in a racing game may show an ad for Nike for one gamer, while showing an ad for Pepsi for another. The ability to dynamically rotate ads over time coupled with real-time feedback creates an advertising environment that is in some ways similar to banner ads on webpages, and in some ways different. This summer project is work in conjunction with a leading company that sells in-game advertising. It is our goal to study the novel problem
dynamics, design a model for the optimal scheduling of in-game ads over time, and to come up with heuristics that can track the optimal schedule and deliver near-optimal results in real-time. This is joint work with Alan Scheller-Wolf and Sridhar Tayur.

Speaker: Shuheng Zhou
Date: Friday, May 12
Time: 2:00-3:15pm
Place: WeH 7220

Title: Edge Disjoint Paths in Moderately Connected Graphs

Abstract:

We study the Edge Disjoint Paths (EDP) problem in undirected graphs: Given a graph $G$ with $n$ nodes and a set $\T$ of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a variety of classic NP-complete problems, for which approximability is not well understood.

We show a polylogarithmic approximation algorithm for the undirected EDP problem in general graphs with a moderate restriction on graph connectivity; we require the global minimum cut of $G$ to be $\Omega(\log^5 n)$. Previously, constant or polylogarithmic approximation algorithms were known for trees with parallel edges, expanders, grids and grid-like graphs, and most recently, even-degree planar graphs. These graphs either have special structure (e.g., they exclude minors) or there are large numbers of short disjoint paths. Our algorithm extends previous techniques in that it applies to graphs with high diameters and asymptotically large minors.

This is joint work with Satish Rao.

Speaker: Katrina Ligett

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Truthful, Near-Optimal Mechanism Design

Abstract:

In many situations, such as auctions, one would like to compute a function on inputs held by selfish players. The players may lie to try to influence the outcome of the algorithm in their favor. Mechanism design seeks to design a pricing scheme and algorithm that incentivize truth-telling. While there exist truthful mechanisms for a wide range of settings, the underlying problem is often NP-hard, and naive attempts at applying approximation algorithms may destroy the truthfulness of a mechanism. We will discuss a general technique, presented by Lavi and Swami in FOCS 2005, for converting approximation algorithms into truthful mechanisms.

Speaker: Kirk Pruhs, University of Pittsburgh

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Cake cutting is and is not a piece of cake

Abstract:

The setting for the classic cake cutting problem is a collection of self-interested entities who desire to partition a disparate collection of items of value. Imagine heirs of an estate wanting to divide the possessions of the newly departed. Or imagine the creditors of a bankrupt company, such as Enron, wanting to split up the company’s remaining assets. The entities may well value the items differently. For example, one can imagine different heirs of an estate not necessarily agreeing on the relative value a baseball signed by Pete Rose, a worn leather lazy boy recliner, a mint condition classic Farrah Fawcett poster, etc. The goal is devise a protocol to split up the items fairly, that is, so every entity believes that he/she gets a fair share based on how he/she values the objects. Achieving this goal is potentially complicated by the fact that the entities may well be greedy, deceitful, treacherous, etc. They may not be honest about how they value the objects, they may collude together to cheat another entity, etc.

The cake cutting problem dates from the 1940’s school of Polish mathematics. This problem is frequently discussed in algorithms and discrete mathematics courses, for example CMU 15-451.

In 1948 Steinhaus gave a deterministic protocol with query complexity Theta(n^2). In 1984, Evan and Paz gave a deterministic divide and conquer protocol with query complexity Theta(n log n). We show that every deterministic protocol for this problem has query complexity Omega(n log n). This lower bound also applies even if the deterministic protocol need only be approximately fair. We then show that there is a randomized algorithm that is approximately fair and has query complexity O(n).

This is joint work with Jeff Edmonds.

As I’m sure you all have noticed, we’ve been having either Bagel Factory sandwiches or Napoli pizza at every theory lunch this semester. As one of the co-organizers, ordering the same thing every week makes my life easier, but even I’m getting a little sick of it. So if anyone has any suggestions for food, please let me know, either by e-mail or in the comments. The only constraint is that, including delivery and tip, it can’t cost more than 200 dollars and has to feed about 30-35 people (we like to err on the side of having extra food rather than running out). We also like to have some veggie stuff for you vegetarians and some meat stuff for the rest of us. We’ve been ordering from Wheel Deliver since they’re used to dealing with the University and it’s nice to have a centralized place to order everything, so ideally we’d keep using them, but I’m open to other suggestions too. So please, give me some ideas, since otherwise we’ll probably just keep alternating between sandwiches and pizza. I’d even be interested in whether you like the sandwiches or the pizza more. I know that I prefer the pizza, but apparently a fair number of people disagree with me.

See you all at lunch on Wednesday!