Noticias en español
Online learning with consistency oracle.
Abstract: A binary classification game is being played between a learner and an adversary. At each round, the adversary selects a natural number x and the learner has to predict its label h(x). Is there a bound on the number of mistakes made by the learner, assuming that h comes from some class H? Littlestone gave a learning algorithm which achieves an optimal mistake bound d, provided H has a certain combinatorial property. However, Littlestone’s algorithm is believed to be computationally demanding. Can we have a feasible strategy for the learner and if so, how many mistakes would...
Read MoreOptimal Disease Screening Policies Under Budget Constraints.
Abstract: We study the problem of selecting screening policies for a given disease in a large population which is divided into risk groups, and where we have a measure of benefit and cost for each possible policy. We want to find a selection of them, one for each risk group so that the total benefit is maximized and a budget constraint per time period is satisfied. To that end we start from an individual base model that accounts for the probabilistic appearance and evolution of the disease along stages. Our main result is an ergodic-like theorem which allows us to calculate the expected...
Read MoreComputing Bayes-Nash Equilibria in Auctions via Online Learning.
Abstract: Auction games are a central application of game theory in economics. However, while explicit formulas for Bayes-Nash equilibria are known for particular auction settings, we generally have to rely on numerical methods to predict the outcomes of auctions. We present a simple class of learning algorithms to approximate Bayes-Nash equilibria in these games. Surprisingly, while recent theoretical results suggest that such algorithms perform poorly in general matrix games, we provide experimental evidence that they perform very well in many different auction scenarios. Despite the...
Read MoreConstructing separating hyperplanes for non-convex quadratic problems.
Abstract: In 1971, Balas introduced the intersection cut framework as a method for generating separating hyperplanes (or “cuts”) in integer optimization. These cuts are derived from convex S-free sets, and inclusion-wise maximal S-free sets yield the strongest intersection cuts. When S is a lattice, maximal S-free sets are well-studied from theoretical and computational standpoints. In this talk, we focus on the case when S is defined by a non-convex quadratic inequality and show how to construct basic maximal quadratic-free sets. Additionally, we explore how to generalize the...
Read MoreA Unified Framework for Symmetry Handling.
Abstract: Discrete optimization problems are often solved using constraint programming or mided-integer programming techniques, using enumeration or branch-and-bound techniques. It is well known that if the problem formulation is very symmetric, there may exist many symmetrically equivalent solutions to the problem. Without handling the symmetries, traditional solving methods have have to check many symmetric parts of the solution space, which comes at a high computational cost. Handling symmetries in optimization problems is thus essential for devising efficient solution methods. In this...
Read MoreLoad Balancing Algorithms on Scheduling Problems with a Concave Function of the Load.
Abstract: In load balancing scheduling problems n jobs are to be assigned to m machines. Each job has its own processing time, and we define the load of a machine as the sum of the processing time of all jobs assigned to it. In this work, the machines have a concave non-decreasing function (accessed through a value oracle) applied to their loads and our goal is to maximize the sum of these valuations. This setting models a productivity maximization of machines where we aim to allocate indivisible resources, such as fuel tanks. We prove the existence of a PTAS for the offline version, which...
Read More