Seminarios 2013

 

2013-12-18:

Author: Cristóbal Guzmán, Georgia Tech (USA).

Where: Sala 33, DII, 14.30-16.00

Title: Complejidad distribucional en optimización convexa no-diferenciable.

Abstract:Los métodos de primer orden (subgradiente) en optimización convexa son una elección natural cuando se trata de resolver problemas de gran escala, donde basta con obtener soluciones de mediana precisión. Los límites de desempeño de estos métodos pueden ser parcialmente comprendidos desde la perspectiva de la complejidad de oráculo en el peor caso.

En esta charla se presentan algunas de las limitaciones del estado del arte, y se introducen algunas extensiones de resultados clásicos al modelo de complejidad distribucional. En dicho modelo, la distribución de probabilidad de encontrar una instancia es parte del input del algoritmo, por lo que estos pueden explotar dicha distribución para acelerar su desempeño. Sin embargo, veremos que en el caso de optimización convexa no-diferenciable esto no ocurre, y tanto la complejidad de peor caso, aleatorizada y distribucional coinciden, salvo por un factor constante (esto cierra un gap logaritmico de la complejidad aleatorizada y de peor caso, que fue probado por Nemirovski y Yudin).

Este es un trabajo en conjunto con Gabor Braun y Sebastian Pokutta.

2013-12-11:

Author: Mathieu Faure, Université Aix-Marseille.

Where: Sala 33, DII, 14.30-16.00

Title: Economics of Blood Doping.

Abstract:In this talk, we discuss a game-theoretical model of the use by athletes of performance-enhancing drugs. We focus on a two-player game where players are heterogeneous and performances are subject to uncertainty. While the standard setup assumes these drugs increase maximum performances, we assume that they also increase the probability that a given athlete competes at his best possible level. This second effect drives the doping strategies alone, suggesting that focusing on the first effect leads to incorrect conclusions. The characteristics of Nash equilibria in this setup explain why it is so difficult to fight against doping.

 

2013-12-04:

Author: Denis Sauré, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: Challenges in sequential interdiction under partial information.

Abstract:
In this talk I will discuss the challenges associated with balancing the classical exploration exploitation trade off in the context of interdiction problems. I will first discuss the non-adversarial case, which can be seen as a combinatorial bandit setup, and will present a solution approach. Then I will discuss the additional challenges that arise in the interdiction setup, when feedback from an action follows from the rational reaction of an evader.

 

2013-11-27:

Author: Nodari Sitchinava, Karlsruhe Institute of Technology, Germany.

Where: Sala 33, DII, 14.30-16.00

Title: (Dynamic) range minima queries in the external memory and cache-oblivious models.

Abstract:
I will present new results for the one-dimensional range minimum query (RMQ) problem in the external memory and cache-oblivious models — models for designing I/O- and cache-efficient solutions. On a static instance with N elements and Q queries, our solution takes O(scan(N) + sort(Q)) = O(\frac{N}{B} + \frac{Q}{B}\log_{M/B}\frac{Q}{B}) I/O complexity and O({N+Q}) space in both models. I will also show that an instance of the offline dynamic RMQ problem with N updates and Q queries can be solved in O({\frac{N+Q}{B} \log^2_{M/B} \frac{N+Q}{B}}) I/O complexity and O({N+Q}) space in the external memory model.

 

2013-11-13:

Author: Natacha Astromujoff, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: A quantitive approach to perfect one-factorizations of complete bipartite graphs

Abstract: In this work we prove that pf(n)\geqslant \frac{1}{4}n^2 for all n\geqslant 2, where pf(n) is the maximum over all one-factorizations \cal F of the complete bipartite graph K_{n,n}, of the number in K_{n,n}. For even n, this lower bound is known to be an upper bound, which proves that pf(n)=\frac{1}{4}n^2.
For odd n we can improve this lower bound to show that pf(n)> \frac{1}{4}n^2.

Joint work with Martin Matamala.

 

2013-11-06:

Author: Jean-Bernard Baillon, Université Paris 1.

Where: Sala 33, DII, 14.30-16.00

Title: A “simple” matrix problem connected to Riemann’s Conjecture

Abstract: In this talk we will discuss a somewhat surprising connection between an apparently simple problem in matrix analysis and Riemann’s conjecture.

More precisely, consider R_n the inverse of the lower triangular matrix M_n=\left(\lfloor\frac{i}{j}\rfloor\right)_{1\leq i,j\leq n}, e.g.
M_3=\left[\begin{array}{ccc} 1&0 &0\\2&1&0\\3&1&1\end{array}\right]

Can you prove that |\sum R_{ij}|\leq \mbox{const}\sqrt{n}?
What about |\sum R_{ij}|\leq k_\epsilon\; n^{\frac{1}{2}+\epsilon} ?

Remark: If \lfloor \frac{i}{j}\rfloor is replaced by ( \frac{i}{j})_+ where
x_+=0 if x<1 and x_+=x otherwise, we have |\sum R_{ij}|\sim \ln{n}.

 

2013-10-30:

Author: Daniel Espinoza, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: Large scale networks with side constraints

Abstract: In this talk I present some of the known results and algorithms for solving extremely large problems whose main set of constraints are simple network constraints. We then move on to show how many problems can be modeled using this kind of structure, and then present some challenges on new problems and how to extend the scheme in general (or prove it impossible to extend).

Joint work with Marcos Goycoolea and Eduardo Moreno.

 

2013-10-23:

Author: Alantha Newman, EPFL, Switzerland.

Where: Sala 33, DII, 14.30-16.00

Title: The Traveling Salesman Problem: Algorithms and Open Problems

Abstract:
In the past few years, there has been much progress on the Graphic Traveling Salesman Problem.

In this talk, we will first present the beautiful algorithm of Moemke-Svensson for Graphic TSP followed by some open questions relating to how their techniques can be applied to special classes of graphs.

Then we present a simple algorithm for Graphic TSP based on steiner cycles that yields a tour of length at most 4n/3 when a 2-connected input graph contains a Hamiltonian path. We show that this algorithm can be generalized to yield the same bound on a k-connected graph that has a spanning tree with at most k/2+1 leaves. This suggests the question of how well one can do in general if a graph contains a spanning tree with few leaves: In fact, one can use the Moemke-Svensson algorithm to obtain a tour of length at most 4n/3 + O(k) when the input graph contains a DFS tree with k leaves. We discuss how this approach might be extended to obtain an approximation algorithm for Graph TSP in general graphs.

 

2013-10-09:

Author: Fidaa Abed, Max-Planck Institute, Germany.

Where: Sala 33, DII, 14.30-16.00

Title: Network design games

Abstract: In Network design games we have a graph (directed or undirected). In this graph every edge has a weight representing the cost of creating such an edge. Every player in this game is trying to connect two nodes in the graph, the source and the target, with the cheapest path among all possible paths. If more that one player is interesting in creating one edge, the cost is splitted fairly among them.

I will present the known results about the Price of Anarchy (PoA) and the Price of Stability (PoS) for this game. Then I will point out a famous open problem and show a possible direction to attack this problem.

 

2013-10-02:

Author: Renaud Chicoisne, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: An efficient algorithm to match GPS data on a map

Abstract: GPS data of vehicles travelling on road networks can be used to estimate road travel times.
This requires the identification of the corresponding paths in the network.
In this work we develop an algorithm capable to identify a path minimizing a special distance with the GPS trajectory even in presence of cycles. This algorithm is theoretically fast but can perform slowly in practice. Mild assumptions over the GPS precision and the use of heuristic steps allow a very fast path finding procedure.
We present computational results comparing these algorithms for over 30000 real and generated GPS samples on a grid graph and real maps of the cities of Seattle and Santiago. We show that on average, the paths returned by our algorithm and the heuristic version have respectively 92.5% and 89% of their edges in a corridor of one meter around the GPS trajectory.

 

2013-09-25:

Author: David Conlon, University of Oxford.

Where: Sala Seminarios, CMM, 14.30-16.00

Title: A relative Szemerédi theorem

Abstract: The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. One of the main ingredients in their proof is a relative Szemerédi theorem which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions.

In this talk, we will discuss a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition is sufficient. Our strengthened version can be applied to give the first relative Szemerédi theorem for k-term arithmetic progressions in pseudorandom subsets of Z_N of density N^{-c_k}.

The key component in our proof is an extension of the regularity method to sparse pseudorandom hypergraphs, which we believe to be interesting in its own right. From this we derive a relative extension of the hypergraph removal lemma. This is a strengthening of an earlier theorem used by Tao in his proof that the Gaussian primes contain arbitrarily shaped constellations and, by standard arguments, allows us to deduce the relative Szemerédi theorem.

This is joint work with Jacob Fox and Yufei Zhao.

 

2013-09-11:

Author: Victor Verdugo, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: Programación de máquinas no relacionadas con tiempos de instalación

Abstract: Durante el presente trabajo se estudia el problema de programar un conjunto de tareas J en un conjunto de máquinas M, en donde cada tarea puede ser dividida en varias partes y cada parte es procesada de manera independiente en alguna máquina. Las máquinas son no relacionadas, es decir, cada trabajo j toma un tiempo p_{ij} en procesarse en la máquina i y además existe un tiempo de instalación s_{ij} que requiere la máquina antes de procesar cualquier parte del trabajo j. Encontrar la programación que minimiza el tiempo de funcionamiento de las máquinas es NP-hard. En esta charla se mostrará una (3+sqrt(5))/2 – aproximación para el problema basada en redondear una solución extrema de cierta relajación lineal para el problema.

Trabajo en desarrollo, con José R. Correa, Alberto Marchetti-Spaccamela, Jannik Matuschke, Ola Svensson, Leen Stougie y José Verschae.

 

2013-08-28:

Author: Jeremy Barbay, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: Problemas teóricos en crowd sourcing quality control

Abstract: Recientemente Michael Goodrich presentó (en WADS, “Workshop on Algorithms and Data Structures”) resultados teóricos sobre la detección de “slackers” en sistema de crowd sourcing. Me gustaría comenzar a trabajar de manera similar en problemas de crowd-sourcing como los descritos abajo (y otros mas simples pero similares). Propongo presentarlos de manera informal y conversarlos en el seminario, como una preparacion a la charla de Luis von Ahn (acá el link Charla: El futuro de la educación en línea).

1. Calibrated Peer Review:
Digamos que alguien que somete un artículo a una conferencia tiene que revisar x errores de inglés, para cada uno de los cuales se insertaron d errores de manera automática.
- Sus correcciones (distintas de las xd que ya eran conocidas) y su revisión seran considerados para el resto del proceso solamente si él detectó una proporción p de los xd errores ya conocidos.
¿Cuáles son las propiedades deseables de un tal sistema? e.g.
- razón entre errores “de prueba” y “reales”,
- razón entre incentivo a someter y trabajo a realizar, etc…
- ¿Cuáles son las valores optimales de d, x y p para estas propiedades?

2. Boot Strapping Database
Un usuario tiene que responder con éxito a un desafio (e.g. validar si n fotos muestran o no un gato) para avanzar en un programa (e.g. tener accesso a fotos etiquetadas en un idioma que estudia). Para una proporción p de las fotos, ya se sabe la respuesta al desafio (e.g. si muestran un gato o no). Para las otros fotos, se quiere validar el criterio con una mayoría calculada de las respuestas de los usuarios. Dado que la probabilidad de responder correctamente al desafío es de 1/2^{pn}, un adversario puede avanzar en el programa despues de 2^{pn} intentos, por lo cual hay que “castigarlo”. ¿Cuáles son las politicas suficientes para “castigar” un adversario?
1. doblar la cantidad de fotos a identificar (así el tiempo promedio no converge);
2. doblar la proporcion de fotos para cual las respuestas son conocidas (same argument);
3. estrategia 2 hasta que p=1, y despues estrategia 1.

 

2013-08-21:

Author: José A. Soto, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: Mixed Robust Matching and Extensions

Abstract: The following zero-sum game is played on a weighted graph G:
Alice selects a matching M in G and Bob selects a number k. Then, Alice receives a payoff equal to the ratio of the weight of the top k edges of M; to OPT(k), which is the maximum weight of a matching of size at most k in G. If M guarantees a payoff of at least alpha then it is called alpha-robust.

In 2002, Hassin and Rubistein showed an algorithm that returns a Sqrt(1/2) – robust matching, which is best possible.

In this talk, I will discuss the variant of this game in which Alice is allowed to use randomization. We show an algorithm that returns a 1/ln(4) -robust mixed-matching which is based on the following nontrivial observation: If all the edge-weights are integer powers of 2, then the lexicographically maximum matching is 1-robust. This property holds not only for matchings but also for any independence system in which OPT(k) is a concave function of k.

This is on-going work with Martin Skutella and Jannik Matuschke.

 

2013-07-10:

Author: José Correa, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: Maximizando Funciones Submodulares

Abstract: Veremos un resultado de Buchbinder, Feldman, Naor, y Schwartz (FOCS 2012) que (casi) cierra la historia de la busqueda de algoritmos de aproximación para maximizar funciones submodulares. El resultado principal es un algoritmo aleatorizado que entrega una aproximación de factor 1/2, lo que complementa el resultado de Feige, Mirrokni, y Vondrak (FOCS 2007) quienes demuetran que una 1/2 +ε aproximación para este problema requiere una cantidad exponencial de consultas al oráculo que define la funcion.

 

2013-07-03:

Author: Gonzalo Navarro, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: Encodings para Consultas en Rangos

Abstract: En esta segunda charla mostraremos como extender las Range Minimum Queries en dos direcciones naturales: encontrar el k-ésimo en un rango y encontrar los top-k elementos en un rango. El contexto es el de encodings, es decir estructuras que no acceden al arreglo original. Mostraremos una cota de n log k bits para cualquier encoding de este tipo, una solución para el k-ésimo y top-k en one-sided queries (donde el rango es de la forma [1,i]), y una solución para top-k en two-sided queries (rangos [i,j]). Todas requieren tiempo óptimo o casi óptimo y espacio O(n log k) bits.

2013-06-19:

Author: Gonzalo Navarro, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: Range Minimum Queries

Abstract: Esta es la primera de una secuencia de dos charlas. En la primera describiremos las soluciones al problema de preprocesar un arreglo de números de modo de poder responder, dado un rango, dónde está el mínimo. Este problema ocurre con mucha frecuencia y está relacionado con el de encontrar lowest common ancestors en árboles. Veremos las soluciones más relevantes, llegando a la óptima, en que se necesita tiempo constante y solamente dos bits por entero, pudiéndose descartar el arreglo original. En la segunda charla pasaremos al tema más novedoso de extender estos resultados a encontrar los top-k en un arreglo que no se puede almacenar.

 

2013-06-12:

Author: Mauricio Soto, Universidad de Chile.

Where: Sala 33, DII, 14.30-16.00

Title: c-AND: A (not so) new intersection graph class.

Abstract: In this work, we study the following graph model: vertices are associated to both, an interval in the euclidean line and a representative point in this interval. Two vertices are connected by an edge if and only if for each vertex, its interval contains the other vertex’s representative point. We present a combinatorial characterization and an intersection model for the family. Based on these results, we determine the containment relation of the family with other known graph classes. In the particular case where each point is the center of its respective interval, we provide constructive representations for interval, block and outerplanar graphs.

Joint work with Christopher Thraves (GSyC, Universidad Rey Juan Carlos).

 

2013-06-05:

Author: Laurent Feuilloley, ENS-Cachan, France.

Where: Sala 33, DII, 14.30-16.00

Title: Maximum independent set of rectangles

Abstract: We study the problem of finding a maximum non-overlapping (independent) set of axis-parallel rectangles and its dual problem, consisting on finding a minimum set of points stabbing all rectangles (hitting set). It is immediate to note that given a collection of rectangles the size of a minimum hitting (MHS) set is at most that of a maximum independent set (MIS), while a conjecture of Wegner [1965] asks whether MIS < 2MHS.
We prove that the conjecture holds in the special case when the upper-right corners of all rectangles lie along a decreasing line. Furthermore, we provide a characterization of the resulting graphs and link them to other classes of graphs including the so-called 2-thin graphs. Finally, we give a polynomial time algorithm to find a MIS in such a special case, which constitutes a nontrivial generalization of the algorithm for MIS in interval graphs.

 

2013-05-29:

Author: Alejandro Angulo, Universidad de Chile

Where: Sala 33, DII, 14.30-16.00

Title: Sequence Independent Lifting for Semi-Continuous Knapsack Polyhedron with Generalized Upper Bounds

Abstract: In this work, semi-continuous knapsack polyhedron with generalized upper bounds is studied. It is an important substructure of many problems in which piecewise linear functions or semi-continuous variables must be modeled. Also, it is a generalization of knapsack with generalized upper bounds where continuous
variables are replaced for semi-continuous ones. A set of valid inequalities for this polyhedron are derived from multidimensional sequence independent lifting of seed inequalities of cover type. It is proved, that under some mild conditions this seed inequalities are facet-defining in the projected polyhedron, so, when
exact lifting functions are superadditive, final inequalities are facet-defining too.
Performance evaluation of these inequalities over a set of randomly generated instances shows that they are strong in the sense of root relative gap reduction.

Joint work with Daniel Espinoza.

 

2013-05-22:

Author: Mario Bravo, Universidad de Chile

Where: Sala 33, DII, 14.30-16.00

Title: Reinforcement learning with restrictions on the action space

Abstract: Consider a 2-player normal-form game which is repeated over time. We introduce an adaptive learning procedure, where the players only observe their own realized payoff at each stage. More precisely, we suppose that the agents don’t know their own payoff function, and have no information on the other players. Furthermore, we assume that they have restrictions on their own action space in the sense that, at each stage, their choice is limited to a subset of their action set. We prove that the empirical distributions of play converge to the set of Nash equilibria for zero-sum, potential games and games where one player has two actions. Our analysis relies on recent results on stochastic approximation obtained by Benaim and Raimond (2010).

Joint work with Mathieu Faure (Aix-Marseille)

 

2013-05-15:

Author: José Verschae, Universidad de Chile

Where: Sala 33, DII, 14.30-16.00

Title: Dual techniques for scheduling on a machine with varying speed

Abstract: I will present two types of problems related to scheduling on a machine of varying speed. In a static model, the speed function is (through an oracle) part of the input and we ask for a schedule minimizing the sum of weighted completion times. In a dynamic model, deciding upon the speed is part of the scheduling problem and we are interested in the tradeoff between scheduling cost and speed-scaling cost, that is energy, consumption.
I will shortly introduce the problem and show how it can be interpreted as a problem of minimizing a generalized global cost function on a unit speed machine. After, I’ll present the main ideas of a PTAS for the static and dynamic cases. Instead of focusing in the technical details, I will try to give intuition and explain how the notion of dual schedules can be used to derive such a result. Our results are best possible since this problem is strongly NP-hard. I will also mention other complexity results and more efficient algorithms for special cases.

This is joint work with Nicole Megow.

 

2013-05-08:

Author: Martin Matamala, Universidad de Chile

Where: Sala 33, DII, 14.30-16.00

Title: Etiquetados antimágicos universales

Abstract: Una función inyectiva que asigna enteros positivos a las aristas de un grafo se llama etiquetado de aristas. Cada etiquetado de aristas induce un etiquetado de vértices cuyo valor en un vértice dado es la suma de las etiquetas de todas las aristas incidentes con este vértice. Un etiquetado de aristas es antimágico si el etiquetado inducido en los vértices es inyectivo. Un grafo G con m aristas se dice antimágico universal si para cada conjunto de m enteros positivos, el grafo tiene un etiquetado antimágico con ese conjunto de etiquetas.

En esta charla se presentarán las ideas que permiten demostrar que todo grafo con el máximo grado 2, n-1 y n-2 es antimágico universal.

Trabajo en colaboración con José Zamora.

 

2013-04-24:

Author: András Sebő, CNRS, Laboratoire G-SCOP, Grenoble, France

Where: Sala 33, DII, 14.30-16.00

Title: Gaps

Abstract:The difference between the optimal integer primal and dual solutions of a linear program is the duality  gap.  After some examples including conjectures and recent results  we turn our attention to a purely graph-related question:  the duality gap of the fractional stable set polytope (described by clique inequalities) of a graph, in a reformulation to a suitable  extremal  graph theory context ignoring polyhedra :

What is the maximum difference on graphs with n vertices, between the minimum number of cliques covering the vertices of a graph and its maximum stable set (joint work with András Gyárfas and Nicolas Trotignon, 2012). The solution of this problem is based on interesting interplays between Ramsey numbers and matchings.

The subject is full of mysteries that will be shared with the audience through  open questions.

 

2013-04-17:

Author: Alberto Marchetti-Spaccamela, Sapienza University of Rome, Italy

Where: Sala 33, DII, 14.30-16.00

Title: Combinatorial Optimisation Problems in Real Time Scheduling

Abstract: Real-time scheduling, a central problem in critical embedded systems, consists in determining the sequence of execution of tasks with deadlines guaranteeing the timing constraints imposed by the surrounding physical system. The main difference between the problems studied in real-time scheduling and traditional scheduling theory is the focus that the first places on recurrent workloads. Namely, a real-time system is usually modeled as a finite collection of independent recurring tasks, each of which generates a potentially infinite sequence of jobs arriving over time that must be completed between its arrival time and its deadline. Different formal models for recurring tasks assume different restrictions on the values of the parameters of jobs generated by each task.

I will focus on the the sporadic task model that is one of the most studied models. A sporadic task i is represented as a 3-tuple (C(i), D(i), T(i)), a worst-case execution time C(i), a relative deadline D(i), and a period T(i). A task generates a possibly infinite sequence of jobs: successive jobs of task i arrive at least T(i) time units apart, with each job having an execution requirement of C(i) and a deadline D(i) time units after its arrival time. A sporadic task system S is comprised of several such sporadic tasks; clearly any sporadic task system may generate infinitely many different collections of jobs each one with possibly infinite many jobs.

A sporadic task system S is said to be feasible if a schedule exists for every collection of job arrivals that may legally be generated by S. For a given scheduling algorithm A, S is said to be A-schedulable if algorithm A meets all deadlines when scheduling every collection of job arrivals that may legally be generated by S.

I will discuss two examples of questions to show the richness in combinatorial challenges of real time scheduling and how known techniques from combinatorial optimisation can be successfully applied.

 

2013-04-12:

Author: Flavia Bonomo, UBA (Argentina).

Where: Sala 31, DII, 16.15-17.45

Title: Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem

Abstract: The Double Traveling Salesman Problem with Multiple Stacks is a vehicle routing problem in which pickups and deliveries must be performed in two independent networks. The items are stored in stacks and repacking is not allowed. Given a pickup and a delivery tour, the problem of checking if there exists a valid distribution of items into s stacks of size h that is consistent with the given tours, is known as Pickup and Delivery Tour Combination (PDTC) problem.

In this work, we show that the PDTC problem can be solved in polynomial time when the number s of stacks is fixed but the size of each stack is not. We build upon the equivalence between the PDTC problem and the bounded coloring (BC) problem on permutation graphs: for the latter problem, s is the number of colors and h is the number of vertices that can get a same color. We show that the BC problem can be solved in polynomial time when s is a fixed constant on co-comparability graphs, a superclass of permutation graphs. To the contrary, the BC problem is known to be hard on permutation graphs when h > 5 is a fixed constant, but s is unbounded.

Furthermore, we will show some results on a graph parameter called “thinness” that plays a crucial role in the design of the polynomial-time algorithm,

Joint work with Gianpaolo Oriolo (Università di Roma “Tor Vergata”, Italia) and Sara Mattia (IASI-CNR, Italia).

This is joint work with Shi Li.

 

2013-04-10:

Author: Ola Svensson, EPFL (Switzerland).

Where: Sala 33, DII, 14.30-16.00

Title: Approximating k-Median via Pseudo-Approximation

Abstract: k-median is the problem where we wish to open k facilities so as to minimize the average distance each client has to its closest opened facility. The lack of progress on this central problem compared to facility location (a close relative) is partly due to the difficulty of handling the hard
constraint that at most k facilities are allowed to be opened.

In this talk we shall see that we can relax this constraint into a soft constraint with a “violation-dependent” increase in the runtime. This gives a novel point of view for addressing k-median that allows us to give an algorithm that achieves an approximation guarantee of 1+√3 improving upon the decade-old ratio of 3.

This is joint work with Shi Li.

 

2013-03-27:

Author: Neil Olver, MIT.

Where: Sala 33, DII, 14.30-16.00

Title: Pipage rounding with semidefinite constraints

Abstract: Pipage rounding is a technique for rounding a fractional point of a matroid polytope (e.g., a point in the spanning tree polytope of a graph) to an integral point (e.g., a spanning tree) in a way that has a number of nice properties. I will talk about a generalization of this to a setting involving matrices and a soft semidefinite constraint. This has applications to, e.g., obtaining a “spectrally thin” tree in a graph. This is a spanning trees whose Laplacian is not “too big” compared to the Laplacian of the original graph, a strengthening of the notion of (cut) thin trees which are not “too big” across any cut of the graph.

I will spend a good fraction of the talk discussing background about matrix versions of classical concentration inequalities (like Chernoff bounds), and an open question involving negatively correlated sums of matrix-valued random variables.
(Joint work with Nick Harvey.)

 

2013-03-15:

Author: Ambros Gleixner, Zuse Institute Berlin.

Where: Sala 31, DII, 16.15-17.45

Title: Recent Advances in Solving MINLPs with SCIP

Abstract: State-of-the-artsolversforgenericmixed-integernonlinearpro- gramming utilize a linear relaxation within a branch-and-cut search. We will present new algorithmic techniques that help to improve the performance and robustness of various components of the solution al- gorithm: more accurate LP solutions by iterative refinement; propa- gation of Lagrangian variable bounds learnt from optimization-based bound tightening; and the exploitation of so-called covers (small- est sets of variables that render the problem linear when fixed) for primal heuristics and branching strategies. The computational im- pact of these methods is evaluated within the MINLP solver SCIP. This includes joint work with Timo Berthold, Daniel E. Steffy, Stefan Weltge, Kati Wolter, and Stefan Vigerske.

 

2013-01-23:

Author: Panayotis Mertikopoulos, CNRS researcher at Labora- toire dInformatique de Grenoble

Where: Sala 33, DII.14.30-16.00.

Title: Entropy-driven dynamics and algorithms for learning in games

Abstract: Starting from a heuristic learning scheme in strategic n-person games, we derive a class of entropy-driven continuous-time dynam- ics whose discretization yields an adaptive learning process that only requires players to be able to observe their in-game payoffs. The continuous-time dynamics satisfy a variant of the folk theorem of evolutionary game theory with the concept of Nash equilibrium re- placed by that of a Quantal Response Equilibrium; in particular, in the case of potential games, it is shown that the dynamics converge to perturbed (quantal) approximations of strict Nash equilibria. Mo- tivated by applications to traffic engineering, we then employ tech- niques from the theory of stochastic approximation to show that the resulting discrete-time learning algorithms retain this property, even in the presence of noisy/delayed observations and/or asynchronous updates.

 

2013-01-16:

Author: Tobias Harks, Masstricht University

Where: Sala 33, DII, 14:30-16:00

Title: Resource buying games

Abstract: In resource buying games, players jointly buy a subset of a given resource set. Each player has a predefined family of subsets of resources from which she needs at least one to be available. However, a resource is only available if the sum of payments of all players cover the load-dependent cost of that resource. A strategy of a player is a tupel consisting of one of her resource sets together with a payment vector indicating how much she is willing to contribute towards the purchase of each resource. During the talk, we study the existence and computability of pure Nash equilibria (PNEs) in resource buying games. Resource buying games reduce to connection games in the special case where the costs are fixed and the players resource sets are network-paths connecting two player-specific terminals. While there exist very simple connection games without PNE, we will see that PNEs exist and can be efficiently computed if each players strategy set is the base set of a matroid and the marginal cost of each resource is monotone.

 

2013-01-11: Seminario conjunto AGCO + Matemáticas Discretas

Author: Mark Braverman, Princeton University.

Where: Sala 33, DII, 16:15-17:45

Title: An introduction to information complexity

Abstract: The (two party) information complexity of a function F(X,Y) measures the least amount of information that Alice who holds X and Bob who holds Y need to reveal to each other about their inputs in order to compute F. While this complexity measure is interesting in its own right – for example in the context of information theoretic security, it is also very useful in studying the communication complexity of problems. We will introduce information complexity, and discuss some of its properties and connections to communication complexity. No prior background will be assumed.

 

2013-01-9:

Author: Christian Reitwiessner, U. Técnica Federico Santa María

Where: Sala Multimedia CMM, 6to piso, 14:30-16:00

Title: Necklace Splitting and Multiobjective Optimization

Abstract: Necklace splitting is an area of combinatorics applied by thieves: The general task is to cut a necklace containing various gems of different values stolen by a group of k thieves into k equally valuable parts – with as few cuts as possible. There are even more sophisticated variations of this setting, all with rather surprising solutions. Although they are non-constructive, these results can be applied to obtain a multiobjective polynomial-time approximation scheme for the (multiobjective) maximum matching problem. Furthermore, this scheme can again be combined with another necklace splitting result to improve the deterministic approximation for the (multiobjective) maximum traveling salesperson problem.