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.
Speaker: Christian Klein
Title: Unbiased Controlled Rounding
Date: 2008-04-02 12:00
Place: NSH 1507
Abstract:
Rounding a real-valued matrix to an integer one, such that the rounding errors in all rows and columns are less than one, is a classical problem. It has been applied to hyper-graph coloring, in scheduling and in statistics. Here, it often is also desirable to round each entry randomly such that the probability of rounding it up equals its fractional part. This is known as unbiased rounding in statistics and as randomized rounding in computer science.
In statistics, such roundings are mainly used for two reasons. First, given a table of statistical data, one can increase its readability by rounding each entry to multiples of (some power of) 10. Second, such roundings can be used for statistical disclosure control. Here, one wants to avoid that an attacker can identify individual respondents from the published data.
In this talk, several ways to compute such roundings are presented. They all also ensure some kind of local data consistency that is particularly useful for statistical data, namely that the rounding error in all initial intervals of rows (and columns) is less than one.
It’s All Text! is one of my most-used Firefox add-ons and recently it’s been upgraded to run on 3.0b4.
Edit textareas using an external editor, because it’s all text!
Right click on a textarea, select “It’s All Text!” and edit the text in the editor of your choice.
Alternatively, click on the edit buttons added for your convenience. Right click on the edit buttons for even more options, including preferences.
There are good reasons why you want to use your own favorite text editor to do text editing, and this add-on makes the process extremely easy (no cut and paste needed). But my initial reason was to avoid the “back” button: on my ThinkPad, it’s right next to the arrow keys and if you happen to hit it by mistake, whoosh, all your text is gone…
Highly recommended.
P.S. Of course this post and many others are written using it. 
Title:Intersection Cuts in 2 Dimensions
Speaker: Francois Margot, CMU
When: March 27, 12:30-13:30
Where: Porter Hall 125B
Abstract:
When solving Mixed Integer Linear Programs (MILP) with branch-and-cut algorithms a variety of cuts can be generated. The best known cuts are probably Gomory mixed integer cuts, obtained from a single row of the optimal simplex tableau for the linear relaxation of the MILP. Recently, results on generating cuts using information from two rows of the tableau have appeared. In particular, Andersen, Louveaux, Wolsey and Weismantel (2007) investigate the facets of a particular relaxation of the MILP to a problem with two integer variables and two constraints. They show that all facets are then split inequalities or intersection cuts obtained from triangles or quadrilaterals. We give the converse, determining which of these splits, triangles and quadrilaterals actually give facets. We also give the corresponding characterization for an infinite-dimensional relaxation of the relaxation of Andersen et al., similarly to the relaxation used by Gomory and Johnson in their study of the group problem. Joint work with Gerard Cornuejols.
Via Punk Rock OR, I wish you will 133.1% agree with this post.
When: 2008-03-25 12:00
Where: NSH 1507
Speaker: Aaron Roth
Title: The Price of Malice in Linear Congestion Games
Abstract:
The price of anarchy has proven to be a useful measure for quantifying the degradation of performance in a system that is populated by selfish agents. However, it is a brittle measure, because it assumes that all users of the system are perfectly rational and adeptly seek to minimize their own cost. In actual networks, this is not always the case! Users may be oblivious to congestion, may be unable to calculate optimal routes, or may be explicitly malicious (consider, for example, denial of service attacks and worms). In this talk, we study the price of malice in traffic routing games, in which users must choose paths on a network to route their flow, and incur traffic dependent latency costs. We quantify by how much Byzantine (possibly malicious) users can degrade social cost. We provide bounds on two measures of the price of malice that have been proposed in the literature, by bounding the price of total anarchy. Bounding the price of malice using the price of total anarchy has the advantage that our bounds on social cost can be plausibly achieved by computationally efficient, decentralized agents who may only be aware of their own costs.
Where: 1507 NSH
When: 2008-03-19 Noon
Speaker: Abe Othman
Title: Beyond the Revelation Principle: Manipulation-Optimal Mechanisms
Abstract:
Rational, self-interested agents will lie to a mechanism if it benefits them. Despite this, the revelation principle states that any outcome a mechanism implements can also be implemented by a mechanism where agents are motivated to tell the truth. In this paper, we introduce the concept of manipulation-optimal mechanisms: non-truthful mechanisms that always do as well as the best truthful mechanism, and strictly better if any agent fails to find/play its best manipulation (lie).
Though the existence of such a mechanism has been shown previously in an artificial context, we study how broadly the paradigm applies in general. We curtail it with an impossibility result: in a manipulation-optimal mechanism, each agent can have at most one manipulable type. For such settings, we show that manipulation-optimal mechanisms can exist if the goal is social welfare maximization, but not when agents are symmetric and the mechanism is anonymous. We also show that there exist anonymous manipulation-optimal mechanisms with the goal of affine welfare maximization, even with symmetric players.
We then explore a way around our impossibility result: natural restrictions on the agents’ strategies. We study the Generalized Second-Price auction used by Google, Yahoo!, and MSN to auction billions of dollars of search keywords annually. This mechanism has been criticized because it is manipulable. Under two common assumptions, however, we show that it is manipulation optimal. Thus, switching to a truthful mechanism could only be deleterious to profits.
Joint work with Tuomas Sandholm.
Name: R. Ravi, Tepper School of Business and Russell Schwartz, Computer Science Department
University: Carnegie Mellon University
Date: Friday, March 7, 2008
Time: 1:30 to 3:00 pm
Location: Room 151 Posner Hall
Title: Mathematical Programming Methods for Phylogeny Reconstruction from Genetic Variation Data
Abstract:
Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny inference will be required if we are to be able to continue to make effective use of the rapidly growing stores of variation data now being gathered. We present two integer linear programming (ILP) formulations to find the most parsimonious phylogenetic tree from a set of binary variation data. One method uses a flow-based formulation that can produce exponential numbers of variables and constraints in the worst case. The method has, however, proven extremely efficient in practice on datasets that are well beyond the reach of the available provably efficient methods, solving several large mtDNA and Y-chromosome instances within a few seconds and giving provably optimal results in times competitive with fast heuristics than cannot guarantee optimality. An alternative formulation establishes that the problem can be solved with a polynomial-sized ILP.
The above methods are applicable for reconstruction of maximum parsimony trees from haplotype data, but such data are difficult to determine directly for autosomal DNA. Data more commonly is available in the form of genotypes, which consist of conflated combinations of pairs of haplotypes from homologous chromosomes. Currently, there are no general algorithms for the direct reconstruction of maximum parsimony phylogenies from genotype data. Hence phylogenetic applications for autosomal data must therefore rely on other methods for first computationally inferring haplotypes from genotypes. We extend our previous methods for computing maximum parsimony phylogenies directly from genotype data. We show that the standard practice of first inferring haplotypes from genotypes and then reconstructing a phylogeny on the haplotypes often substantially overestimates phylogeny size. As an immediate application, our method can be used to determine the minimum number of mutations required to explain a given set of observed genotypes.
Joint work with Srinath Sridhar, Fumei Lam and Guy E. Blelloch.
Time: 2008-03-05 12:00
Place: NSH 1507
Speaker: Deeparnab Chakrabarty
Title: Steiner Trees – Geometry, Linear Programs and Algorithms
Abstract:
In this talk, we investigate the bidirected cut LP relaxation for the Minimum Steiner Tree problem. We use geometry to devise a new lower bound on the cost of any Steiner tree. The lower bound is captured via an LP which we call the simplex-embedding LP. A short description of it is that it is an l_1-embedding of the graph on a simplex, maximizing a certain linear objective function. Interestingly, the dual of the LP turns out to be equivalent to the bi-directed cut relaxation.
For quasi-bipartite graphs, graphs which have no Steiner-Steiner edges, we will show how we improve the upper bound on the integrality gap of our LP relaxation (and hence as well as the bidirected cut LP relaxation). In this talk, we will show an upper bound of $\sqrt{2}$ which improves upon the known 3/2. We will also indicate how this can be further improved to 4/3. In contrast, the best lower bound known is 8/7 by Martin Skutella.
This is joint work with Nikhil R. Devanur and Vijay V. Vazirani.
Title: Coloring triangle-free graphs on surfaces
Speaker: Robin Thomas, Georgia Tech
When: February 28, 12:30-13:30
Where: Porter Hall 125B
Abstract:
Let S be a fixed surface, and let k and q be fixed integers. Is there a polynomial-time algorithm that decides whether an input graph of girth at least q drawn in S is k-colorable? This question has been studied extensively during the last 15 years. In the first part of the talk we will survey known results. In the second part of the talk we describe a solution to one of the two cases left open (the prospects for the other one are not bright). For every surface S we give a polynomial-time algorithm that computes the chromatic number of an input triangle-free graph G drawn in S. The new contribution here is deciding whether G is 3-colorable, and is obtained using a coloring extension theorem that in turn makes use of disjoint paths in order to construct a coloring. The notion of “winding number” of a 3-coloring plays an important role. This is joint work with Zdenek Dvorak and Daniel Kral.
