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.
