Noticias en español
An orbit around quasi-trasitive graphs
Abstract: A graph is called quasi-transitive if it has finitely many orbits under automorphism. I will present some recent advances on quasi-transitive graphs, especially in the planar and minor-free cases. I will also talk about some related recent work with Agelos Georgakopoulos and Bobby Miraftab.
Read MoreDecremental tree sums.
Abstract: In this talk, I will discuss the following semi-dynamic graph problem: Maintain a vertex-weighted forest under the following operations: Delete an edge; change the weight of a vertex; and, given a vertex v, return the total weight of all vertices in the same tree as v. I’ll present the following results from joint work with Marek Sokołowski. * A data structure with O(m + n log* n) time for m operations; * a linear-time data structure for *unweighted* forests; * and a data structure with (conditionally) optimal, but unknown running time. At the end, I will briefly speculate...
Read MoreGeneralized Assignment and Knapsack Problems in the Random-Order Model
Abstract: We study different online optimization problems in the random-order model. There is a finite set of bins with known capacity and a finite set of items arriving in a random order. Upon arrival of an item, its size and its value for each of the bins is revealed and it has to be decided immediately and irrevocably to which bin the item is assigned, or to not assign the item at all. In this setting, an algorithm is $\alpha$-competitive if the total value of all items assigned to the bins is at least an $\alpha$-fraction of the total value of an optimal assignment that knows all...
Read MoreExpansion of random 0/1 polytopes and the Mihail and Vazirani conjecture.
Abstract: A 0/1 polytope is the convex hull of a set of 0/1 d-dimensional vectors. A conjecture of Milena Mihail and Umesh Vazirani says that the graph of vertices and edges of every 0/1 polytope is highly connected. Specifically, it states that the edge expansion of the graph of every 0/1 polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of...
Read MoreA Normality Conjecture on Rational Base Number Systems
RESUMEN: The rational base number system, introduced by Akiyama, Frougny, and Sakarovitch in 2008, is a generalization of the classical integer base number system. Within this framework two interesting families of infinite words emerge, called minimal and maximal words. We formulate the conjecture that every minimal and maximal word is normal over an appropriate subalphabet. The aim of the talk is to convince the audience that the conjecture seems true and of considerable difficulty. In particular, we shall discuss its connections with several older conjectures, including the existence of...
Read More