All
Speakers: Jannik Matuschke
The min-cost matching problem suffers from being very sensitive to small changes of the input. Even in a simple setting, e.g., when the costs come from the metric on the line, adding two nodes to the input might change the optimal solution completely. On the other hand, one expects that small changes in the input should incur only small changes on the constructed solutions, measured as the number of modified edges.
Speakers: Manuel Aprile
Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the extended formulation also depends on the size of the slack matrix (hence, of the exact description in the original space). We give general sufficient conditions under which those tools can be implemented as to be output-efficient. In particular we apply this to Yannakakis' extended formulation for the stable set polytope of perfect graphs, for which, to the best of our knowledge, an efficient construction was previously not known.
Speakers: Seungbum Jo
We consider the problem of encoding two-dimensional arrays, whose elements come from a total order, for answering Top-k queries. The aim is to obtain encodings that use space close to the information-theoretic lower bound, which can be constructed efficiently. For 2 x n arrays, we first give upper and lower bounds on space for answering sorted and unsorted 3-sided Top-k queries. For m x n arrays, with m <=n and k <=mn, we obtain (m lg{(k+1)n choose n}+4nm(m-1)+o(n))-bit encoding for answering sorted 4-sided Top-k queries.
Speakers: Alfio Giarlotta
Semiorders are binary relations that are complete, Ferrers, and semitransitive. In particu- lar, they display a transitive asymmetric part (strict preference), and a usually intransitive symmetric part (indifference). Semiorders are among the most studied categories of binary relations in preference modeling. This is due to the vast range of economic scenarios which can modelled by appealing to the notion of ‘just noticeable difference’. We give a univer- sal characterization of semiorders, which uses the notions of a Z-product and a Z-line.
Speakers: Tom Kelly
In a fractional coloring, vertices of a graph are assigned subsets of the [0, 1]-interval such that adjacent vertices receive disjoint subsets. The fractional chromatic number of a graph is at most k if it admits a fractional coloring in which the amount of "color" assigned to each vertex is at least 1/k. We investigate fractional colorings where vertices "demand" different amounts of color, determined by local parameters such as the degree of a vertex.
Speakers: Jean-Paul Doignon
A typical two-stage process governs the selection of meal items in an Italian menu. The process admits a direct formalization in terms of choice spaces. Path-independent choice spaces are cryptomorphic to convex geometries (or antimatroids, introduced by Robert E. Jamison). There results a construction of a new convex geometry for a convex geometry (the base) given together with a family of convex geometries (the fibers) indexed by the elements of the base; we call the outcome a resolution.
Speakers: Vissarion Fisikopoulos
We experimentally study the problem of estimating the volume of convex polytopes, focusing on H- and V-polytopes, as well as zonotopes. Although a lot of effort is devoted to practical algorithms for H-polytopes there is no such method for the latter two representations. We propose a new, practical method for all representations, which is faster on H-polytopes; it relies on Hit-and-Run (HnR) sampling, and combines a new simulated annealing method with the Multiphase Monte Carlo (MMC) approach.
Speakers: Samuel Fiorini
Tomorrow Sam will tell us how to compute a maximum independent set in a graph embedded in a fixed surface if there are not many disjoint odd cycles in the graph. Note the unusual room: NO8.202 ("petit séminaire"), because of exams taking place in the other rooms.