Noticias en español
Hiring under uncertainty and competition: variations of the secretary problema.
Abstract: In this talk, we study some variations of the Secretary Problem. In the Secretary Problem, an employer sees a sequence of candidates. Each time a new candidate arrives, the employer makes an irrevocable choice on whether to hire based only on the relative ranking of the candidates seen so far. The employer tries to maximize the probability of hiring the best. It is known that the optimal strategy hires the best with probability 1/e. We consider an infinite arrival regime. This allows us to apply a lemma characterizing the number of “promising candidates” in any given time interval....
Read MoreBeating Greedy Asymptotically for Weighted k-Matroid Intersection
Abstract: Greedy is one of the most widely used algorithmic paradigms, both in practice and in theory. Its success is classically explained by matroid theory: whenever the underlying optimization problem has a matroid structure, Greedy is optimal. Greedy also extends to problems involving multiple matroids, but its performance guarantee deteriorates to 1/k, where k is the number of matroids. For Weighted k-Matroid Intersection, Greedy has long been the asymptotically best-known algorithm. In this talk, I will survey recent progress that improves on Greedy for Weighted k-Matroid Intersection...
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 MoreIdentifying the deviator.
Abstract: Alice and Bob control a random walk: alternately, each of them flips a fair coin, is supposed to report the outcome, and the random work advances according to the report. Suppose that the random walk did not return to the origin infinitely often. We suspect that one of Alice and Bob misreported the outcomes of her or his coin. Can we identify the deviator? More generally, several players are supposed to follow a prescribed profile of strategies (e,g, select each of Right and Left with probability 1/2). If they follow this profile, they will reach a given target (e.g., the...
Read More