Encoding Two-Dimensional Range Top-k Queries Revisited Wed, Apr 24, 2019 12:30 CEST

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.

Universal Semiorders Thu, Mar 28, 2019 12:30 CET

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.

Fractional coloring with local demands Wed, Mar 27, 2019 12:30 CET

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.

From Italian menus to resolutions of convex geometries Fri, Mar 1, 2019 12:30 CET

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.

Volume estimation by a new annealing schedule for cooling convex bodies Fri, Feb 1, 2019 12:30 CET

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.

Computing a maximum independent set in a graph embedded in a fixed surface when the odd cycle packing number is bounded Wed, Jan 16, 2019 12:30 CET

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.

Finding a Maximum-Weight Convex Set in a Chordal Graph Wed, Nov 21, 2018 12:30 CET

Speakers: Keno Merckx

TBA Wed, Nov 14, 2018 12:30 CET

Speakers: Natalia Garcia Colin

Hypergraphic polytopes and flip graphs Wed, Nov 7, 2018 12:30 CET

Speakers: Jean Cardinal

The cage problem Wed, Oct 24, 2018 12:30 CEST

Speakers: Gabriela Araujo