TBA

TBA

TBA

TBA

TBA

TBA

TBA

TBA

TBA

We consider the model of exploration of an undirected graph G by a single agent which is called the rotor-router mechanism or the Propp machine (among other names). Let p_v indicate the edge adjacent to a node v which the agent took on its last exit from v. The next time when the agent enters node v, first the "rotor" at node v advances pointer p_v to the next edge in a fixed cyclic order of the edges adjacent to v. Then the agent is directed onto edge p_v to move to the next node. It was shown before that after initial O(mD) steps, the agent periodically follows one established Eulerian cycle (that is, in each period of 2m consecutive steps the agent will traverse each edge exactly twice, once in each direction). The parameters m and D are the number of edges in G and the diameter of G. We investigate robustness of such exploration in presence of faults in the pointers p_v or dynamic changes in the graph. In particular, we show that after the exploration establishes an Eulerian cycle, if at some step k edges are added to the graph, then a new Eulerian cycle is established within O(km) steps. We show similar results for the case when the values of k pointers p_v are arbitrarily changed and when an arbitrary edge is deleted from the graph. Our proofs are based on the relation between Eulerian cycles and spanning trees known as the "BEST" Theorem (after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte).

This is joint work with: E. Bampas, L. Gasieniec, R. Klasing and A. Kosowski.

For a graph G, a signed domination function of G is a two-colouring of the vertices of G with colours +1 and -1 such that the closed neighbourhood of every vertex contains more +1's than -1's. This concept is closely related to combinatorial discrepancy theory as shown by Fueredi and Mubayi [J. Combin. Theory, Ser. B76 (1999) 223-239]. The signed domination number of G is the minimum of the sum of colours for all vertices, taken over all signed domination functions of G. In this talk, we will discuss new upper and lower bounds for the signed domination number. These new bounds improve a number of known results.

In this presentation we give an overview of applications of, and algorithms for, multi-index assignment problems (MIAPs). MIAPs, and relatives of it, have a long history both in applications as well as in theoretical results, starting at least in the 1950's. In particular, we focus here on the complexity and approximability of special cases of MIAPs.

A prominent example of a MIAP is the so-called axial three index assignment problem (3AP) which has many applications in a variety of domains including clustering. A description of 3AP is as follows. Given are three n-sets R, G, and B. For each triple in R X G X B a cost-coefficient c(i,j,k) is given. The problem is to find n triples such that each element is in exactly one triple, while minimizing total cost. We show positive and negative results for finding an optimal solution to this problem that depend upon different ways of how the costs c(i,j,k) are specified.

We consider approximating the minmax value of a multiplayer game in strategic form. Tightening recent bounds by Borgs et al., we observe that approximating the value with a precision of "ε log n" digits (for any constant ε > 0) is NP-hard, where n is the size of the game. On the other hand, approximating the value with a precision of c log log n digits (for any constant c ≤ 1) can be done in quasi-polynomial time.We consider the parameterized complexity of the problem, with the parameter being the number of pure strategies k of the player for which the minmax value is computed. We show that if there are three players, k = 2 and there are only two possible rational payoffs, the minmax value is a rational number and can be computed exactly in linear time. In the general case, we show that the value can be approximated with any polynomial number of digits of accuracy in time n^O(k). On the other hand, we show that minmax value approximation is W[1]-hard and hence not likely to be fixed parameter tractable. Concretely, we show that if k-CLIQUE requires time n^Ω(k) then so does minmax value computation.

This is joint work with Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, and Peter Bro Miltersen.

We consider the profit maximizing pricing problem for single-minded buyers. Here, we wish to sell a set of m items to n buyers, each of whom is interested in buying a single set of items. Our goal is to set prices for the items such that the profit obtained by selling the items to the buyers who can afford them is maximized. We also assume in our case, that we have arbitrarily many copies of each item to sell.

When the underlying set of items are edges of a graph, and the buyers are interested in buying specific paths, this is called the tollbooth problem. We consider the special case where the graph is a tree, or a path. In the case of a tree, the problem is already known to be APX-hard. We give an O(log n) approximation algorithm. When the graph is a path, the problem is called the highway problem. In this case, we show that the problem is strongly NP-hard, complementing an earlier QPTAS. We also consider the discount model where some items are allowed to have negative prices, and show that a very simple case is already APX-hard.

This is joint work with K. Elbassioni, S. Ray and R. Sitters.

Randomized mechanisms, which map a set of bids to a probability distribution over outcomes rather than a single outcome, are an important but ill-understood area of computational mechanism design. We investigate the role of randomized outcomes ("lotteries") in the context of a fundamental and archetypical multi-parameter mechanism design problem: selling heterogeneous items to unit-demand bidders. To what extent can a seller improve her revenue by pricing lotteries rather than items, and does this modification of the problem affect its computational tractability? We show that the answers to these questions hinge on the exact model of consumer behavior we deploy and present several tight bounds on the increase in revenue obtainable via randomization and the computational complexity of revenue maximization in these different models. This is joint work with Shuchi Chawla, Bobby Kleinberg, and Matt Weinberg.

Multiobjective Optimization has many applications in such fields as the internet, finance, biomedicine, management science, game theory and engineering. However, solving MO problems is not an easy task. Searching for all Pareto optimal solutions is expensive and time consuming process because there are usually exponentially large (or infinite) Pareto optimal solutions. Even for the simplest problem determining whether a point belongs to the Pareto curve is NP-hard.

In this talk we are going to discuss some continuous and combinatorial multiobjective optimization problems and their applications in management, finance and military. Exact and heuristic techniques for solving these problems are presented.

We also consider nondifferentiable multiobjective programming problems involving generalized convex functions and present optimality conditions and duality results for the problems.

For a fixed graph H, let ex(n,H) be the maximum number of edges of an n-vertex graph not containing a copy of H. The asymptotic estimation of ex(n,H) is a central problem to extremal graph theory, and for the case when H is non-bipartite the answer is given by the Erdős-Stone theorem. However despite considerable effort, the problem is still open when H is bipartite.

A related topic is the study of ex(n, l × H), the maximum number of edges of an n-vertex graph not containing l-vertex disjoint copies of a graph H. Insofar, this function has been investigated only for some special values of H. In this talk I shall first discuss known results about ex(n, l × H). Then for a given α ∈ (0,1) I shall determine the asymptotic behaviour of ex(n, αn × H), in the particular case when H is a bipartite graph. The proof is an application of the regularity lemma.

This is joint work with Jan Hladký.

We introduce a "Pólya choice" urn model combining elements of the well known "power of two choices" model and the "rich get richer" model. From a set of k urns, randomly choose c distinct urns with probability proportional to the product of a power γ > 0 of their occupancies, and increment one with the smallest occupancy. The model has an interesting phase transition. If γ ≤ 1, the urn occupancies are asymptotically equal with probability 1. For γ > 1, this still occurs with positive probability, but there is also positive probability that some urns get only finitely many balls while others get infinitely many.

Fix a positive integer k, and consider the class of all graphs which do not have k+1 vertex-disjoint cycles. A classical result of Erdős and Pósa says that each such graph G contains a blocker of size at most f(k). Here a blocker is a set B of vertices such that G-B has no cycles. We give a minor extension of this result, and deduce that almost all such labelled graphs on vertex set 1,...,n have a blocker of size k. This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph R_n taken uniformly at random from the class: we see for example that the probability that R_n is connected tends to a specified limit as n → ∞. There are corresponding results when we consider unlabelled graphs with few disjoint cycles. We consider also variants of the problem involving for example disjoint long cycles. This is joint work with Valentas Kurauskas and Mihyun Kang.

Gupta et al. introduced a very general multi-commodity flow problem in which the cost of a given flow solution on a graph G=(V,E) is calculated by first computing the link loads via a load-function l, that describes the load of a link as a function of the flow traversing the link, and then aggregating the individual link loads into a single number via an aggregation function.

We show the existence of an oblivious routing scheme with competitive ratio O(log n) and a lower bound of Ω(log n/loglog n) for this model when the aggregation function agg is an L_p-norm.

Our results can also be viewed as a generalization of the work on approximating metrics by a distribution over dominating tree metrics and the work on minimum congestion oblivious. We provide a convex combination of trees such that routing according to the tree distribution approximately minimizes the L_p-norm of the link loads. The embedding techniques of Bartal and Fakcharoenphol et al. can be viewed as solving this problem in the L₁-norm while the result on congestion minmizing oblivious routing solves it for L_∞. We give a single proof that shows the existence of a good tree-based oblivious routing for any L_p-norm.

We present two algorithms for counting the number of colourings of sparse random graph. Our approach is based on correlation decay techniques originating in statistical physics.

The first algorithm is based on establishing correlation decay properties of Gibbs distribution which are related to Dobrushin's condition for uniqueness of Gibbs measure on infinite trees. More specifically, we impose boundary conditions to a specific set of vertices of the graph and we show that the effect of this boundary decays as we move away.

For the second algorithm we set a new context for exploiting correlation decay properties. Instead of imposing boundary conditions -fixing the colouring of vertices-, we impose a specific graph structure to some region (i.e. delete edges) and show that the effect of this change on the Gibbs distribution decays as we move away. It turns out that this approach designates a new set of spatial correlation decay conditions that can be used for counting algorithms.

In both cases the algorithms with high probability provide in polynomial time a (1/poly(n))-approximation of the logarithm of the number of k-colourings of the graph ("free energy") with k constant. The value of k depends on the expected degree of the graph. The second technique gives better results than the first one in terms of minimum number of colours needed.

Finally, the second algorithm can be applied to another class of graphs which we call locally a-dense graphs of bounded maximum degree Δ. A graph G = (V, E) in this family has following property: For all {u,v} in E the number of vertices which are adjacent to v but not adjacent to u are at most (1-a)Δ, where 0<a<1 is a parameter of the model. For a locally a-dense graph G with bounded Δ the algorithm computes in polynomial time a (1/polylogn)-approximation to the logarithm of the number of k-colourings, for k> (2-a)Δ. By restricting the treewidth of the neighbourhoods in G we can improve the approximation.

The analogue of hereditary properties of graphs for permutations are known as "permutation classes", defined as downsets in the "permutation containment" partial ordering. They are most commonly described as the collection "avoiding" some set of permutations, cf forbidden induced subgraphs for hereditary graph properties. Their origin lies with Knuth in the analysis of sorting machines, but in recent years have received a lot of attention in their own right. While much of the emphasis has been on exact and asymptotic enumeration of particular families of classes, an ongoing study of the general structure of permutations is yielding remarkable results which typically also have significant enumerative consequences.

In this talk I will describe a number of these structural results, with a particular emphasis on the question of partial well-order -- i.e. the existence or otherwise of infinite antichains in any given permutation class. The building blocks of all permutations are "simple permutations", and we will see how these on their own contribute to the partial well-order problem. We will see how "grid classes", a seemingly independent concept used to express large complicated classes in terms of smaller easily-described ones, also have significant consequences in determining the existence of infinite antichains. Finally, I will present recent and ongoing work in combining these two concepts, both to describe a general method of constructing antichains and to prove when certain classes are partially well-ordered.

We consider the problem of maximizing the probability of hitting a strategically chosen hidden virtual network by placing a wiretap on a single link of a communication network. This can be seen as a two-player win-lose (zero-sum) game that we call the wiretap game. The value of this game is the greatest probability that the wiretapper can secure for hitting the virtual network. The value is shown to be equal the reciprocal of the strength of the underlying graph. We provide a polynomial time algorithm that finds linear-sized description of the maxmin-polytope, and a characterization of its extreme points. It also provides a succint representation of all equilibrium strategies of the wiretapper that minimize the number of pure best responses of the hider. Among these strategies, we efficiently compute the unique strategy that maximizes the least punishment that the hider incurs for playing a pure strategy that is not a best response.

Finally, we show that this unique strategy is the nucleolus of the recently studied simple cooperative spanning connectivity game.

Joint work with: Haris Aziz, Mike Paterson and Rahul Savani.

A reset word for a finite deterministic automaton is a word which takes the machine to a fixed state from any starting state. Investigations into an old conjecture on the length of a reset word (if one exists) has led to new properties of permutation groups lying between primitivity and 2-transitivity, and a surprising fact about the representation of transformation monoids as endomorphism monoids of graphs. In the talk I will discuss some of these things and their connections.

Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling - GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g., 50% throughput in switches). However, it was recently shown that in networks in which the local pooling conditions are satised, GMS achieves 100% throughput. A graph G = (V,E) is said to satisfy the local pooling conditions if for every induced subgraph H of G there exists a function g : V(H) → [0, 1] such that Σ_v∈S g(v)=1 for every maximal stable set S in H.

We first analyze line graphs and give a characterization of line graphs that satisfy local pooling. Line graphs are of interest since they correspond to the interference graphs of wireless networks under primary interference constraints. Finally we consider claw-free graphs and give a characterization of claw-free graphs that satisfy local pooling. This is joint work with Berk Birand, Maria Chudnovsky, Paul Seymour, Gil Zussman and Yori Zwols.

Online algorithms studied in theory are characterized by the fact that they get to know the input sequence incrementally, one job at a time, and a new job is not issued until the previous one is processed by the algorithm. In real applications, jobs can usually be delayed for a short amount of time. As a consequence, the input sequence of jobs can be reordered in a limited fashion to optimize the performance. In this talk, the power and limits of this online reodering paradigm is discussed for several problems.

Let X be the number of triangles in a random graph G(n,1/2). Loebl, Matousek and Pangrac showed that X is close to uniformly distributed modulo q when q=O(log n) is prime. We extend this result considerably, and discuss further implications of our methods for the distribution of X. This is joint work with Atsushi Tateno (Oxford).

If A is a set of n positive integers, how small can the set {a/(a,b) : a,b ∈ A} be? Here as usual (a,b) denotes the HCF of a and b. This elegant question was raised by Granville and Roesler, who also reformulated it in the following way: given a set A of n points in Z^d, how small can (A-A)⁺, the projection of the difference set of A onto the positive orthant, be?

Freiman and Lev gave an example to show that (in any dimension) the size can be as small as n^2/3 (up to a constant factor). Granville and Roesler proved that in two dimensions this bound is correct, i.e. that the size is always at least n^2/3, and asked if this held in any dimension. Holzman, Lev and Pinchasi showed that in three dimensions the size is at least n^3/5, and that in four dimensions the size is at least n^6/11 (up to a logarithmic factor), and they also asked if the correct exponent is always 2/3.

After some background material, the talk will focus on recent developments, including a negative answer to the n^2/3 question.

Joint work with Béla Bollobás.

Circulant graphs form an important and very well-studied class of graph. They are Cayley graphs of cyclic groups and have been proposed for numerous applications such as local area computer networks, large area communication networks, parallel processing architectures, distributed computing, and VLSI design. Their connectivity and diameter, cycle and path structure, and further graph-theoretical properties have been studied in great detail. Polynomial time algorithms for isomorphism testing and recognition of circulant graphs have been long-standing open problems which were completely solved only recently.

Our goal here is to extend some of the fundamental results concerning circulant graphs to the similarly defined yet more general class of distance graphs. We prove that the class of circulant graphs coincides with the class of regular distance graphs. We study the existence of long cycles and paths in distance graphs and analyse the computational complexity of problems related to their connectivity and diameter.

Joint work with L. Draque Penso und J.L. Szwarcfiter.

A graph has low discrepancy if its global edge distribution is "close" to that of a random graph with the same overall density. It has been known that low discrepancy is related to the spectra of various matrix representations of the graph such as the adjacency matrix or the normalized Laplacian. More precisely, a large spectral gap implies low discrepancy. The topic of this talk is the converse implication: does low discrepancy imply a large spectral gap? The proofs are based on the Grothendieck inequality and the duality theorem for semidefinite programs.

We introduce the study of social context games. A social context game is defined by an underlying game in strategic form, and a social context consisting of an undirected graph of neighborhood among players and aggregation functions. The players and strategies in a social context game are as in the underlying game, while the players' utilities in a social context game are computed from their payoffs in the underlying game based on the graph of neighborhood and the aggregation functions. Examples of social context games are ranking games and coalitional con- gestion games. A signifcant challenge is the study of how various social contexts affect various properties of the game. In this work we consider resource selection games as the underlying games, and four basic social contexts. An important property of resource selection games is the existence of pure strategy equilibrium. We study the existence of pure strategy Nash equilibrium in the corresponding social context games. We also show that the social context games possessing pure strategy Nash equilibria are not potential games, and therefore are distinguished from congestion games.

Joint work with Itai Ashlagi and Moshe Tennenholtz.

The problem of reaching consensus in a distributed environment is one of the fundamental topics in the area of distributed computing, systems and architectures. It was formally abstracted in late 70's by Lamport, Pease and Shostak. The early work on this problem focused on feasibility, i.e., what are the conditions under which the consensus can be solved. Later, the complexity of solutions has become of great importance. In this talk I'll introduce the problem, present selected classic algorithms and lower bounds, and conclude with my recent work on time and communication complexity of consensus in a message-passing system.

For a connected graph G = (V, E), a subset U of vertices is called a k-cut if U disconnects G, and the subgraph induced by U contains exactly k≥1 components. More specifically, a k-cut U is called a (k, l)-cut if V \ U induces a subgraph with exactly l≥2 components. We study two decision problems, called k-CUT and (k, l)-CUT, which determine whether a graph G has a k-cut or (k, l)-cut, respectively. By pinpointing a close relationship to graph contractibility problems we first show that (k, l)-CUT is in P for k=1 and any fixed constant l≥2, while the problem is NP-complete for any fixed pair k, l≥2. We then prove that k-CUT is in P for k=1, and NP-complete for any fixed k≥2. On the other hand, we present an FPT algorithm that solves (k, l)-CUT on planar graphs when parameterized by k + l. By modifying this algorithm we can also show that k-CUT is in FPT (with parameter k) and DISCONNECTED CUT is solvable in polynomial time for planar graphs. The latter problem asks if a graph has a k-cut for some k≥2.

Joint work with Takehiro Ito and Marcin Kamiński.

This is a survey talk about counting/sampling contingency tables and cell-bounded contingency tables. In the cell-bounded contingency tables problem, we are given a list of positive integer row sums r=(r₁,...,r_m), a list of positive integer column sums c=(c₁,...,c_n), and a non-negative integer bound b_ij, for every 1 ≤ i ≤ m, 1 ≤ j ≤ n.

The problem is to count/sample the set of all m-by-n tables X ∈ Z^mn of non-negative integers which satisfy the given row and column sums, and for which 0 ≤ X_ij ≤ b_ij for all i, j. I will outline a complicated (reduction to volume estimation) algorithm for approximately counting these tables in polynomial time, when the number of row is constant. I also hope to outline a more recent, 'cute' dynamic programming algorithm for exactly the same case of constantly-many rows. The case for general m is still open.

Joint with Martin Dyer and Dana Randall

The Ramsey number R(l x H) is the smallest integer m such that any l-colouring of the edges of K_m induces a monochromatic copy of H. We prove that R(4 x P_n)=2.5n+o(n). Luczak proposed a way how to attack the problem of finding a long monochromatic path in a coloured graph G: one should search for a large monochromatic connected matching in the reduced graph of G. Here we propose a modification of Luczak's technique: we find a large monochromatic connected fractional matching. This relaxation allows us to use LP duality and reduces the question to a vertex-cover problem.

This is a joint work with Jan Hladký and Daniel Král'.

Random graphs G on n vertices and with edge probability at least c(log n/n)^(1/Δ) are robust in the following sense: Let H be an arbitrary planar bipartite graph on (1-ε)n vertices with maximum degree Δ. Now you, the adversary, may arbitrarily delete edges in G such that no vertex looses more than a third of its neighbours. However, you will not be able to destroy all copies of H.

This result is obtained (joint work with Yoshiharu Kohayakawa and Anusch Taraz) via a sparse version of the regularity lemma. In the talk I will provide some background concerning related results, introduce sparse regularity, and outline how this can be used to prove theorems such as the one above.

An important instance of the Caccetta-Häggkvist conjecture asserts that an n-vertex digraph with minimum outdegree at least n/3 contains a directed triangle. Improving on a previous bound of 0.3532n due to Hamburger, Haxell, and Kostochka we prove that a digraph with minimum outdegree at least 0.3465n contains a directed triangle. The proof is an application of a recent combinatorial calculus developed by Razborov. This calculus enables one to formalize common techniques in the area (such as induction or the Cauchy-Schwartz inequality). In the talk I shall describe Razborov's method in general, and its application to the setting of the Cacceta-Häggvist Conjecture.

This is joint work with Dan Král' and Sergey Norin.

Szemerédi's regularity lemma is a powerful tool in extremal graph theory, which had have many applications. In this talk we present several variants of Szemerédi's original lemma (due to several researchers including Frieze and Kannan, Alon et al., and Lovász and Szegedy) and discuss their relation to each other.

We consider the problem of periodic graph traversal in which a mobile entity with constant memory has to visit all n nodes of an arbitrary undirected graph G in a periodic manner. Graphs are supposed to be anonymous, that is, nodes are unlabeled. However, while visiting a node, the robot has to distinguish between edges incident to it. For each node v the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in minimization of the length of the exploration period.

This problem is unsolvable if the local port numbers are set arbitrarily (shown by Budach in 1978). However, surprisingly small periods can be achieved when carefully assigning the local port numbers. Dobrev, Jansson, Sadakane, and Sung described an algorithm for assigning port numbers, and an oblivious agent (i.e. an agent with no memory) using it, such that the agent explores all graphs with n vertices within period 10n. Providing the agent with a constant number of memory bits, the optimal length of the period was later proved to be no more than 3.75n (using a different assignment of the port numbers). Following on from this, a period of length at most (4 1/3)n was shown for oblivious agents, and a period of length at most 3.5n for agents with constant memory.

This talk describes results in two papers by the speaker, which are joint work with several other authors.

I will discuss the problem of cutting the (discrete or continuous) d-dimensional torus economically, so that no nontrivial cycle remains. This improves, simplifies and/or unifies results of Bollobás, Kindler, Leader and O'Donnell, of Raz and of Kindler, O'Donnell, Rao and Wigderson. More formal, detailed abstract(s) appear in http://www.math.tau.ac.il/~nogaa/PDFS/torus3.pdf and in http://www.math.tau.ac.il/~nogaa/PDFS/torusone.pdf.

Joint work with Bo'az Klartag.

In the interference scheduling problem, one is given a set of n communication requests described by pairs of points from a metric space. The points correspond to devices in a wireless network. In the directed version of the problem, each pair of points consists of a dedicated sending and a dedicated receiving device. In the bidirectional version the devices within a pair shall be able to exchange signals in both directions. In both versions, each pair must be assigned a power level and a color such that the pairs in each color class can communicate simultaneously at the specified power levels. The feasibility of simultaneous communication within a color class is defined in terms of the Signal to Interference Plus Noise Ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. This is commonly referred to as the "physical model" and is the established way of modelling interference in the engineering community. The objective is to minimize the number of colors as this corresponds to the time needed to schedule all requests.

We study oblivious power assignments in which the power value of a pair only depends on the distance between the points of this pair. We prove that oblivious power assignments cannot yield approximation ratios better than Ω(n) for the directed version of the problem, which is the worst possible performance guarantee as there is a straightforward algorithm that achieves an O(n)-approximation. For the bidirectional version, however, we can show the existence of a universally good oblivious power assignment: For any set of n bidirectional communication requests, the so-called "square root assignment" admits a coloring with at most polylog(n) times the minimal number of colors. The proof for the existence of this coloring is non-constructive. We complement it by an approximation algorithm for the coloring problem under the square root assignment. This way, we obtain the first polynomial time algorithm with approximation ratio polylog(n) for interference scheduling in the physical model.

This is joint work with Alexander Fanghänel, Thomas Keßelheim and Harald Räcke

The Traveling Salesman Problem (TSP) is one of the most famous NP-hard problems. So, much works have been done to study polynomially solvable cases, that is, to find good conditions for distances between cities such that an optimal tour can be found in polynomial time. These good conditions give some restriction on the optimal solution, for example, Monge property. For a given complete weighted digraph G, a vertex x of G, and a positive integer k, the Vehicle Routing Problem (VRP) is to find a minimum weight connected subgraph F of G such that F is a union of k cycles sharing only the vertex x. In this talk, we apply good conditions for the TSP to the VRP. We will show that if a given weighted digraph satisfies several conditions, which is known for the TSP, then an optimal solution of the VRP can also be computed in polynomial time.

Consider a firm, called the buyer, that satisfies its demand over a T-period time horizon by assigning the demand vector to a supplier via a procurement (reverse) auction; call this the Standard auction. The firm is considering an alternative procedure in which it will allow bids on one or more periods; in this auction, there can be more than one winner covering the demand vector; call this the Multiple Winner auction. Choosing the Multiple Winner auction over the Standard auction will tend to: (1) allow each supplier the option of supplying demand for any subset of periods of the T-period horizon; (2) increase competition among the suppliers, and (3) allow the buyer to combine bids from different suppliers in order to lower his purchase cost. All three effects might lead one to expect that the buyer's cost will always be lower in the Multiple Winner auction than in the Standard auction. To the contrary, there are cases in which the buyer will have a higher cost in the Multiple Winner auction. We provide a bound on how much greater the buyer's cost can be and show that this bound is sharp.

The identification of functional modules in protein-protein interaction networks is an important topic in systems biology. These modules might help, for example, to better understand the underlying biological mechanisms of different tumor subtypes. In this talk, I report on results of a cooperation with statisticians and medical researchers from the University of Würzburg. In particular, I will present an exact integer linear programming solution for this problem, which is based on its connection to the well-known prize-collecting Steiner tree problem from Operations Research.

I will decribe a family of finitely presented, but infinite-state, stochastic models that arise by adding a natural recursion feature to Markov Chains, Markov Decision Processes, and Stochastic Games.

These models subsume a number of classic and heavily studied purely stochastic models, including (multi-type) branching processes, (quasi-)-birth-death processes, stochastic context-free grammars, and others. They also provide a natural abstract model of probabilistic procedural programs with recursion.

The theory behind the algorithmic analysis of these models, developed over the past few years, has turned out to be very rich, with connections to a number of areas of research. I will survey just a few highlights from this work. There remain many open questions about the computational complexity of basic analysis problems. I will highlight a few such open problems.

(Based on joint work with Mihalis Yannakakis, Columbia University)

For a given undirected graph G, the Network Loading Problem (NLP) deals with the design of a least cost network by allocating discrete units of facilities with different capacities on the links of G so as to support expected pairwise demands between some endpoints of G. In this work, we relax the assumption of known demands and study robust NLP with polyhedral demands to obtain designs flexible enough to support changing communication patterns in the least costly manner. More precisely, we seek for a final design that remains operational for any feasible demand realization in a prescribed polyhedral set.

Firstly, we give a compact multi-commodity formulation of the problem for which we prove a nice decomposition property obtained from projecting out the flow variables. This simplifies the resulting polyhedral analysis and computations considerably by doing away with metric inequalities, an attendant feature of the most successful algorithms on the Network Loading Problem. Then, we focus on a specific choice of the uncertainty description, called the "hose model", which specifies aggregate traffic upper bounds for selected endpoints of the network. We study the polyhedral aspects of the Network Loading Problem under hose demand uncertainty and present valid inequalities for robust NLP with arbitrary number of facilities and arbitrary capacity structures as the second main contribution of the present work. Finally, we develop an efficient Branch-and-Cut algorithm supported by a simple but effective heuristic for generating upper bounds and use it to solve several well-known network design instances.

We study the design of optimal mechanisms in a setting where job-agents compete for being processed by a service provider that can handle one job at a time. Each job has a processing time and incurs a waiting cost. Jobs need to be compensated for waiting. We consider two models, one where only the waiting costs of jobs are private information (1-d), and another where both waiting costs and processing times are private (2-d). An optimal mechanism minimizes the total expected expenses to compensate all jobs, while it has to be Bayes-Nash incentive compatible. We derive closed formulae for the optimal mechanism in the 1-d case and show that it is efficient for symmetric jobs. For non-symmetric jobs, we show that efficient mechanisms perform arbitrarily bad. For the 2-d case, we prove that the optimal mechanism in general does not even satisfy IIA, the "independent of irrelevant alternatives" condition. We also show that the optimal mechanism is not even efficient for symmetric agents in the 2-d case.

Joined work with Birgit Heydenreich, Debasis Mishra and Marc Uetz.

Communication networks (such as the Internet or BT's network) are held together by a wide variety of interacting network control systems. Examples include routing protocols, which determine the paths used by different sessions, and flow control mechanisms, which determine the rate at which different sessions can send traffic. Many of these control processes can be viewed as distributed algorithms that aim to solve a network-wide optimisation problem.

I will present a mathematical framework, based on Lagrangian decomposition, for the design and analysis of such algorithms. As an illustration, I will discuss how this framework has been used in BT Innovate to develop a new resource control system which integrates multi-path routing and admission control decisions.

The notion of convexity plays an important role in convergence proofs for our algorithms. We can design a control system with stability guarantees as long as the system's target behaviour can be captured as the solution to a convex optimisation problem. Unfortunately, many standard network design problems are formulated as integer programming problems and therefore inherently non-convex. I will discuss some of the implications of this non-convexity and identify some related research challenges.

We discuss bounds on extremal sets for problems like those below:

1. What is the largest subset of (ℤ/nℤ)^r that does not contain an arithmetic progression of length k?
2. What is the largest subset/(multiset) of (ℤ/nℤ)^r that does not contain n elements that sum to 0?
3. What is the largest subset of [1,...,n]^r that does not contain a solution of x+y=z (i.e., which is a sum free set)?
4. Colour the elements of [1,...,n]^r red and blue. How many monochromatic Schur triples are there?

A matrix is called Monge, if its density matrix is nonnegative. Monge matrices play an important role in optimisation. Distance multiplication (also known as min-plus or tropical multiplication) of two Monge matrices of size n can be performed in time O(n²). Motivated by applications to string comparison, we introduced in a previous work the following subclass of Monge matrices. A matrix is called unit-Monge, if its density matrix is a permutation matrix; we further restrict our attention to a subclass that we call simple unit-Monge matrices. Our previous algorithm for distance multiplication of simple unit-Monge matrices runs in time O(n^3/2). Landau conjectured in 2006 that this problem can be solved in linear time. In this work, we give an algorithm running in time O(n log⁴ n), thus approaching Landau's conjecture within a polylogarithmic factor. The new algorithm implies immediate improvements in running time for a number of string comparison and graph algorithms: semi-local longest common subsequences between permutations; longest increasing subsequence in a cyclic permutation; longest pattern-avoiding subsequence in a permutation; longest piecewise monotone subsequence; maximum clique in a circle graph; subsequence recognition in a grammar-compressed string; sparse spliced alignment of genome strings.

The notion of a boundary graph property is a relaxation of that of a minimal property. Several fundamental results in graph theory have been obtained in terms of identifying minimal properties. For instance, Robertson and Seymour showed that there is a unique minimal minor-closed property with unbounded tree-width (the planar graphs), while Balogh, Bollobás and Weinreich identified nine minimal hereditary properties with the factorial speed of growth. However, there are situations where the notion of minimal property is not applicable. A typical example of this type is given by graphs of large girth. It is known that for each particular value of k, the graphs of girth at least k have unbounded tree-, clique- or rank-width, their speed of growth is superfactorial and many algorithmic problems remain NP-hard for these graphs, while the “limit” property of this sequence (i.e., acyclic graphs) has bounded tree-, clique- and rank-width, its speed of growth is factorial, and most of algorithmic problems can be solved in polynomial time in this class. The notion of boundary properties of graphs allows to overcome this difficulty. In this talk we survey some available results on this topic and identify the first boundary class for the Hamiltonian cycle problem.

Joint work with N. Korpelainen and A. Tiskin

Turán's theorem shows that every n-vertex graph with minimum degree n/2 contains a triangle. A proof (for large n) of the Pósa conjecture shows that every n-vertex graph with minimum degree 2n/3 contains the square of a Hamilton cycle; this is a cyclic ordering of the vertices in which every three consecutive vertices forms a triangle. We fill in the gap between these theorems, giving the correct relationship (for large n) between the minimum degree of an n-vertex graph and the lengths of squared cycles which are forced to exist in the graph. We also discuss generalisations of all three theorems to other graphs with chromatic number three, and offer some conjectures on higher chromatic numbers. This is joint work with Julia Böttcher and Jan Hladký.

We discuss recent work on graphical degree sequences, i.e., sequences of integers that correspond to the degrees of the vertices of a graph. Historically, such degree sequences have been used to provide sufficient conditions for graphs to have a certain property, such as being k-connected or hamiltonian. For hamiltonicity, this research has culminated in a beautiful theorem due to Chvátal (1972). This theorem gives a sufficient condition for a graphical degree sequence to be forcibly hamiltonian, i.e., such that every graph with this degree sequence is hamiltonian. Moreover, the theorem is the strongest of an entire class of theorems in the following sense: if the theorem does not guarantee that a sequence π is forcibly hamiltonian, then there exists a nonhamiltonian graph with a degree sequence that majorizes π. Very recently, Kriesell solved an open problem due to Bauer et al. by establishing similar conditions for k-edge connectivity for any fixed k. We will introduce a general framework for such conditions and discuss recent progress and open problems on similar sufficient conditions for a variety of graph properties. This is based on joint work with Bauer, van den Heuvel, Kahl, and Schmeichel.

Min-Max function appear in various contexts in mathematics, computer science, and engineering. For instance, in the analysis of zero-sum two-player games on graphs, Min-Max functions arise as dynamic programming operators. They also play a role in the performance analysis of certain discrete event systems, which are used to model computer networks and manufacturing systems. In each of these fields it is important to understand the long-term iterative behaviour of Min-Max functions. In this talk I will explain how this problem is related to certain combinatorial geometric problems and discuss some results and a conjecture.

We consider finite and simple graphs. We say that a graph G contains a graph F, if F is isomorphic to an induced subgraph of G. A graph G is F-free if it does not contain F. Let ℱ be a (possibly infinite) family of graphs. A graph G is ℱ-free if it is F-free, for every F ∈ ℱ.

Many interesting classes of graphs can be characterized as being ℱ-free for some family ℱ. The most famous such example is the class of perfect graphs. A graph G is perfect if for every induced subgraph H of G, χ(H) = ω(H), where χ(H) denotes the chromatic number of H and ω(H) denotes the size of a largest clique in H. The famous Strong Perfect Graph Theorem states that a graph is perfect if and only if it does not contain an odd hole nor an odd antihole (where a hole is a chordless cycle of length at least four).

In the last 15 years a number of other classes of graphs defined by excluding a family of induced subgraphs have been studied, perhaps originally motivated by the study of perfect graphs. The kinds of questions this line of research was focused on were whether excluding induced subgraphs affects the global structure of the particular class in a way that can be exploited for putting bounds on parameters such as χ and ω, constructing optimization algorithms (problems such as finding the size of a largest clique or a minimum coloring), recognition algorithms and explicit construction of all graphs belonging to the particular class. A number of these questions were answered by obtaining a structural characterization of a class through their decomposition (as was the case with the proof of the Strong Perfect Graph Theorem).

In this talk we survey some of the most recent uses of the decomposition theory in the study of classes of even-hole-free graphs. Even-hole-free graphs are related to β-perfect graphs in a similar way in which odd-hole-free graphs are related to perfect graphs. β-Perfect graphs are a particular class of graphs that can be polynomially colored, by coloring greedily on a particular, easily constructable, ordering of vertices.

In a combinatorial exchange the goal is to find a feasible trade between potential buyers and sellers requesting and offering bundles of indivisible goods. We investigate the approximability of several optimization objectves in this setting and show that the problems of surplus and trade volume maximization are inapproximable even with free disposal and even if each agent's bundle is of size at most 3. In light of the negative results for surplus maximization we consider the complementary goal of social cost minimization and present tight approximation results for this scenario. Considering the more general supply chain problem, in which each agent can be a seller and buyer simultaneously, we prove that social cost minimization remains inapproximable even with bundles of size 3, yet becomes polynomial time solvable for agents trading bundles of size 1 or 2. This yields a complete characterization of the approximability of supply chain and combinatorial exchange problems based on the size of traded bundles. We finally briefly address the problem of exchanges in strategic settings.

This is joint work with Moshe Babaioff and Patrick Briest.

A uniform random intersection graph G(n,m,k) is a random graph constructed as follows. Label each of n nodes by a randomly chosen set of k distinct colours taken from some finite set of possible colours of size m. Nodes are joined by an edge if and only if some colour appears in both their labels. These graphs arise in the study of the security of wireless sensor networks. Such graphs arise in particular when modelling the network graph of the well known key predistribution technique due to Eschenauer and Gligor. In this talk we consider the threshold for connectivity and the appearance of a giant component of the graph G(n,m,k) when n → ∞ with k a function of n such that k≥2 and m=⌊n^α⌋ for some fixed positive real number α.

We discuss the following scheduling problem. A two-machine flowshop produces identical parts. Each of the parts is assumed to require a number of manufacturing operations, and the machines are assumed to be flexible enough to perform different operations. Due to economical or technological constraints, some specific operations are preassigned to one of the machines. The remaining operations, called flexible operations, can be performed on either one of the machines, so that the same flexible operation can be performed on different machines for different parts. The problem is to determine the assignment of the flexible operations to the machines for each part, with the objective of maximizing the throughput rate. We consider various cases depending on the number of parts to be produced and the capacity of the buffer between the machines. Along the way, we underline the fact that this problem belongs to the class of "high multiplicity scheduling problem": for this class of problems, the input data can be described in a very compact way due to the fact that the jobs fall into a small number of distinct job types, where all the jobs of a same type possess the same attribute values. High multiplicity scheduling problems have been recently investigated by several researchers who have observed that the complexity of such problems must be analyzed with special care.

Joint work with Hakan Gültekin.

In this talk I will consider computational problems that (A) can be solved in polynomial time for graphs of bounded treewidth and (B) where the order of the polynomial time bound is expected to depend on the treewidth of the instance. Among the considered problems are coloring problems, factor problems, orientation problems and satisfiability problems. I will present an algorithmic meta-theorem (an extension of Courcelle's Theorem) that provides a convenient way for establishing (A) for some of the considered problems and I will explain how concepts from parameterized complexity theory can be used to establish (B).

The connectivity of a communications network can sometimes be enhanced if the nodes are able, at some expense, to form links using an external network. Using graphs, the following is a possible way to model such situations.

Let G = (V,E) be a graph. A subset X of vertices in V may be chosen, the so-called external vertices. An internal path is a normal path in G; an external path is a pair of internal paths P₁ = v₁ · · · v_s, P₂ = w₁ · · · w_t in G such that v_s and w₁ are from the chosen set X of external vertices. (The idea is that v₁ can communicate with w_t along this path using an external link from v_s to w₁.) For digraphs we use similar vocabulary, but then using directed paths.

Next suppose a certain desired connectivity for the network is prescribed in terms of edge, vertex or arc-connectivity. Say that for a given k there need to be at least k edge- (or vertex- or arc-) disjoint paths (which can be internal or external) between any pair of vertices. What is the smallest set X of external vertices such that this can be achieved?

A related problem is the Source Location Problem : In this we need to find, given a graph or digraph and a required connectivity requirement, a subset S of the vertices such that from each vertex in the graph there are at least the required number of edge- (or vertex- or arc-) disjoint paths between any vertex and the set S. And again, the goal is to minimise the number of vertices in S.

It seems clear that the External Network Problem and the Source Location Problem are closely related. In this talk we discuss these relations, and also show some instances where the problems behave quite differently. Some recent results on the complexity of the different types of problems will be presented as well.

Joint work with Matthew Johnson (University of Durham)

We consider graphs whose edges are painted with two colours (some edges might get both colours), and ask, given a fixed such graph H, how large another such graph G can be if it has many vertices but doesn't contain a copy of H. The notion of largeness here is the total weight of G if red edges are given weight p and blue edges weight q, with p+q=1.

This question arises in the applications of Szemerédi's Regularity Lemma, in particular to Ramsey-type games, and to the study of edit distance and property testing.

We shall describe an approach to answering this question and to settling some outstanding issues concerning edit distance.

In this talk, we discuss scheduling and rescheduling problems with controllable job processing times. We start with the optimal allocation of a set of jobs on a set of parallel machines with given machining time capacities. Each job may have different processing times and different convex compression costs on different machines. We consider finding the optimal machine-job allocation and compression level decisions for the total cost. We propose a strengthened conic quadratic formulation for this problem. We provide theoretical and computational results that prove the quality of the proposed reformulation. We next shortly discuss match-up scheduling approach in the same scheduling environment with an initial schedule subject to a machine breakdown. We show how processing time controllability provides flexibility in rescheduling decisions.

We present an O(mn)-time algorithm for finding optimal strategies for discounted, infinite-horizon, Deterministic Markov Decision Processes (DMDP), where n is the number of vertices (or states) and m is the number of edges (or actions). This improves a recent O(mn^2)-time algorithm of Andersson and Vorobyov.

Joint work with Omid Madani and Mikkel Thorup.

Cliquewidth and NLC-width are two closely related parameters that measure the complexity of graphs. Both clique- and NLC-width are defined to be the minimum number of labels required to create a labelled graph by certain terms of operations. Many hard problems on graphs become solvable in polynomial time if the inputs are restricted to graphs of bounded clique- or NLC-width. Cliquewidth and NLC-width differ by a factor of at most two.

The relative counterparts of these parameters are defined to be the minimum number of labels necessary to create a graph while the tree-structure of the term is fixed. We show that the problems Relative Cliquewidth and Relative NLC-width differ significantly in computational complexity: the former is NP-complete, the latter is solvable in polynomial time. Additionally, our technique enables combinatorial characterisations of clique- and NLC-width that avoid the usual operations on labelled graphs.

The random geometric graph G(n,r) is constructed by picking n vertices X₁, · · · , X_n ∈ [0,1] ^d i.i.d. uniformly at random and adding an edge (X_i, X_j) if ‖X₁-X₂‖ < r. I will discuss the behaviour of the chromatic number of G(n,r) and some related random variables when n tends to infinity and r=r(n) is allowed to vary with n.

In this talk, we first give an overview of several exact approaches to graph colouring: known integer linear programming formulations, approaches based on SDP relaxations, as well as selected approaches not using any mathematical programming. Second, we introduce an integer programming formulation of graph colouring based on reversible clique partition or, seen another way, optimal polynomial-time transformation of graph colouring to multicolouring. The talk will be concluded by discussion of some specifics of applications of graph colouring in timetabling applications and utility of the proposed formulation in this context.

Why might markets tend toward and remain near equilibrium prices? In an effort to shed light on this question from an algorithmic perspective, we formalize the setting of Ongoing Markets, by contrast with the classic market scenario, which we term One-Time Markets. The Ongoing Market allows trade at non-equilibrium prices, and, as its name suggests, continues over time. As such, it appears to be a more plausible model of actual markets.

For both market settings, we define and analyze variants of a simple tatonnement algorithm that differs from previous algorithms that have been subject to asymptotic analysis in three significant respects: the price update for a good depends only on the price, demand, and supply for that good, and on no other information; the price update for each good occurs distributively and asynchronously; the algorithms work (and the analyses hold) from an arbitrary starting point. We show that this update rule leads to fast convergence toward equilibrium prices in a broad class of markets that satisfy the weak gross substitutes property.

Our analysis identifies three parameters characterizing the markets, which govern the rate of convergence of our protocols. These parameters are, broadly speaking:

• A bound on the fractional rate of change of demand for each good with respect to fractional changes in its price.
• A bound on the fractional rate of change of demand for each good with respect to fractional changes in wealth.
• The closeness of the market to a Fisher market (a market with buyers starting with money alone).

Joint work with Lisa Fleischer.

The multi-armed bandit paradigm has been studied extensively for over 50 years in Operations Research, Economics and Computer Science literature, modeling online decisions under uncertainty in a setting in which an agent simultaneously attempts to acquire new knowledge and to optimize its decisions based on the existing knowledge. In this talk I'll discuss several new results motivated by web applications, such as content matching (matching advertising to page contest and user's profile) and efficient web crawling.

We discuss control strategies for communication networks such as the Internet or wireless multihop networks, where the aim is to optimize network performance. We describe how welfare maximization can be used as a paradigm for network resource allocation, and can also be used to derive rate-control algorithms. We apply this to the case of multipath data transfers. We show that welfare maximization requires active balancing across paths by data sources, which can be done provided the underlying "network layer" is able to expose the marginal congestion cost of network paths to the "transport layer". When users are allowed to change the set of paths they use, we show that for large systems the path-set choices correspond to Nash equilibria, and give conditions under which the resultant Nash equilibria correspond to welfare maximising states. Moreover, simple path selection policies that shift to paths with higher net benefit can find these states.

We conclude by commenting on incentives, pricing and open problems.

Most data networks nowadays employ shortest path routing protocols to control the flow of data packets. With these protocols, all end-to-end traffic streams are routed along shortest paths with respect to some administrative routing weights. Dimensioning and routing planning are extremely difficult for such networks, because end-to-end routing paths cannot be configured individually but only jointly and indirectly via the routing weights. Additional difficulties arise if the communication demands must be sent unsplit through the network - a requirement that is often imposed to ensure tractability of end-to-end traffic flows and to prevent package reordering in practice. In this case, the lengths must be chosen such that the shortest paths are uniquely determined for all communication demands.

In this talk we consider the minimum congestion unsplittable shortest path routing problem MinConUSPR: Given a capacitated digraph D = (V, A) and traffic demands d_(s,t), (s, t) ∈ K ⊆ V², the task is to find routing weights λ_a ∈ ℤ₊, a ∈ A, such that the shortest (s, t)-path is unique for each (s, t) ∈ K and the maximum arc congestion (induced flow/capacity ratio) is minimal.

We discuss the approximability of this problem and the relation between the unsplittable shortest path routing paradigm and other routing schemes. We show that MinConUSPR is NP-hard to approximate within a factor of O(|V|^1-ε), but approximable within min(|A|, |K|) in general. For the special cases where the underlying graph is an undirected cycle or a bidirected ring, we present constant factor approximation algorithms. We also construct problem instances where the minimum congestion that can be obtained by unsplittable shortest path routing is a factor of Ω(|V|²) larger than that achievable by unsplittable flow routing or shortest multi-path routing, and a factor of Ω(|V|) larger than that achievable by unsplittable source-invariant routing.

I will consider waves in finite domains, for example water waves in a swimming pool. For such waves to exchange energy among different modes, these modes must be in resonance in both frequency and wavenumber, which leads to a set of nontrivial conditions/equations in integers. I will discuss some known results and open questions about the solutions of these Diophantine equations.

The observation that many natural and engineered networks exhibit scale-free degree distributions, and that such networks are particularly prone to epidemic outbreaks, raises questions about how best to control epidemic spread on such networks.

We will begin with some background on threshold phenomena for epidemics, describing how the minimum infection rate needed to sustain long-lived epidemics is related to the cure rate and the topology of the graph. In particular, we will see that, on scale-free networks, this minimum infection rate tends to zero as the network grows large. We will describe two ways of tackling this problem. One involves allocating curing or monitoring resources non-uniformly, favouring high-degree nodes. Another mechanism, called contact tracing, involves identifying and curing neighbours (or contacts) of infected nodes, and is used in practice. We will present some mathematical results for both these mechanisms.

Joint work with Borgs, Chayes, Saberi and Wilson.

The index of a Nash equilibrium is an integer that is related to notions of ``stability'' of the equilibrium, for example under dynamics that have equilibria as rest points. The index is a relatively complicated topological notion, essentially a geometric orientation of the equilibrium. We prove the following theorem, first conjectured by Hofbauer (2003), which characterizes the index in much simpler strategic terms:

Theorem. A generic bimatrix game has index +1 if and only if it can be made the unique equilibrium of an extended game with additional strategies of one player. In an mxn game, it suffices to add 3m strategies of the column player.

The main tool to prove this theorem is a novel geometric-combinatorial method that we call the "dual construction," which we think is of interest of its own. It allows to visualize all equilibria of an mxn game in a diagram of dimension m-1. For example, all equilibria of a 3xn game are visualized with a diagram (essentially, of suitably connected n+3 points) in the plane. This should provide new insights into the geometry of Nash equilibria.

Joint work with Arndt von Schemde.

In view of the apparent computational difficulty of computing a Nash equilibrium of a game, recent work has addressed the computation of "approximate Nash equilibrium". The standard criterion of "no incentive for any player to change his strategy" is here replaced by "small incentive for any player to change his strategy". The question is, how small an incentive can we aim for, before once again we have a computationally difficult problem? In this talk, I explain in detail what is meant by Nash equilibrium and approximate Nash equilibrium, and give an overview of some recent results.

In the classic minimum makespan scheduling problem, we are given an input sequence of jobs with processing times. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. We consider online scheduling algorithms without preemption. Much effort has been made to narrow the gap between upper and lower bounds on the competitive ratio of this problem.

A quite good and easy approximation can be achieved by sorting the jobs according to their size and than assigning them greedily to machines. However, the complete sorting of the input sequence contradicts the notion of an online algorithm. Therefore, we propose a new method to somewhat reorder the input in an online manner. Although our proofs are technically surprisingly simple, we give, for any number of identical machines, tight and significantly improved bounds on the competitive ratio for this new method.

This talk is based on joint work with Deniz Özmen and Matthias Westermann

We study the power of ascending auctions in a scenario in which a seller is selling a collection of identical items to anonymous unit-demand bidders. We show that even with full knowledge of the set of bidders' private valuations for the items, if the bidders are ex-ante identical, no ascending auction can extract more than a constant times the revenue of the best fixed price scheme.

This problem is equivalent to the problem of coming up with an optimal strategy for blowing up indistinguishable balloons with known capacities in order to maximize the amount of contained air. We show that the algorithm which simply inflates all balloons to a fixed volume is close to optimal in this setting.

Joint work with Anna Karlin, Mohammad Mahdian, and Kunal Talwar

We will consider generating a random vertex colouring of a graph using a Markov chain. The aim is to determine the smallest number of colours, measured as a multiple of the maximum degree, for which the chain converges in time polynomial in the number of vertices. We will examine this problem for the case of an Erdős-Rényi random graph. This has been studied previously for graphs with small edge density. However, the methods used in the sparse case do not seem applicable as the edge density becomes larger. We will describe a different approach, which can be used to obtain results for denser graphs.

We suggest a game theoretic framework (so called now 'interval model') for the analysis of option prices in financial mathematics. This leads to remarkable explicit formulas and effective numeric procedures for rainbow (or coloured) options hedging.

How efficiently can one move about in a network linking a configuration of n cities? Here the notion of "efficient" has to balance (a) total network length against (b) short network distances between cities. My talk will explain how to use Poisson line processes to produce networks which are nearly of shortest total length, which make the average inter-city distance almost Euclidean.

This is joint work with David Aldous.

We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite point set P, our goal is to find a set C of size k such that the sum of errors D(P,C) = Σ_{{p in P}} min_{{c in C}} {D(p,c)} is minimized. The main result in this talk can be stated as follows: There exists an O(n 2^{(k/ε)^O(1)}) time (1+ε)-approximation algorithm for the k-median problem with respect to D, if the 1-median problem can be approximated within a factor of (1+ε) by taking a random sample of constant size and solving the 1-median problem on the sample exactly.

Using this characterization we obtain the first linear time (1+ε)-approximation algorithms for the k-median problem for doubling metrics, for the Kullback-Leibler divergence, Mahalanobis distances and some special cases of Bregman divergences.

We consider the notorious travelling salesman problem (TSP) and such seemingly well-studied algorithms as the Held & Karp dynamic programming algorithm, the double-tree and Christofides heuristics, as well as algorithms for finding optimal pyramidal tours. We show how the ideas from these classical algorithms can be combined to obtain one of the best tour-constructing TSP heuristics. The main message of our presentation: despite the fact that the TSP has been investigated for decades, and thousands(!) of papers have been published on the topic, there are still plenty of exciting open problems, some of which (we strongly believe) are not that difficult to resolve.

We consider the notorious travelling salesman problem (TSP) and such seemingly well-studied algorithms as the Held & Karp dynamic programming algorithm, the double-tree and Christofides heuristics, as well as algorithms for finding optimal pyramidal tours. We show how the ideas from these classical algorithms can be combined to obtain one of the best tour-constructing TSP heuristics. The main message of our presentation: despite the fact that the TSP has been investigated for decades, and thousands(!) of papers have been published on the topic, there are still plenty of exciting open problems, some of which (we strongly believe) are not that difficult to resolve.

Chvátal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or ½, such cuts are known as {0,½}-cuts. This talk reports on our study to separate general {0,½}-cuts effectively, despite its NP-completeness.

We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated {0,½}-cut, we formulate the (reduced) problem as an integer linear program. Some simple heuristic separation routines complete the algorithmic framework.

Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.

Koller, Megiddo and von Stengel showed in 1994 how to efficiently find minimax behavior strategies of two-player imperfect information zero-sum extensive games using linear programming. Their algorithm has been widely used by the AI-community to solve very large games, in particular variants of poker. However, it is a well known fact of game theory that the Nash equilibrium concept has serious deficiencies as a prescriptive solution concept, even for the case of zero-sum games where Nash equilibria are simply pairs of minimax strategies. That these deficiencies show up in practice in the AI-applications was documented by Koller and Pfeffer. In this talk, we argue that the theory of equilibrium refinements of game theory provides a satisfactory framework for repairing the deficiencies, also for the AI-applications. We describe a variant of the Koller, Megiddo and von Stengel algorithm that computes a *quasi-perfect* equilibrium and another variant that computes all *normal-form proper* equilibria. Also, we present a simple yet non-trivial characterization of the normal form proper equilibria of a two-player zero-sum game with perfect information.

The talk is based on joint papers with Troels Bjerre Sørensen, appearing at SODA'06 and SODA'08.

This talk examines the computational complexity of approximating the number of solutions to a Boolean constraint satisfaction problem (CSP). It extends a line of investigation started in a classical paper of Schaefer on the complexity of the decision problem for CSPs, and continued by Creignou and Hermann, who addressed exact counting.

We find that the class of Boolean CSPs exhibits a trichotomy. Depending on the set of allowed relations, the CSP may be polynomial-time solvable (even exactly); or the number of solutions may be as hard to approximate as the number of accepting computations of a non-deterministic Turing machine. But there is a third possibility: approximating the number of solutions may be complete for a certain logically defined complexity class, and hence equivalent in complexity to a number of natural approximate counting problems, of which independent sets in a bipartite graph is an example.

All the necessary background material on approximate counting and CSPs will be covered.

This is joint work with Martin Dyer (Leeds) and Leslie Ann Goldberg (Liverpool).

From the theory of graph minors we know that the class of planar graphs is the only critical class with respect to tree-width. In this talk, we reveal a critical class with respect to clique-width, a notion generalizing tree-width. This class is known in the literature under different names, such as unit interval, proper interval or indifference graphs, and has important applications in various fields. We prove that the unit interval graphs constitute a minimal hereditary class of unbounded clique-width and discuss some applications of the obtained result.

In this talk we study basic network design problems with modular capacity assignment. The focus is on classes of strong valid inequalities that are defined for cuts of the underlying network. We show that regardless of the link model, facets of the polyhedra associated with such a cut translate to facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Accordingly, we focus on the facial structure of the cutset polyhedra. A large class of facets of cutset polyhedra is defined by flow-cutset inequalities. These inequalities are presented in a unifying way for different model variants. We propose a generic separation algorithm and in an extensive computational study on 54 instances from the survivable network design library (SNDlib), we show that the performance of CPLEX can significantly be enhanced by this class of cutting planes.

Suppose we have a grid mxn, two real-valued functions f and g on [m] and [n] respectively, and a threshold value b. We declare a point (i,j) in the grid to be open if f(i) + g(j) is at most b. It turns out that, if there is a path of open points from the bottom point (1,1) to the top point (m,n), then there is a monotone path of open points, i.e., if we can get from bottom to top at all, then we can do so without having to retreat.

This is an instance of the following much more general result. Let f be a submodular function on a modular lattice L; we show that there is a maximal chain C in L on which the sequence of values of f is minimal among all paths from 0 to 1 in the Hasse diagram of L, in a certain well-behaved partial order -- the "worm order" -- on sequences of reals. One consequence is that the maximum value of f on C is minimised over all such paths. We discuss the worm order, relate our work to that on searching a graph, and mention some sample applications.

Joint work with Peter Winkler.

In this talk I will first present the basic working principles of Ant Colony Optimization (ACO) and then explain some of our work on applying ACO to vehicle routing problems. The main idea in this context is to exploit problem knowledge to improve the performance of the general purpose heuristic ACO.

We prove that finding a rooted subtree with at least k leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in digraphs from a wide family L that includes all strong and acyclic digraphs. This settles completely an open question of Fellows and solves another one for digraphs in L. We also prove the following combinatorial result which can be viewed as a generalization of many results for a "spanning tree with many leaves" in the undirected case, and which is interesting on its own: If a digraph D ∈ L of order n with minimum in-degree at least 3 contains a rooted spanning tree, then D contains one with at least (n/4)^1/3-1 leaves.

Joint work with Noga Alon, Fedor Fomin, Michael Krivelevich and Saket Saurabh

An oblivious routing protocol makes its routing decisions independent of the traffic in the underlying network. This means that the path chosen for a routing request may only depend on its source node, its destination node, and on some random input. In spite of these serious limitations it has been shown that there are oblivious routing algorithms that obtain a polylogarithmic competitive ratios w.r.t. the congestion in the network (i.e., maximum load of a network link).

In this talk I will present a new hierarchical decomposition technique that leads to good oblivious routing algorithms. This decomposition can also be used as a generic tool for solving a large variety of cut based problems in undirected graphs.

How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order log n. Recently, we (Paterson and Zwick) constructed n-block stacks with overhangs of order n^1/3, exponentially better than previously thought possible. The latest news is that we (Paterson, Peres, Thorup, Winkler and Zwick) can show that order n^1/3 is best possible, resolving the long-standing overhang problem up to a constant factor.

I shall review the construction and describe the upper bound proof, which illustrates how methods founded in algorithmic complexity can be applied to a discrete optimization problem that has puzzled some mathematicians and physicists for more than 150 years.

High performance floating point hardware is notoriously difficult to design correctly. In fact, until recently, the most expensive hardware bug encountered in industry, was the Intel FDIV bug in 1994 that lead to a charge of 450 million dollars against earnings. At the same time, floating point arithmetic is unique in that there is a fairly unambiguous specification, the IEEE 754 standard, which all implementations should obey. Unfortunately, bridging the gap between the mathematical specification of the standard and a low-level implementation is an extremely difficult task. At Intel we have developed an approach that combines the strengths of theorem proving with symbolic trajectory evaluation (a type of model checking), that allows us to completely verify the correctness of todayÇs floating point units. In this talk I will discuss the evolution of this approach and discuss some of the results that have been obtained in addition to areas of future research.

It is well known that boundedness of tree-width implies polynomial-time solvability of many algorithmic graph problems. The converse statement is generally not true, i.e., polynomial-time solvability does not necessarily imply boundedness of tree-width. However, in graphs of bounded vertex degree, for some problems, the two concepts behave in a more consistent way. We study this phenomenon with respect to three important graph problems -- dominating set, independent dominating set and induced matching -- and obtain several results toward revealing the equivalency between boundedness of the tree-width and polynomial-time solvability of these problems in bounded degree graphs. Joint work with Martin Milanic.

The PCP theorem [AS, ALMSS] specifies a way of encoding any mathematical proof such that the validity of the proof can be verified probabilistically by querying the proof only at a constant number of locations. Furthermore, this encoding is complete and sound, i.e., valid proofs are always accepted while invalid proofs are accepted with probability at most 1/2. A natural question that arises in the construction of PCPs is by how much does this encoding blow up the original proof while retaining low query complexity.

The study of efficient probabilistic checkable proofs was initiated in the works of Babai et. al. [BFLS] and Feige at. al. [FGLSS] with very different motivation and emphases. The work of Babai et. al. considered the direct motivation of verifying proofs highly efficiently. In contrast, Feige et. al. established a dramatic connection between efficient probabilistically checkable proofs (PCPs) and the inapproximability of optimization problems.

In this talk, I'll review some of the recent works of Ben-Sasson et. al. [BGHSV'04, BGHSV'05], Dinur-Reingold [DR], Ben-Sasson and Sudan [BS'04] and Dinur [Din'06] that have led to the construction of PCPs that are at most a polylogarithmic factor longer than the original proof and furthermore, are checkable by a verifier running in time at most polylogarithmic in the length of the original proof.

An important ingredient in these constructions is a a new variant of PCPs called "PCPs of Proximity''. These new PCPs facilitate proof composition, a crucial component in PCP construction. I'll outline how these new PCPs allow for shorter PCP constructions and efficient proof verification

We give an overview of the optimization challenges addressed in recent years ranging from frequency assignment in mobile networks to multi-layer network design in backbone networks. We discuss the practical problems, the mathematical modelling, the methodologies used to tackle these problems, and the results achieved.