search

Lunches

Bipartite Diameter and Other Measures Under Translation Thu, Nov 21, 2019 12:30 CET

Speakers: Boris Aronov

Let A and B be two sets of points in R^d, where |A|=|B|=n and the distance between them is defined by some bipartite measure dist(A,B). We study several problems in which the goal is to translate the set B, so that dist(A, B) is minimized. The main measures that we consider are (i) the diameter in two and three dimensions, that is diam(A,B) = max {d(a,b) : a in A, b in B}, where d(a,b) is the Euclidean distance between $a$ and $b$,

On Grammars, Polytopes, and Groups Fri, Nov 8, 2019 12:30 CET

Speakers: Mateus de Oliveira Oliveira

A fundamental step towards solving combinatorial problems using techniques from linear programming theory is to encode the space of feasible solutions for such problems as the set of vertices of polytopes of small extension complexity. In this work, we establish several connections between the extension complexity of polytopes, formal language theory, and group theory. In particular, we introduce the notion of homogeneous context-free grammars and show that polytopes corresponding to languages accepted by polynomial-size non-uniform families of grammars with polynomial homogeneity have polynomial extension complexity.

Coloring and Maximum Weight Independent Set of rectangles Wed, Nov 6, 2019 12:30 CET

Speakers: Bartosz Walczak

We prove that every intersection graph of axis-parallel rectangles in the plane with clique number ω has chromatic number O(ω log ω), which is the first improvement of the original O(ω²) bound of Asplund and Grünbaum from 1960. As a consequence, we obtain a polynomial-time O(log log n)-approximation algorithm for Maximum Weight Independent Set in axis-parallel rectangles, improving the previous best approximation ratio of O(log n/log log n). Joint work with Parinya Chalermsook.

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank Wed, Sep 11, 2019 12:30 CEST

Speakers: Makrand Sinha

Chattopadhyay, Mande and Sherif (to appear in STOC 2019) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communication complexity. This gives an exponential separation between randomized communication complexity and logarithm of the approximate rank, refuting the log-approximate-rank conjecture. We show that even the quantum communication complexity of the sink function is polynomial, thus also refuting the quantum log-approximate-rank conjecture.

3D Snap Rounding Wed, Jun 19, 2019 12:30 CEST

Speakers: Leo Valque

Many computational geometry algorithms require greater accuracy for output than for input. So, to send or use the output, we often need to round it off. If this is done naively, intersections can occur during rounding. An algorithm from Devillers, Lenhart, Lazard was presented last year to solve this problem. The worst case of this algorithm is \(O(n^15)\). An implementation of this algorithm shows that on average, it is \(O(n \sqrt{n})\).

A time- and space-optimal algorithm for the many-visits TSP Wed, May 29, 2019 12:30 CEST

Speakers: Matthias Mnich

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number kcof times. Travel costs may not be symmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984).

Maintaining Perfect Matchings at Low Cost Fri, May 10, 2019 12:30 CEST

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.

Extended formulations from communication protocols in output-efficient time Thu, May 2, 2019 12:30 CEST

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.

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.