[Lowerbounds, Upperbounds]

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.