# 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 uc.cl. Webpage: http://www.dii.uchile.cl/acgo/seminar-acgo/

2018-03-21
14:30 hrs.
Tim Oosterwijk. U Chile.
Approximating Vector Scheduling
Av. República 701, Sala 33.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2018-03-14
14:30 hrs.
Bruno Zillotto. Ceremade, Paris Dauphine University.
Markov Decision Processes With Long Duration
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo
2018-01-24
14:30 hrs.
Martin Böhm. University of Birmingham, Charles University.
Nested Convex Bodies Are Chaseable
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2018-01-05
12:00 hrs.
Kurt Melhorn. Instituto Max-Planck de Informática
Markets and Fair Division of Goods
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2018-01-03
14:30 hrs.
Alfredo Torrico. Gatech
Robust Submodular Maximization: Offline and Online Algorithms
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-12-27
14:30 hrs.
Nicolas Sanhueza. University of Birmingham
An Asymptotic Bound for The Strong Chromatic Number
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-12-20
14:30 hrs.
Kevin Schewior. U Chile & Mpii.
The Itinerant List-Update Problem
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-12-13
14:30 hrs.
Bhalchandra D. Thatte. Ufmg, Brazil.
Subgraph Posets and Graph Reconstruction
República 779 B, Sala 2do Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-12-06
14:30 hrs.
Andreas Tönnis. U. Chile
The Temp Secretary Problem and Extensions
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-11-22
14:30 hrs.
Johannes Fischer. Tu Dortmund.
Simple, Fast and Lightweight Parallel Wavelet Tree Construction.
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-11-15
14:30 hrs.
Claudio Telha Cornejo, Core & Om Partners.. Core, UC Louvain
A Competitive Uncapacitated Lot-Sizing Game
República 779 B, Sala 3er Piso
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-10-11
14:30 hrs.
Andrés Cristi. U Chile
A Near Optimal Mechanism for Energy Aware Scheduling
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-10-04
14:30 hrs.
José Verschae. PUC
Symmetry and Hierarchies in Approximation Algorithms: Some Open Problems
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-09-27
14:30 hrs.
Martin Matamala . Dim, U Chile.
An Extension of (Perfect) Matching
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-09-13
14:30 hrs.
Antoine Hochart. U Chile
Ergodicity of Zero-Sum Stochastic Games
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-09-06
14:30 hrs.
José Fuentes. Dcc, U Chile.
Fast and Compact Planar Embeddings
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-08-30
14:30 hrs.hrs.
Miquel Oliu Barton. Université Paris-Dauphine.
The Unknown Stochastic Game
República 779 B, Sala 3er Piso.
http://www.dii.uchile.cl/acgo/seminar-acgo/
2017-05-17
14:30hrs.
Carlos Ochoa. U Chile
Synergistic Solutions on Multisets
Av República 779 B (Beauchef), Sala 3er Piso.
Abstract:
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.
2017-04-12
14:30hrs.
Marc Schroder. U Chile
Claim Games for Estate Division Problems
Republica 779B, Sala P3, 3rd floor.
Abstract:

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.

2017-03-29
14:30hrs.
Kevin Schewior. U Chile / Max Planck Institute for Informatics
Chasing Convex Bodies
U Chile, Campus Beauchef, República 779 B, Sala 3er Piso