[Lowerbounds, Upperbounds]

Title: Scarf’s Lemma and the Stable Paths Problem
Speaker: Penny Haxell, Waterloo
When: May 1, 12:30-13:30
Where: Porter Hall 125B

Abstract:

We address a question in graphs called the stable paths problem, which is an abstraction of a network routing problem concerning the Border Gateway Protocol (BGP). The main tool we use is Scarf’s Lemma. This talk will describe Scarf’s Lemma and how it is related to other results more familiar to combinatorialists, and then will explain its implications for the stable paths problem.

Friday May 2nd, 2008
3:30 PM
7500 Wean Hall

Nash Bargaining via Flexible Budget Markets

Vijay V. Vazirani, Georgia Tech

In his seminal 1950 paper, John Nash defined the bargaining problem; the ensuing theory of bargaining lies today at the heart of game theory. In this work, we initiate an algorithmic study of Nash bargaining problems.

We consider a class of Nash bargaining problems whose solution can be stated as a convex program. For these problems, we show that there corresponds a market whose equilibrium allocations yield the solution to the convex program and hence the bargaining problem. For several of these markets, we give combinatorial, polynomial time algorithms, using the primal-dual paradigm.

Unlike the traditional Fisher market model, in which buyers spend a fixed amount of money, in these markets, each buyer declares a lower bound on the amount of utility she wishes to derive. The amount of money she actually spends is a specific function of this bound and the announced prices of goods.

Over the years, a fascinating theory has started forming around a convex program given by Eisenberg and Gale in 1959. Besides market equilibria, this theory touches on such disparate topics as TCP congestion control and efficient solvability of nonlinear programs by combinatorial means. Our work shows that the Nash bargaining problem fits harmoniously in this collage of ideas.

Iterative Methods in Combinatorial Optimization

Mohit Singh

Wednesday, April 30, 2008, 3:30 pm, 384 Posner

Abstract:

Linear programming has been a successful tool in combinatorial optimization to achieve polynomial time algorithms for problems in P and also to achieve good approximation algorithms for problems which are NP-hard. We demonstrate that iterative methods give a general framework to analyze linear programming formulations of polynomial time solvable problems as well as NP-hard problems.

In this thesis, we focus on degree bounded network design problems. The most well-studied problem in this class is the Minimum Bounded Degree Spanning Tree problem defined as follows. Given a weighted undirected graph with degree bound B, the task is to find a spanning tree of minimum cost that satisfies the degree bound. We present a polynomial time algorithm that returns a spanning tree of optimal cost and maximum degree B+1. This generalizes a result of Furer and Raghavachari to weighted graphs, and thus settles a 15-year-old conjecture of Goemans affirmatively. This is also the best possible result for the problem in polynomial time unless P=NP.

We also study degree bounded versions of general network design problems including the minimum bounded degree Steiner tree problem, the minimum bounded degree Steiner forest problem, minimum bounded degree k-edge connected subgraph problem and the minimum bounded degree arborescence problem. We show that iterative methods give bi-criteria approximation algorithms that return a solution whose cost is within a small constant factor of the optimal solution and the degree bounds are violated by an additive factor in undirected graphs and a small multiplicative factor in directed graphs. These results also imply first additive approximation algorithms for various degree constrained network design problems in undirected graphs.

We also show the generality of the iterative methods and apply it to the degree constrained matroid problem, multi-criteria spanning tree problem, multi-criteria matroid basis problem and the generalized assignment problem achieving or matching best known approximation algorithms for them.

Thesis Committee:
Prof. R. Ravi, Carnegie Mellon University (Chair)
Prof. Gerard Cornuejols, Carnegie Mellon University
Prof. Alan Frieze, Carnegie Mellon University
Prof. Michel Goemans, Massachusetts Institute of Technology
Prof. Anupam Gupta, Carnegie Mellon University

A while ago I checked out Beautiful Code from our library. Jon Bentley wrote chapter 3, which is about Quicksort, and paradoxically named the chapter “The Most Beautiful Code I Never Wrote”. This video is an extension of that chapter and will explain the name. I can recommend the talk, especially the third part in which he talks about the industrial implementation of qsort (that part starts shortly after 34:00).

April 30, 2008
Varun Gupta
12:00 PM, 1507 Newell-Simon Hall
Title: Optimal size-based scheduling with selfish users

Abstract:

We consider the online single-server job scheduling problem. It is known that to minimize the average response time of jobs in this setting, at all times the job with the shortest remaining service time must be scheduled. This requires that the server knows about the sizes of all the jobs. However, in the scenario where the server does not know the sizes of the jobs whereas the jobs know their own sizes, the server can not rely on the jobs to truthfully reveal their sizes since a job may reduce its own response time by misreporting. While there are mechanisms in the literature that achieve truthful revelation, such mechanisms are based on imposing a tax and hence involve “real” money - which is not always desirable.

In this work, we propose a novel token based scheduling game. We prove that while playing the above scheduling game, all the jobs trying to minimize their own response time will end up implementing the shortest remaining service time first scheduling policy themselves.

Available here at informIT.

Andrew Binstock and Donald Knuth converse on the success of open source, the problem with multicore architecture, the disappointing lack of interest in literate programming, the menace of reusable code, and that urban legend about winning a programming contest with a single compilation.

Among other things, he explained why the numbering of Volume 4 fascicles starts at 0 and not 1. (You may recall that there is no Volume 0 and so zero-based counting cannot be exactly the reason. Well, I mean not exactly.)

Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time

Pall Melsted, CMU
April 25, 2008, 3:30PM, Wean 7220

Abstract:

We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor.

This is joint work with Prasad Chebolu and Alan Frieze.

Title: The formulation complexity of minimum cut
Speaker: Ojas Parekh, Emory University
When: April 24, 12:30-13:30
Where: Porter Hall 125B

Abstract:

Our focus in this talk will be the size of linear programming formulations of combinatorial optimization problems. We may view this parameter as akin to traditional measures of complexity, such as computational time and space. We will focus on problems in P, in particular the minimum cut problem. For a graph $(V,E)$, existing linear formulations for the minimum cut problem require $\Theta(|V||E|)$ variables and constraints. These formulations can be interpreted as a composition of $|V|-1$ polyhedra for minimum $s$-$t$ cuts paralleling early algorithmic approaches to finding globally minimum cuts, which relied on $|V|-1$ calls to a minimum $s$-$t$ cut algorithm. We present the first formulation to beat this bound, one that uses $O(|V|^2)$ variables and $O(|V|^3)$ constraints. Our formulation directly implies a smaller compact linear relaxation for the Traveling Salesman Problem that is equivalent in strength to the standard subtour relaxation.

Date: 2008-04-23 12:00
Place: NSH 1507
Speaker: Elaine Shi
Title: How to build private Google Docs

Abstract: I will describe some latest results in predicate encryption. The crypto construction allows a user to store her personal files on a remote untrusted server, and make expressive search queries to retrieve certain documents. The remote untrusted server learns no unintended information.

Title: Approximation Algorithms for Vehicle Routing and Scheduling.

Viswanath Nagarajan, Thesis Proposal for Ph.D. in Algorithms, Combinatorics and Optimization.
10:30am Wednesday 23-April
Room 384, 3rd floor Posner Hall (Tepper School of Business)

Broadly speaking, any scheduling problem can be characterized as serving a set of requests using a limited set of resources, subject to constraints detailing how the resources may serve requests. Due to the complicating nature of constraints in typical scheduling problems, most of them are NP-complete and hence we do not expect efficient (i.e. polynomial time) exact algorithms. The two main approaches to practical solutions of such problems are (i) exact algorithms that compute the optimal solution but take exponential time in the worst case, and (ii) heuristic algorithms that run in polynomial time but find near-optimal solutions. An approximation algorithm is an efficient heuristic along with a worst-case guarantee on the quality of the near-optimal solutions found by it. The goal of this thesis is to design approximation algorithms for some scheduling problems, with an emphasis on Vehicle Routing Problems.

Vehicle routing problems (VRPs) form a rich class of variants of the basic Traveling Salesman Problem, that are also practically motivated. In VRPs, a fleet of vehicles represents the resources used to serve a set of client-requests (such as transporting objects to the clients). Many VRPs just seek to minimize cost incurred by the vehicles while serving client requests; a goal in this thesis is to study VRPs that incorporate some additional criteria on the vehicle routes.

All VRPs are defined in relation to a metric space (i.e. set of locations with a distance function on them). Most of the work on approximation algorithms for VRPs has focussed on symmetric metrics. The corresponding problems on asymmetric metrics become considerably harder. Another goal of this thesis is to design algorithms for VRPs on asymmetric metrics.

Committee: R. Ravi (Chair), Gerard Cornuejols, Anupam Gupta, Mike Trick

Date: 2008-04-16 12:00
Speaker: Mike Dinitz
Title: The Discounted Secretary Problem
Place: NSH 1507

Abstract:

The classical secretary problem studies how to select online an element with maximum value in a randomly ordered sequence. The problem is closely connected with online mechanism design in which agents {e} with private values v(e) for a good arrive sequentially in random order and the mechanism designer wishes to allocate the good to an agent with maximum value. The difficulty lies in the fact that an agent’s allocation must be decided irrevocably upon arrival. A mechanism for this problem is called alpha-competitive if it gets, in expectation, at least a 1/alpha fraction of the (expected) optimal offline solution. It is well-known how to design constant-competitive algorithms for the classical secretary problem and several variants. In this talk we will discuss the discounted secretary problem, in which there is a time-dependent “discount” factor d(t) and the benefit derived from assigning the good at time t to agent e is the product of d(t) and v(e). For instance, the special case when d(t) is decreasing captures the natural tension between selling early and waiting to maximize the value of the agent receiving the good. We provide nearly matching logarithmic upper and lower bounds for this problem, and show a constant-competitive algorithm when the expected optimum is known in advance.

Name: Nikolaos Sahinidis
University: Carnegie Mellon University Dept. of Chemical Engineering
Date: Friday, April 18, 2008
Time: 3:30 to 5:00 pm
Location: Room 388 Posner Hall
Title: Optimization in the New Biology

Abstract:

A variety of modern bioinformatics and systems biology problems can be approached systematically from an optimization point of view. This talk will focus on protein side-chain prediction, protein structural alignment, structure determination from X-ray diffraction measurements, and metabolic systems analysis and design. To solve these problems, we have employed machinery from linear algebra, dynamic programming, combinatorial optimization, and mixed-integer nonlinear programming. Many of the underlying biological problems are purely continuous in nature but have, to this date, been approached mostly via combinatorial optimization algorithms that are applied to discrete approximations. Other problems naturally present a strong and difficult combinatorial component.

Title: A Polynomial Bound on Vertex Folkman Numbers
Speaker: Andrzej Dudek, Emory University
When: Tuesday April 15, 12:30-13:30
Where: Wean Hall 5304

Abstract:

In 1970, Folkman proved that for a given integer r and a graph G of order n there exists a graph H with the same clique number as G such that every r coloring of vertices of H yields at least one monochromatic copy of G. His proof gives no good bound on the order of graph H, i.e., the order of H is bounded by an iterated power function of n. In this talk we will give an alternative proof of Folkman’s theorem with the relatively small order of H bounded from above by O(n^3 log^3 n). This is joint work with Vojtech Rodl.

Friday April 18th, 2008
3:30pm
WEH 7220

TITLE: What makes a good Steiner point?

Benoit Hudson
Toyota Technological Institute at Chicago

ABSTRACT:

The mesh refinement problem is to take an input geometry (defined by a set of points, curves, and surfaces), and output a set of points that both “respects'’ the geometry and has good “quality.'’ What it means for a tetrahedral mesh to respect curved surfaces is already interesting and will take some explaining. Even knowing what the goal is, mesh refinement algorithms typically are of the form: until the output is good enough, add points. But where should we add these additional Steiner points? And how do we know that the algorithm will stop? Most prior work is very specific about where to add points, and thus needs its own very specific proof that the algorithm ends.

In this talk, I will give a set of rules for choosing Steiner points. Any algorithm that follows my rules — as most previous algorithms do — will terminate. After hearing me out, you will know how to represent curved surfaces with linear elements, and you will be able to design your very own meshing algorithm with confidence.

Via this post in Michael Trick’s Operations Research Blog, I discovered a truly mesmerizing article about teaching: The Amazing Miss A And Why We Should Care About Her. I hope you would enjoy it as much as I do.

And after you have read Michael’s post and the article, I invite you to think about CS education.

Title: Approximation Algorithms for Network Design With Uncertainty
Speaker: Barbara Anthony
When: Wednesday, April 16, 10:30 am
Where: Doherty Hall 4303

Abstract: We present an extension of the k-median problem where we are given a metric space (V,d) and not just one but m client sets S_i (subsets of V) for i = 1, …, m, and the goal is to open k facilities F to minimize the worst-case cost over all the client sets, i.e. max_{i in [m]} sum_{j in S_i} d(j,F). This is a ‘min-max’ or ‘robust’ version of the k-median problem; however, note that in contrast to previous papers on robust/stochastic problems, we have only one stage of decision-making — where should we place the facilities? We present an O(log n + log m) approximation for robust k-median: The algorithm is simple and combinatorial, and is based on reweighting/Lagrangean-relaxation ideas. In fact, we give a general framework for (minimization) facility location problems where there is a bound on the number of open facilities. For robust and stochastic versions of such location problems, we show that if the problem satisfies a certain ‘projection’ property, essentially the same algorithm gives a logarithmic approximation ratio in both versions. We use our framework to give the first approximation algorithms for robust/stochastic versions of k-tree, capacitated k-median, and fault-tolerant k-median.

This talk, on robust and stochastic location problems, covers one part of my thesis on approximation algorithms for network design with uncertainty.

Thesis Committee:
Anupam Gupta (Computer Science, chair)
Thomas Bohman (Math)
Alan Frieze (Math)
R. Ravi (Tepper)

Speaker: Eric Blais
Title: Testing juntas
Date: 2008-04-09 12:00
Place: NSH 1507

Abstract:

A function on $n$ variables is called a $k$-junta if it depends on at most $k$ of the variables. A randomized algorithm $A$ is an algorithm for testing $k$-junta if it can reliably distinguish the case where a given function $f$ is a $k$-junta from the case where $f$ is “far” from being a $k$-junta using only a few queries to $f$. In this talk, we will explore the following question: What is the minimum number of queries required by to test $k$-juntas? Until recently, all known algorithms for testing $k$-juntas required at least $O(k^2)$ queries. I will introduce a new algorithm for testing $k$-juntas with only $O(k^{1.5})$ queries.

I think this would be worth mentioning for my CMU fellows:

As you know we have campus-wide subscriptions to many web services, like the ACM Digital Library and Elsevier’s “ScienceDirect”. But if you are off-campus, then understandably you cannot take advantage of such subscriptions. There was a time when all you could do was to ssh into a campus machine followed by, say, a wget+scp dance. But these days you can also use the “WebVPN service“, which is I find to be a lot more convenient, and direct.

I just noticed that the ACM Digital Library have started to prominently display “Bibliometrics” for each of its articles. Currently, we get the number of downloads in the last 6 weeks and last 12 months, as well as the number of citations. The last of which was available before, but you had to go further down into the page.

In case you want a quick link to see, here is Bob Tarjan’s classic Efficiency of a Good But Not Linear Set Union Algorithm.

Title: Two results in Discrete Differential Geometry
Speaker: Aaron Trout, Chatham University
When: April 3, 12:30-13:30
Where: Porter Hall 125B
Abstract:

We will discuss two results in discrete differential geometry: 1) A combinatorial 3-manifold with edges of degree at most five has edge-diameter at most five. 2) Suppose such a combinatorial 3-manifold $M$ has vertices $v$ and $w$ at the maximum edge-distance. Then, $M$ is a 3-sphere whose triangulation is completely determined by the star of $v$. These theorems are analogous to two important results in the differential geometry of positively curved spaces. The first is analogous to the Bonnet-Myers theorem, which bounds the diameter of Riemannian manifolds whose Ricci curvature is everywhere greater than a fixed positive constant. The second result is a discrete version of the Toponogov-Cheng rigid-sphere theorem, which shows that the maximum diameter allowed by the Bonnet-Myers theorem is achieved only for the standard sphere. The proofs we present are entirely combinatorial in nature, use only elementary arguments, and follow closely the proofs of the corresponding classical results. We will also talk about some enumeration algorithms which can be used to investigate the geometry of combinatorial manifolds. This talk is based on my Ph.D. thesis, which was done at Rice University under the direction of Robin Forman.