[Lowerbounds, Upperbounds]

SPEAKER: Anupam Gupta
TIME: Thursday 4:30-5:30 pm, November 2nd, 2006
PLACE: PPB 300
TITLE: Oblivious Network Design

Consider the following form of the Steiner Forest problem: for each pair of vertices {u,v} in the network, you have to decide on a *single path* P_{uv} between u and v. Now an adversary decides the set S of pairs to be connected, and you pay \$1 for each edge in the \union_{(u,v) \in S} P_{uv}.

Question: How should you choose the paths?

We show O(log^2 n)-competitive algorithm for this problem. In general, we develop a framework to model oblivious network design problems (of which the above problem is a special case), and give algorithms with poly-logarithmic competitive ratio for problems in this framework (and hence for this problem).

This is joint work with MohammadTaghi Hajiaghayi and Harald Raecke.

SPEAKER: MohammadTaghi Hajiaghayi
TIME: Wednesday 12-1pm, November 1, 2006
PLACE: NSH 1507

TITLE: Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design and Related Problems

ABSTRACT:
We consider approximation algorithms for non-uniform buy-at-bulk network design problems. Buy-at-bulk network design problems arise in settings where economies of scale and/or the availability of capacity in discrete units result in concave or sub-additive cost functions on the edges. One of the main application areas is in the design of telecommunication networks. The typical scenario is that capacity (or bandwidth) on a link can be purchased in some discrete units u_1 < u_2 < ... < u_r with costs c_1 < c_2 < ... < c_r such that the cost per bandwidth decreases c_1/u_1 > c_2/u_2 > … > c_r/u_r. The capacity units are sometimes referred to as cables or pipes. A basic problem that needs to be solved in this setting is the following: given a set of bandwidth demands, install sufficient capacity on the links of an underlying network topology so as to be able to route the demands. The goal is to minimize the total cost. Alternatively, we can think of the following scenario. We have two independent cost functions on the links of the network: a buy cost b(e) a rent cost r(e). We are given a set of demands between some pairs of nodes. A feasible solution for the non-uniform multicommodity buy-at-bulk instance is to buy some links and rent some other ones such that all the demands can be routed and the total cost is minimized; the cost of every bought edge is b(e) and for rented edges it is r(e) per unit of flow (bandwidth) over that link.

This problem generalizes several classical problems, such as minimum cost flow to the settings that the cost of each edge is a concave monotone function. It is known that the problem is hard to approximate within a factor of \Omega(log^{1/4-\eps} n) for any \eps>0. We give the first poly-logarithmic approximation algorithm for this problem.

Time permitting we will mention the applications of our approach for stochastic two-stage network design and network design with vertex costs.

Friday October 27, 2006
Wean 7220, 3:30PM

Buffer Heap: A Cache-Oblivious Priority Queue with Applications to Shortest Path Computations

Vijaya Ramachandran
University of Texas at Austin

We present the Buffer Heap (BH), a cache-oblivious priority queue that supports all traditional priority queue operations as well as the Decrease-Key operation in O((1/B) log n) amortized block transfers (or I/Os) per operation, where B is the (unknown) block size and n is the number of elements on the BH. Using the BH we present shortest path methods based on Dijkstra’s algorithm that are theoretically superior to traditional methods in terms of the number of I/Os performed.

We present experimental results that indicate that BH is faster than other general-purpose priority queues when the number of priority queue operations is reasonably large. We also present experimental results that show that shortest path methods that use BH and its variants are faster on some natural classes of graphs than Dijkstra’s algorithm with traditional general-purpose priority queues.

This is joint work with Rezaul Alam Chowdhury; additionally, Lingling Tong and David Lan Roche contributed to the experimental work.

SPEAKER: Todd Phillips
TIME: Wednesday 12-1pm, October 25, 2006
PLACE: NSH 1507
TITLE: Runtime-Efficient Meshing Algorithms

ABSTRACT:

I will overview the meshing problem in three and higher dimensions, presenting various state of the art algorithmic guarantees on the output. I will present a simple new meshing algorithm, “Sparse Voronoi Refinement” (SVR), that provides near-optimal worst case runtime along with output guarantees. We will explore how packing and structural lemmas lead to a concise, elegant proof of the runtime guarantees. We will discuss more complex extensions of SVR as well as SVR’s implications for future meshing research. This is joint work with Gary Miller and Benoit Hudson.

Speaker: Egon Balas, University Professor of Industrial
Administration and Applied Mathematics and
The Thomas Lord Professor of Operations Research

Title: On the Cycle Polytope of a Directed Graph and Its Relaxations
Date: Friday, October 20, 2006
Time: 1:30 to 3:00 pm
Place: Room 343 Posner Hall

Abstract

The cycle polytope of a digraph is the convex hull of incidence vectors of cycles. Some earlier papers (Balas 89, 95) on the Prize Collecting TSP gave a partial characterization of a higher dimensional representation of the cycle polytope in the space of arc and node (or arc and loop) variables. A subsequent paper on the Cycle Polytope (Balas and Oosten 98) explored the connection of this higher dimensional polytope with its projection on the space of arc variables, i.e. the standard representation of the cycle polytope. Together these papers gave an efficient procedure, based on lifting and projection, for generating from every facet defining inequality for the asymmetric TSP, a facet defining inequality for the cycle polytope. None of these facet defining inequalities cut off the origin, i.e. the incidence vector of the empty arc set. In recent joint work with Ruediger Stephan, we identified a rich set of facet defining inequalities for the cycle polytope that cut off the origin and are unrelated to the TSP. After investigating the relationship between the cycle polytope, its dominant, and the upper cycle polyhedron, we examine the polar relationship between cycles and permutations or the transitive tournaments they define. Our central result is a characterization of the relationship between facets of the dominant of the cycle polytope, facets of the cycle polytope that cut off the origin, and vertices of the linear relaxation of the transitive tournament polytope.

SPEAKER: Vijaya Ramachandran
TIME: Thursday 4:30-5:30 pm, October 19th, 2006
PLACE: PPB 300
TITLE: The Diameter of Sparse Random Graphs

ABSTRACT:

We derive an expression of the form $c ln n + o(ln n)$ for the diameter of a sparse random graph with a specified degree sequence. The result holds a.a.s., assuming certain convergence and supercriticality conditions are met. The classes of random graphs for which this result applies include the classical random graph model $G_{n,p}$ when $p=(1+b)/n$ for any positive constant $b$, and ‘power-law’ graphs when the giant component exists and the number of edges is linear in the number of vertices. The proof is constructive and yields a method for computing the constant $c$. Our methods also establish that almost all pairs of vertices that are connected by a path in such a random graph have almost the same shortest path distance.

This is joint work with Dan Fernholz.

SPEAKER: Warren D. Smith
TIME: Wednesday 12-1pm, Octobre 18, 2006
PLACE: NSH 1507

TITLE: Low-Tech Secure Voting Schemes

ABSTRACT:

You want to have secret ballot voting (nobody knows how anybody voted - prevents vote-buying and coercion). Even if the voter wants to reveal her vote, she should be unable. And you want to have verifiable voting - all should be confident the election results were correctly computed using only the correct votes (none altered, deleted, or added).

At first, it seemed impossible to achieve both desires. Later it was seen (via very complicated cryptographic multiparty protocols) how to do it. But last month Ron Rivest invented a blitheringly simple way to do it without any cryptography or computers at all. Then I fixed the flaws in Rivest’s schemes.

Speaker: John Hooker, Professor of Operations Research
Title: Duality in Optimization and Constraint Satisfaction
Date: Friday, October 13, 2006
Time: 1:30 to 3:00 pm
Place: Room 384 Posner Hall

In this talk I attempt to unify the various duals that have been developed in optimization and constraint satisfaction. I show that they can be classified as inference duals, relaxation duals, or both. They include linear programming, surrogate, Lagrangean, superadditive, and constraint duals, as well as duals defined by resolution and filtering algorithms. Inference duals give rise to nogood-based search methods (such as Benders decomposition) and sensitivity analysis, while relaxation duals provide bounds. This analysis shows that duals may be more closely related than they appear, as are surrogate and Lagrangean duals. It also reveals common structure between solution methods, such as Benders decomposition and Davis-Putnam-Loveland methods with clause learning. It provides a framework for devising new duals and solution methods.

Friday, October 13th, 2006
WEH 7220, 3:30pm

Dispersion of Mass and the Complexity of Randomized Algorithms

Santosh Vempala
Faculty, Georgia Tech

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in $\R^n$ (the current best algorithm has complexity roughly $n^4$, conjectured to be $n^3$). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing.

This is joint work with Luis Rademacher.

SPEAKER: Viswanath Nagarajan
TIME: Wednesday 12-1pm, October 11, 2006
PLACE: NSH 1507
TITLE: Approximating the Dial-a-Ride problem

ABSTRACT:
The Dial-a-Ride problem is the following: given an $n$ vertex metric space, $m$ objects each specified by a source-destination pair, and a vehicle of capacity $k$, find the minimum length tour that moves each object from its source to destination such that there are at most $k$ objects in the vehicle at any point in the tour. The tour is said to be non-preemptive if each object, once picked up at its source is dropped only at its destination. The tour is said to be preemptive if each object can be dropped at intermediate vertices before being delivered at its destination.

We give an approximation algorithm for the non-preemptive Dial-a-Ride problem which achieves a guarantee of $\tilde{O}(min{\sqrt{n},\sqrt{k}})$. When the capacity $k$ is large, this is an improvement over the previous best approximation ratio of $\tilde{O}(\sqrt{k})$ due to Charikar & Raghavachari ‘98. We also show that there is always a tour that preempts each object at most once, and has a cost $O(\log2 n)$ times the optimal (many) preemptive tour.

Joint work with Anupam Gupta, M.T. Hajiaghayi, and R. Ravi.

SPEAKER: Mohit Singh
TIME: Thursday 4:30-5:30 pm, October 5, 2006
PLACE: PPB 300
TITLE: Improved approximation ratios for traveling salesperson tours and paths in directed graphs

ABSTRACT:

Traveling salesperson problem and its variants are one of the most widely studied combinatorial optimization problems. In this talk, we will concentrate on metric asymmetric traveling salesperson problems. In metric asymmetric traveling salesperson problems the input is a complete directed graph in which edge lengths satisfy the triangle inequality, and one is required to find a minimum length walk that visits all vertices. In ATSP the walk is required to be cyclic. In asymmetric traveling salesperson path problem (ATSPP) the walk is required to start at vertex s and to end at vertex t.

We show that the path version of the problem is almost as easy to solve as the cyclic version of the problem by showing that an \alpha-approximation for the cycle version leads to a (2+e)\alpha-approximation for the path version for every fixed e>0. We also improve on the previous best value of \alpha for the cycle version of the problem.

Joint Work with Uriel Feige.

SPEAKER: Daniel Golovin
TIME: Wednesday 12-1pm, October 4, 2006
PLACE: NSH 1507
TITLE: Quorum Placement in Networks: Minimizing Network Congestion

ABSTRACT:
Quorum systems provide a logical framework for maintaining data consistency under distributed accesses in a distributed system and have several applications. Implementing a quorum system requires one to map the quorum system onto the physical network that comprises the distributed system by assigning the logical elements of the quorum system to machines. The network traffic generated by the quorum system will depend heavily upon what mapping is used. We call the task of finding good mappings the quorum placement problem, and develop approximation algorithms for placing quorum systems to minimize the induced network congestion.

This is joint work with Anupam Gupta, Bruce Maggs, Florian Oprea, and Michael Reiter.