Well-quasi-ordering digraphs by the strong immersion relation.

Event Date: Dec 16, 2020 in ACGO, Seminars

Abstract: A well-quasi-ordering is a reflexive and transitive binary relation such that every infinite sequence has a non-trivial increasing subsequence. The study of well-quasi-ordering was stimulated by two conjectures of Vazsonyi in 1940s: trees and subcubic graphs are well-quasi-ordered by the topological minor relation. It is known that the topological minor relation does not well-quasi-order all graphs. Nash-Williams in 1960s introduced the notion of strong immersion and conjectured that the strong immersion relation well-quasi-orders all graphs, which is a common generalization of...

Read More

Counting integer partitions with the method of maximum entropy.

Event Date: Dec 09, 2020 in ACGO, Seminars

  Abstract: The problem of asymptotically counting integer partitions has a long and storied history, beginning with the pioneering work of Hardy and Ramanujan in 1918. In the work presented here, we give a probabilistic perspective on this problem, and use this approach to prove an asymptotic formula for the number of partitions of an integer n where the sums of the kth powers of the parts are also fixed, for some collection of values k. To obtain this result, we reframe the counting problem as an optimization problem, and find the probability distribution on the set of all integer...

Read More

Matroids, polymatroids and submodular functions: algebra or optimization?

Event Date: Dec 02, 2020 in ACGO, Seminars

Abstract: Matroids, polymatroids and submodular functions are beautiful objects that have appeared in many areas of mathematics including algebra, geometry, topology and optimization. Consequently, they have been studied from multiple points of view. This oftentimes has the consequence that the same results are proven from different points of view and by very different communities. A notable example being their study in optimization and algebraic combinatorics. The goal of this talk is to tell this story, show how a small mixture of ideas from different communities lead to powerful algebraic...

Read More

An optimal algorithm for strict circular seriation.

Event Date: Nov 25, 2020 in ACGO, Seminars

Abstract: Seriation is an exploratory combinatorial data analysis technique to reorder objects into a sequence along a one-dimensional continuum when the only available information among the objects is their pairwise similarity (or dissimilarity). Linear seriation aims at inferring an ordering (permutation) consistent with an underlying linear order of the data. In many cases however, the data objects may be arranged around a closed continuum yielding a rather circular underlying order. In a matrix representation, this can be visualized as a symmetric matrix of pairwise dissimilarities...

Read More

Apportionment Mechanisms under Parity Constraints and the case of Chile and a new Political Constitution.

Event Date: Nov 18, 2020 in ACGO, Seminars

  Abstract: How many seats should be allocated to each political party in an election? This question has a long and rich history, and plays a fundamental role in order to ensure appropriate levels of representation in the parliaments. We consider this question in the presence of types (e.g. men and women), where apart from ensuring proportionality at the party level, we also have to find an allocation which is paritary for the types. We consider two different approaches: one of them, with a greedy/local search paradigm, corresponds to a mechanism recently approved in the chilean...

Read More

On the two-dimensional knapsack problem for convex polygons.

Event Date: Oct 28, 2020 in ACGO, Seminars

Abstract: We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow rotating the polygons by arbitrary angles. In this talk we will first present: – a quasi-poly time O(1)-approximation – a poly time O(1)-approximation algorithm if all input polygons are triangles. We will then look into the setting of resource augmentation, i.e., we allow to increase the size of the...

Read More