Seminario AGCO

The ACGO seminars are held every wednesday as part of an effort of a group of researchers around the topics of Algorithms, Combinatorics, Game Theory and Optimization. Our team consists of researchers in different disciplines and from several chilean universities. If you are interested in giving a talk or receiving the announcements of the seminars, please send us an email to jverschae followed by Webpage:

14:30 hrs.
Andrés Cristi. U Chile
A Near Optimal Mechanism For Energy Aware Scheduling
República 779 B, Sala 3er Piso.
14:30 hrs.
José Verschae. PUC
Symmetry And Hierarchies In Approximation Algorithms: Some Open Problems
República 779 B, Sala 3er Piso.
14:30 hrs.
Martin Matamala . Dim, U Chile.
An Extension Of (Perfect) Matching
República 779 B, Sala 3er Piso.
14:30 hrs.
Antoine Hochart. U Chile
Ergodicity Of Zero-Sum Stochastic Games
República 779 B, Sala 3er Piso.
14:30 hrs.
José Fuentes. Dcc, U Chile.
Fast And Compact Planar Embeddings
República 779 B, Sala 3er Piso.
14:30 hrs.hrs.
Miquel Oliu Barton. Université Paris-Dauphine.
The Unknown Stochastic Game
República 779 B, Sala 3er Piso.
Carlos Ochoa. U Chile
Synergistic Solutions On Multisets
Av República 779 B (Beauchef), Sala 3er Piso.
Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size $n$ and number of queries $q$ fixed. Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to further refine this approach and take advantage all at once of the structure (i.e., the multiplicities of the elements), some notions of local order (i.e., the number and sizes of runs) and global order (i.e., the number and positions of existing pivots) in the input; and of the structure and order in the sequence of queries. Our main result is a synergistic deferred data structure which outperforms all solutions in the comparison model that take advantage of only a subset of these features. As intermediate results, we describe two new synergistic sorting algorithms, which take advantage of some notions of structure and order (local and global) in the input, improving upon previous results which take advantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) in the input; and one new multiselection algorithm which takes advantage of not only the order and structure in the input, but also of the structure in the queries.
Marc Schroder. U Chile
Claim Games For Estate Division Problems
Republica 779B, Sala P3, 3rd floor.

The estate division problem, also known as bankruptcy problem, concerns the issue of dividing an estate among a group of claimants when the sum of entitlements exceeds the size of the estate. This problem was formally introduced by O’Neill (1982), after which most of the literature focused on comparing different solution rules by means of their properties. We approach the problem strategically and analyse the claim game.

Kevin Schewior. U Chile / Max Planck Institute For Informatics
Chasing Convex Bodies
U Chile, Campus Beauchef, República 779 B, Sala 3er Piso
Krzysztof Fleszar. U Chile
Maximum Disjoint Paths: New Algorithms Based On Tree-Likeness
República 779 B, Sala 3er Piso (Beauchef)

Maximum Edge Disjoint Paths is a classical NP-hard problem of finding a maximum-size subset from a given set of k terminal pairs that can be routed via edge-disjoint paths.

One of the big open problems in approximation algorithms is to close the gap between the best known approximation upper bound of $\sqrt{n}$ (Chekuri et al. (2006)) and the best known lower bound of $2^{\sqrt{\log n}}$ (Chuzhoy et al. (2016)). In their seminal paper, Raghavan and Thompson (Combinatorica, 1987) introduce the technique of randomized rounding for LPs; their technique gives an O(1)-approximation when edges may be used by $O(\log n / \log\log n)$ paths.

In this talk, I introduce the problem and present two of our algorithms (ESA 2016) that strengthen the fundamental results above. They provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest.

- An $O(\sqrt{r} \log{kr})}$-approximation algorithm. Up to a logarithmic factor, it strengthens the best known ratio $\sqrt{n}$ due to Chekuri et al., as $r \le n$.

- An $O(1)$-approximation algorithm with congestion bounded by $O(\log{kr} / \log\log{kr})$, strengthening the bound obtained by the classic approach of Raghavan and Thompson.

At the end, an open problem will be stated.

Saeed Hadikanlo. Univ. de Paris 9
Learning In Nonatomic Anonymous Games: Application To First Order Mean Field Games
República 779 B, Sala 3er Piso.
We introduce a model of anonymous games where the actions are chosen from possibly player dependent sets. We propose several learning procedures similar to the well-known Fictitious Play and Online Mirror Descent and prove their convergence to equilibrium under the classical monotonicity condition. Typical examples are First Order Mean Field Games.
Cristobal Guzman. PUC
Statistical Query Algorithms For Stochastic Convex Optimization
U Chile (Beauchef), Av Republica 701, Sala 33.
Statistical query (SQ) algorithms are the class of learning algorithms that can be implemented using approximate expectations of any given function of the input distribution, as opposed to direct access to i.i.d. samples. This computational model has a number of applications, ranging from noise-tolerant learning to differential privacy, and it has been used to obtain unconditional lower bounds on conjectured hard problems over distributions.
In this talk I will give an introduction to the theory of SQ algorithms, and we will see some recent developments in the case of stochastic convex optimization. Our main contribution is establishing nearly optimal SQ algorithms for mean vector estimation (this includes stochastic linear programming), which serves as a basis to obtain SQ versions of various gradient-type and polynomial time algorithms for stochastic convex optimization. Time permitting, I will show some consequences of our results for learning of halfspaces, differential privacy, and proving unconditional lower bounds on the power of convex relaxations for random constraint satisfaction problems.

This talk is based on joint work with Vitaly Feldman and Santosh Vempala, to appear in SODA 2017. 
Krzysztof Fleszar, Marc Schroder, Kevin Schewior. U Chile
Sesión de Problemas Abiertos
PUC, San Joaquín, Ciencias de la Salud SC403
Se darán 3 mini-charlas de aproximadamente 15 min cada una para después trabajar en los problemas. 

Krzysztof Fleszar: Edge Disjoint Paths
Marc Schroder: Negative prices in routing games
Kevin Schewior: Online Deadline Scheduling with Speed Augmentation
Fábio Botler. U Chile
Decomposing 8-Regular Graphs Into Paths Of Length 4
U Chile (Beaucheff). Av Republica 701, Sala 33
A T-decomposition of a graph G is a set of edge-disjoint copies of T in G that cover the edge set of G. Graham and Häggkvist (1989) conjectured that any 2\ell-regular graph G admits a T-decomposition if T is a tree with \ell edges. Kouider and Lonc (1999) conjectured that, in the special case where T is the path with \ell edges, G admits a T-decomposition D where every vertex of G is the end-vertex of exactly two paths of D, and proved that this statement holds when G has girth at least (\ell + 3)/2. In this talk we verify Kouider and Lonc’s Conjecture (and, consequently, Graham-Häggkvist’s Conjecture) for paths of length 4.
Monaldo Mastrolilli. Idsia, Suiza
High Degree Sum Of Squares Proofs/hierarchy For 0/1 Problems
U Chile (Beauchef), Av Republica 701, Sala 33
The Lasserre/Sum-of-Squares (SOS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy converges to the 0/1 polytope in n levels and captures the convex relaxations used in the best available approximation algorithms for a wide variety of optimization problems.

In this talk I will give a gentle introduction of the SOS framework for 0/1 problems from a more general point of view.

I will point it out that this more general definition is needed for certain class of problems e removes some of the weakness of the standard SOS approach.
Bruno Ziliotto. Paris Dauphine University (Cnrs)
Limit Value In Zero-Sum Stochastic Games
U Chile (Beauchef) Av Republica 701, Sala 33
We consider a model of repeated game involving two adversary players, and where the state of nature is imperfectly observed. An old conjecture by Mertens (1986) predicted that in this model, when the game is repeated over and over, the optimal payoff of players should converge. We provide a counterexample to this conjecture.

No game theory prerequisite of any kind is needed to understand the talk.
Lin Chen. Hungarian Academy Of Sciences
N-Fold Integer Programming And Scheduling
U Chile (Beauchef), Av República 701, Sala 33.

N-fold integer programming is shown to admit an $O(n^3)$ FPT time algorithm by Hemmecke, Onn and Romanchuck (Math. Programming 2013). Very recently, it is observed by Knop and Koutecky (arxiv:1603.02611v1, 2016) that it has a close relationship with the scheduling problem. Indeed, they show that $R||Cmax$ and $R||sum w_jC_j$ could be formulated as an n-fold integer programming, whereas an FPT time algorithm follows by choosing proper parameters. It also implies an 2^{O(1/\epsilon^2)}+O(n^3) time EPTAS for P||Cmax without using configuration ILP.

In this talk, I will talk about the basic idea of the FPT time algorithm for n-fold integer programming and its relationship with scheduling. I will then talk about one of my recent work (with Daniel Marx), which extends n-fold integer programming to a more general form. Using this general form, we derive FPT algorithms for routing on a tree.

Jackie Zhang. U Chile
Vagueness In Multidimensional Proposals
U Chile (Beauchef), Republica 701, Sala 33
I study how the option of being vague shapes proposals in a delegation environment. Two agents compete for a decision maker (DM)’s approval to implement a multidimensional action. Based on their knowledge of the consequences of actions, agents propose their future actions but can be vague about any dimension. The DM, uncertain about the consequences of actions, chooses one of the agents to act. All players are known for their most desired consequences. It is shown that vagueness on the dimension on which one stands closer to the DM than his opponent (i.e. one’s advantageous dimension) preserves such an advantage, while preciseness on one’s advantageous dimension undermines it. Vagueness therefore tends to occur on agents’ advantageous dimensions.
Jannik Matuschke. Tu Munchen
Minimizing Congestion In Virtual Private Ring Networks
U Chile (Beauchef), Av. República 701, DII, Sala 33.
Given a network with a set of n terminals we want to setup a virtual private network (VPN) that allows communication between the terminals. For any two terminals, we have to decide on a route via which the two terminals communicate with each other. Our goal is to minimize the congestion of the resulting VPN, i.e., the worst-case load any link can receive in any possible communication profile between the terminals (a communication profile is a fractional matching on the terminals specifying how much data is transmitted between each pair).

We observe that for the case of ring networks, this problem is equivalent to bounding the size of a maximum matching in a sequence of graphs arising from iteratively inverting the incidence vectors of the terminals. We show how to construct a routing template of congestion n/3 by partitioning the terminals into three groups, and prove that this solution is optimal. We conjecture that a similar partitioning technique yields an optimal solution in the case that links have distinct capacities. However, if we allow the terminals to have distinct data demands, the problem becomes NP-hard.

This is joint work with Neil Olver and Kristóf Bérczi.
Pablo Pérez-Lantero, Usach.. Nucleo Milenio Información y Coordinación en Redes
The Intersection Graph Of The Disks With Diameters The Sides Of a Convex N-Gon
U Chile (Beauchef), Av. República 701, DII.
Given a convex polygon of n sides, one can draw n disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the undirected graph with vertices the n disks and two disks are adjacent if and only if they have a point in common. We prove that for every convex polygon this graph is planar. Particularly, for n=5, this shows that for any convex pentagon there are two disks among the five side disks that do not intersect, which means that K_5 is never the intersection graph of such five disks. For n=6, we then have that for any convex hexagon the intersection graph of the side disks does not contain K_3,3 as subgraph.