Friday, September 30, 2005
1:30 pm Posner Hall 151

Zhaosong Lhu
Dept. of Mathematical Sciences, CMU

Large-Scale Semidefinite Programming via a Saddle Point Mirror-Prox Algorithm

We first demonstrate that positive semidefiniteness of a large well-structured sparse symmetric matrix can be represented via positive semidefiniteness of a bunch of smaller matrices linked, in a linear fashion, to the matrix. We derive also the “dual counterpart” of the outlined representation, which expresses the possibility of positive semidefinite completion of a well-structured partially defined symmetric matrix in terms of positive semidefiniteness of a specific bunch of fully defined submatrices of the matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex-concave saddle point problems, which can be solved by a Prox-method developed by Nemirovski (2004) with efficiency $O(\epsilon^{-1})$. Implementations and some numerical results for large-scale Lovasz capacity and MAXCUT problems are finally presented.

FRIDAY, September 30, 2005

Probability in Science and Industry Seminar

4:30 P.M., WeH 7500
Marty Reiman
Bell Laboratories, Math Sciences Research Center.

Refreshments at 4:00 in the Math Lounge, WeH 6220.

TITLE:

An Asymptotically-Optimal Dynamic Admission Policy for a Revenue Management Problem

ABSTRACT:

We consider the following canonical revenue management problem, which has been analyzed in the context of airline seat inventory control and has applications to other service industries and supply chain management. There are several resource types (legs), each of which has a fixed capacity (number of seats). There are several customer classes (routes), each with an associated arrival process, price and resource consumption vector. The aim is to make dynamic accept/reject decisions at customer arrival epochs to maximize the total expected revenue obtained over the finite horizon [0,T] subject to not exceeding the capacity of any of the resources.

Motivated by the analysis of so-called fluid and diffusion limits (obtained as resource capacities and arrival rates grow large) of the system, we introduce a certain control policy that involves solving a couple of simple linear programs. We then show that this policy is asymptotically optimal on the so-called diffusion scale, a property that is not shared by other approaches such as booking limits and bid price control.

BIO: Dr. Martin I. Reiman is a distinguished member of technical staff in the Mathematical Sciences Research Center of Bell Labs, Lucent Technologies in Murray Hill, NJ. He has been at Bell Labs since receiving his PhD in operations research from Stanford University in 1977. Dr. Reiman’s research has focused on the analysis, optimization and control of stochastic service (queueing) systems, with an emphasis on fluid and diffusion limits. This work has been motivated by problems in communication, computing and manufacturing systems. He is the vice-chair/chair-elect of the Applied Probability Society of INFORMS and has been an associate editor of the Annals of Applied Probability as well as area editor of Mathematics of Operations Research.

I have a Slashdot backlog… I am still on May 22. So it wasn’t until this noon that I learned about the passing away of George Dantzig, the inventor of the Simplex method for solving LPs. Salute.

This reminds of a discussion I had with one of our faculty candidates last semester. Vladlen Koltun gave a fabulous job talk here and the first half of it was devoted to his work on strongly polynomial time linear programming. His magic weapon seems to be arrangement polytopes. The key idea is that linear programming on any polytope can be reduced, in polynomial time of course, to linear programming on an arrangement polytope with provably polynomial diameter. My notes say the diameter is $n * d$, where $d$ is the number of variables (dimension) and $n$ is the number of half-spaces (”faces”).

The diameter of any given polytope is important for Simplex, which navigates on extreme points. This is one major reason why the Hirsch conjecture attracts a lot of attention. The conjecture states that the diameter of any polytope is bounded by $n - d$. (I know how to check that on a “hypercube” for $d$ being 2 and 3. ) The fear is that there may exist a “worst-case” polytope with super-polynomial diameter that will ruin Simplex.

But using this reduction idea as told by Koltun, the diameter may no longer be an obstacle and instead we may choose to focus our energy on navigating on an arrangement polytope. At this point let me end the summary by noting that he showed, together with Umesh Vazirani, that linear programming is still not easy even when reduced to arrangement polytopes. I don’t know if they have any newer developments since then.

Back to our discussion after his talk. Several years ago I hit upon a result which I have dug up back when I was studying the subject of smoothed analysis:

Carl W. Lee, Regular Triangulations of Convex Polytopes, DIMACS Technical Report 90-16, 1990.

In this paper, Lee showed that every $d$-dimensional polytope can “patched” into a $(d+1)$ dimensional polytope in which the original polytope is a facet of the new polytope and the new polytope has $2(n-d)$ diameter. It’s not quite Hirsch, but a linear diameter seems too good already.

Lee’s construction is pretty simple: add a new dimension and add a new point at coordinate $(0, \ldots,0,1)$, i.e., it is the only point that is not lying on the 0-plane of the new dimension. So you first get a pyramid. The degeneracy at the apex is handled by a careful but simple perturbation. More precisely, starting with the linear program:

$\max c \cdot x$
$a_i \cdot x \leq b_i, 1 \leq i \leq n$

We transform it into

$\max c \cdot x + 0x_{d+1}$
$a_i \cdot x + (b_i - \epsilon_i)x_{d+1} \leq b_i, 1 \leq i \leq n$
$x_{d+1} \geq 0$

where the $\epsilon_i$ are indeterminates with lexicographic order $0$ < $\epsilon_n$ << $\cdots$ << $\epsilon_1$ << $1$. (Apparently ASCIIMathML doesn't support \ll yet.) Check that the apex is indeed at $(0, \ldots, 0, 1)$. Because the $\epsilon_i$ are very small, we know that $(x, 0)$ is optimal for the new program iff $x$ is optimal for the original.

Not surprisingly, we are not done yet. It's true that in principle the new program can be solved in a linear number of pivots, but the hard question remains: which sequence of pivots do you want?

Now how Lee's method meshes with tools from smoothed analysis seems to be a long story. My day dreaming is that we could control the apex perturbation more carefully. Then the apex can be used as a polynomial time oracle: You start at an extreme point in the original polytope, take the airplane to go to the apex, compute, then jump down with a parachute along a carefully chosen edge to end up at another extreme point that is expected to be closer to the optimal.

I hope one day I will come back to write more. "Time is always against us. Please, take a seat there."

As an aside, from this Slashdot post I also learned about The Unsolvable Math Problem urban legend in which Dantzig unknowingly solved two major open problems as homework questions. Hehe.

SPEAKER: Vincent Conitzer

TITLE: Computational Aspects of (Iterated) Dominance, Nash Equilibrium, and What Lies In-Between

ABSTRACT: Two fundamental solution concepts in game theory are (iterated) dominance and Nash equilibrium. A strategy (probability distribution over the player’s actions) is dominated if it performs worse than some other strategy, against any opponent strategies. In iterated dominance, dominated strategies are removed, after which other strategies may become dominated, etc. A Nash equilibrium consists of a strategy for each player so that no player has an incentive to deviate. A Nash equilibrium always exists (Nash 50), but the question of how hard it is to compute one has been called “together with factoring […] the most important concrete open question on the boundary of P today” (Papadimitriou 01)

In this talk, I will discuss some of our most recent results on computational questions that concern these solution concepts. I will also provide a generalized eliminability definition that spans a spectrum from dominance to Nash equilibrium. Whether a strategy can be eliminated can be computed efficiently if we are close to the “dominance” end of this spectrum, but it is coNP-complete at the “Nash” end of the spectrum.

September 23rd 2005
Wean 7220
3:30pm

Speaker:
Stefano Leonardi, Visiting Faculty from Universita’ di Roma “La Sapienza”

Title:
Cost-sharing Mechanisms for Network Design

Abstract:

Today’s Internet seamlessly connects billions of users that mostly pursue selfish motives in both, single-handed and collaborative ways. By design the Internet is anarchic and hence, it is devoid of a central authority that possesses global knowledge and the power to regulate the agents’ behavior. In this talk we focus on the design of so called ‘mechanisms’ that encourage truthful and fair behavior among the agents/users by means of issuing rewards and by postulating interaction rules.

We present a first mechanism able to share between users in a fair manner the cost of a Steiner forest that connects a set of terminal pairs. This mechanism is also proved to recover at least 1/2 the cost of the solution. This mechanism is a primal dual algorithm based on a new linear programming relaxation that is shown stronger than the classical undirected cut relaxation. We also prove that no such mechanism can recover more than 1/2 of the cost of the solution for the Steiner tree game, therefore implying tightness of our result.

This is joint work with Guido Schaefer (TU Berlin), Jochen Koenemann (University of Waterloo) and Stefan van Zwam (Eindhoven University of Technology).

If you have not registered for FOCS 2005 yet, please consider doing it now. The early registration for the conference and also the hotel is ending this Friday (Sept 23).

http://www.cs.cmu.edu/~FOCS05/

Abie Flaxman (CMU)

“Random Sampling Auctions”

September 29, 15:00-16:00, PPB 300

ABSTRACT:
Random sampling is the most prevalent technique for designing incentive-compatible auctions to maximize the auctioneer’s profit when the bidders’ valuations are a priori unknown. The first and simplest application of random sampling to auctions is in the context of auctioning a digital good. For this problem, the random sampling optimal price auction works by selecting a bipartition of the bidders uniformly at random and offering the optimal sale price for each part to the other part.

We give a simple analysis of the competitive ratio of the random sampling auction. The random sampling auction was previously known to be worst-case competitive with a bound of 7600; our analysis improves the bound to 15. It is believed that the auction is in fact 4-competitive, and we show that on the equal revenue input, where any sale price gives the same revenue, random sampling is exactly a factor of four from optimal.

This is joint work with Uri Feige, Jason Hartline, and Bobby Kleinberg.

Speaker: Maverick Woo
Time: Wednesday 12pm-1pm
Place: NSH 1507

Title: A Tale of Two Simple Data Structures

Abstract:

Among the numerous designs for meldable heaps, Fat Heaps by Kaplan and Tarjan (1998) stand out to be almost perfect. Fat Heaps retain the simplicity of Fibonacci Heaps, but the time bounds are worst-case instead of amortized (although they don’t match Fibonacci Heaps in the Meld operation.) The key ingredient in this design is an abstraction known as redundant counters, introduced by Clancy and Knuth back in 1977. I will show how Fat Heaps work, and more importantly, how we can understand its design from a deamortization point of view. This part of the talk will be self-contained.

In the Dynamic Connectivity problem, we are given a set of $n$ fixed vertices on which we have to maintain a dynamic graph supporting an intermixed sequence of edge insertions, edge deletions and connectivity queries (”Are $u$ and $v$ connected?”). A long line of papers have been written on this problem, but I will focus on the conceptually simple design by Holm, de Lichtenberg and Thorup (1998) that supports each operation in deterministic amortized $O(log^2 n)$ time. This part of the talk will depend on an abstraction known as Dynamic Trees. I will explain the abstraction but will not go into the details of its implementation and analysis.

Notes from Maverick:

Coincidentally, Danny Sleator is teaching how to implement Dynamic Trees with Splay Trees in his Advanced Data Structure course right after this talk. The class starts at 1:30pm in Wean 4623.

Some days ago Anupam asked me how to insert a blank slide right after the current one during a slide show. It may seem curious to many people, but if you teach with a Tablet PC, then it makes perfect sense. This is analogous to having blank transparencies (and the Tablet stylus as the marker) when using an overhead projector. It’s especially useful when a question pops up from the audience and you would like to address it with the help of writing things down. And if you are using PowerPoint 2003, you can retain all the handwritings you made during the slide show and distribute them together with the exisiting slides.

The straightforward way of doing it is to break out from the slide show, insert a blank slide and then resume the show. But do we have a slicker way?

Turns out this is not hard to do in PowerPoint. First, press Alt-F11 (Tools->Macro->Visual Basic Editor). Select Insert->Module in the main menu. Now enter the following code:

Sub InsertBlankSlide()
Dim newIndex As Long
With ActivePresentation
newIndex = .SlideShowWindow.View.Slide.SlideIndex + 1
.Slides.Add newIndex, ppLayoutBlank
.SlideShowWindow.View.GotoSlide newIndex
End With
End Sub

Select File->Close and Return to PowerPoint. Now go to the Master slide and create a new shape there. Right click on that shape and select Action Settings. In the Mouse Click tab, select Run Macro and pick InsertBlankSlide from the combo box underneath it. Click OK and there you go. (Try running the presentation and click on that new shape.)

For a more elaborate example that also includes changing pen type, I refer you to Anupam’s slides in 15-251 (CMU’s 200-level CS theory core). For example, look at this one. It’s true that you can change the pen type by pressing hot keys during a slide show, but if you are using a slate Tablet PC, then you don’t have a keyboard.

P.S. It would be nice if we can change the pen weight programmatically since the default pen weight is a bit too thick. However, I haven’t spent enough time to get it working. All I know is that this is not possible in the object model that PowerPoint exposes. That, however, only means this cannot be done easily (as I have an example here). On the other hand, Anupam has pointed out that you only need to change the pen weight once during a slide show and the weight will not change during the rest of the show. I guess it’s easier to wait for Office 12 to come out than to nail it.

Friday, September 16, 2005
2:00 pm Posner Hall 259

Vineet Goyal
Tepper School of Business

Title:
Approximation Algorithms for Demand-Robust and Data-Robust Optimization Problems

Abstract:
Robust Optimization has traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worst case among the various uncertain scenarios in the model. However besides the costs, uncertainty can also be in the problem constraints or “demand”. To model such uncertainty demand-robust versions of common optimization problems were recently introduced (Dhamdhere et al., FOCS 2005) motivated by worst-case considerations of two-stage stochastic optimization models. We consider the shortest path and minimum spanning tree problems under demand-robust and data-robust models and give approximation algorithms for the same.

In this talk, I would present the improved approximation algorithm for the demand-robust shortest path problem which improves the approximation factor from 16 to 7.1. I would also present some hardness results for the data-robust models.

This is joint work with R. Ravi.

John Turner
Tepper School of Business

Title:
Robust Solutions for Some Special Cases of the Resource-Constrained Project Scheduling Problem

Abstract:
In the pursuit of robust solutions to the Resource Constrained Project Scheduling Problem, we introduce the robust objective $\sum_i Pred(i)$, which counts the total number of precedence relationships in a schedule. We focus on the special case of RCPSP that has a single resource and whose temporal constraints are precedence constraints. In the standard notation, this problem is $PS1|prec|\sum_i Pred(i)$. To our knowledge, this objective has not been previously studied in the context of project scheduling. By employing a generalization of Dilworth’s Theorem, we develop a MILP and then suggest the use of Bender’s Decomposition to solve this MILP. The use of Bender’s Decomposition is justified by the fact that the Bender’s subproblem in our case is a network flow problem, which can be solved very quickly. We then conclude with some symmetry-breaking and min-forbidden-set-breaking constraints that may be added to the master problem ILP to speed up solution time.

Thursday September 15, at 16:00
Room 300 in PPB (Physical Plant Building)

Oleg Pikhurko (CMU)
How to solve a hypergraph Turan problem exactly?

Abstract:

For a k-graph F, the Turan function ex(n,F) is the maximum size of an F-free k-graph on n vertices. In general, it is notoriously hard to determine. Even if we know ex(n,F) asymptotically, the exact computation might turn out to be a difficult task. I will discuss the stability approach for proving exact Turan results that was suggested by Simonovits in the 1960s and used recently by Furedi, Keevash, Mubayi, Sudakov, and others.

Some of the presented results are joint work with Dhruv Mubayi.

From my inbox is a question related to my post on wireless presentation control:

Q: Without walking over to the keyboard, how do you go to the previous slide with just a wireless mouse (that doesn’t allow you to control the cursor)?
A: Go to to Tools->Options->View and disable “Popup/Show menu on right mouse click”.

With this option disabled, a right click will bring you to the previous slide. I really think this option should be disabled by default, but it isn’t.

Note that even if you have disabled this option, you can still “pop” the popup menu. Put down the wireless mouse on a table and move the cursor. You will notice the popup menu icon on the lower left corner. Click on it and you will get back the popup menu that you used to get with a right click. (In PowerPoint 2003, you will see four icons instead of one, but the situation is similar.)

Also note that most commands in that popup menu actually have keyboard shortcuts. Press ? (the question mark) in the slide show mode to discover them. I consider the ability to jump to any slide quickly the most important.

Have fun teaching!

The Joint ALADDIN/Theory/Operations Research Seminar

Date: September 16th 2005
Time: 3:30
Place: Wean 7220
Title: Algorithmic Self-Assembly: Models and Problems
Speaker: Ashish Goel, Stanford University

Abstract:
Self-assembly has emerged as an important technique for molecular computation and nano-technology. At these scales, self-assembly is governed by simple (and local) probabilistic rules for growth.

We will discuss two important challenges in algorithmic self-assembly, robustness and efficiency.

This talk will present recent results, and also attempt to provide a road-map of open problems.

Speaker: David Abraham
Time: Wednesday 12pm-1pm
Place: NSH 1507
Title: Two-Sided Matching Markets with One-Sided Preferences

Abstract:

In many countries, new medical graduates are required to take a one-year intern position before achieving full accreditation. Some graduates prefer hospitals that are close to their home, whilst others base their preferences on prestige, money etc. Unfortunately, there are only a limited number of positions, and so some graduates may not be allocated one of their top choices.

How do we decide which graduates go where? If hospitals have preferences over graduates, this is just the well-known Stable Marriage problem. However, if the market only has one-sided preferences, the answer is not so clear.

In this talk, we will discuss several alternative objective functions. We will focus on the problem of finding a popular matching - one for which there is no other matching that more graduates prefer.

This talk is in partial fulfilment of the speaking requirement.

I’m just wondering if anyone from CMU is planning to go to the AMS Sectional Meeting held in Johnson City, TN on Oct 15-16.

See link: http://www.ams.org/amsmtgs/2116_program.html

Right now, I haven’t decided whether I’m going or not. So, if you’re planning or just considering to go, please drop me an email.

Hubert

Well, I don’t know if SODA is rising, falling, or maybe falling in one regard because it is rising in another, but I do know that the list of accepted papers has been published.

According to Cliff Stein, there were 432 submissions, of which 135 have been accepted. A comment at Jeff Erickson’s blog reveals that 135 is the maximum that they can fit in 3 days, as discussed in the business meeting last year.

Update: this is the official list on SODA 2006’s web site.

I have modified the Event Calender locally so that it works with the event metadata stored by WP iCal.

Now the Event section on the frontpage will show you a list of posts that contains future events. Post a comment here if you have suggestions.

I have installed Brian’s Threaded Comments and patched it a bit to work with SecureImage (CAPTCHA for anonymous comments). Now you can reply to a particular comment and have the comments threaded together. If you want, please feel free to try it out with this post.

Have fun!

P.S. In case you are running WordPress 1.5 and also want to get both Threaded Comments and SecureImage working, what you need is to patch Threaded Comments to rename the \$image array. Both packages use it and so they overwrite each other. Lovely global variables.

CS Theory town hall meeting

Introductions

Danny Sleator
Manuel Blum
Rick Statman – computability theory, resources in math dept, Alan Frieze, Tom Bohman, Oleg Pikhurko
Gary Miller – Sparse systems, class on numerical methods and spectral stuff
David Abraham – 2 sided matching markets
Abraham Flaxman – algorithms and uncertainty, take minutes, last year grad student, lets pool resources
Steven Rudich
Daniel Golovin – approx algorithms, uncertainty in input but not average case
Adam Weirman – 5ht year with Mor Harchol-Balter, scheduling and queues
Mugizi Rwebangira – learning labeled, unlabeled
David Offner – approximation algorithm, graph algorithms, and pure combinatorics
Pall Melsted – Graphs algorithms
Barbara Anthony – robust optimization
Don Sheehy – computational geom, 1st year
Roy Liu – masters student with Manuel and Luis
Michelle Goodstein – applied algorithms
Luis von Ahn – trying to graduate, makes stuff up
Mike Mass — 1st year combinatorial and graph algorithms
Hector – visiting Luis heading to TTI
Srinath Sridhar - comp biology, evolutionary trees, data structures
Mohit Singh - approx
Vineet Goyal - approx, robust optimization and approximation
Mike Rochash – programming languages and applications
Dan Blandford – compressed data structures
Konstantin Andreev - 6th year with Bruce Maggs
Guy Blelloch – graph compression, data structures
Stefano Leondari – visiting for year, approx online game theory complex networks
Dan Licada – logic and pl with bob harper
Phil Gibbons – Intel lab, has algorithm questions come out of systems work, and needs runners for pretty good race Friday
Avrim Blum – machine learning approximation algorithms online algorithms.
ACO students from math and Tepper are here. Now there is a new official way for cs students to get involved in ACO– CS with minor in ACO. Take 3 semesters of courses from math and Tepper and go to ACO seminar. No application necessary.
FOCS conference here this fall. Avrim and Anupam are local chairs, they will need help. Especially reviews of local restaurants, 20 bucks per review (max 1 per person).
Anupam Gupta - approximation algorithm, metric embeddings, course this semester on approximation algorithms. Will put up a wiki for FOCS restaurants. Has other tasks for people to help with for FOCS, i.e. Registration,
Maverick Woo - 6th year, data structures, dynamic connectivity, worst case stuff, and graph theory, like preconditioners. Runs the theory group web server.
Hubert Chen - 4th year graph algorithms and metric embeddings algorithms
Katrina Ligett – taking over organizing theory lunch, which will be 12-1 on Wednesday in NSH 1507. weekly talk, usually by a student, fairly informal.

Seminars

Seminars – Theory Lunch Wednesdays 12-1, Theory Seminar Friday 3:30-4:30, ACO Seminar Thursday 4-5, Fri 2-3:30 OR seminar.

Should we schedule the OR and Theory seminars so that people do not have to run from one side of campus to the other?

Theory Announce mailing list, email Katrina to get added.

Scribes for theory lunch?

Other places are doing it. Quick thing, posted publicly or otherwise.

Maybe we should just record the questions and answers and post that.

Danny: is that for us or for pr? It could be good for pr.
Anupam: maybe the open questions and concluding comments would be valuable.
Stefano: A 1 page annotated bibliography
or maybe suggest a paper or two.

Blog

Maverick has started a blog, http://magic.aladdin.cs.cmu.edu, which has talks and abstracts and stuff.

Feedback from talks

Should we implement some system to provide feedback to speakers. Maybe an open ended form modeled on the speaking requirement form to give the speaker feedback. Suggestions to Katrina.

Wiki for a huge annotated bibliography

Daniel thinks is would be nice to have a knowledge base, especially for new students to get info on areas. This has already been planned, the Aladdin center’s algorithm depot. But not implemented. Maybe a wiki would work.

Share resources

If you know of other stuff that everyone should know, tell Katrina or post on wiki.

Friday, September 9, 2005
2:00 - 3:30 pm
388 Posner Hall

Minimum vehicle routing with a common deadline
Viswanath Nagarajan
Tepper School of Business

An important version of vehicle routing problems involves customer deadlines
and having to service all of them even though it may require many vehicles
to do so. Motivated by such applications, we study approximation algorithms
for the following NP-hard variant: the input to our problem consists of $n$
vertices in a metric space, a specified root vertex $r$, and a length bound
$D$. The goal is to cover all the vertices, using the minimum number of
$r$-paths, each of length at most $D$. On general metrics, we obtain an
$O(\log D)$ approximation algorithm for this problem. When restricted to
tree metrics, we obtain an improved 4-approximation algorithm. Both these
algorithms have a running time that is almost linear in the size of the
input. We also obtain tight bounds on the quality of a candidate lower bound
based on clumping, for general metrics.

On Minimum Degree Minimum Spanning Tree Problem
Mohit Singh
Tepper School of Business

Minimum Degree Minimum Spanning Tree(MDMST) Problem is a
fundamental network design problem. In an instance of MDMST
problem, given a graph $G=(V,E)$ and a cost function $c$ on edges,
we ask for a minimum spanning tree whose maximum degree is
minimized. Here, the maximum degree of a tree is the maximum
degree of any node in the tree. As the problem is NP-hard, we aim
obtain the near best algorithm which returns a MST with maximum
degree $OPT+1$ while the best known result due to Fischer returns
an MST of maximum degree at most $O(OPT+\log n)$. Here, $OPT$
is the maximum degree of the optimum MST.

In my proposal, we presented a non-constructive optimal swap
theorem and a conjecture motivated by the theorem and previous
results. In this paper, we extend the known results which leads us
to a different conjecture. I will also present a roadmap of how
we plan to prove the new conjecture.

This is ongoing work with R. Ravi.