About me
I am an Associate Professor at the Mathematical Engineering Department of the University of Chile.
I am also the Academic Chair (Jefe Docente) of the Mathematical Engineering Department.
I am an associated researcher in the Center for Mathematical Modeling
My research interest are Combinatorics, Algorithms and Combinatorial Optimization.
Previously (2012-2013) I was a Postdoc at the Combinatorial Optimization & Graph Algorithms Group (COGA) of TU-Berlin, in Berlin, Germany.
I received a PhD in Mathematics in 2011 at MIT, under the supervision of Professor Michel Goemans.
I did my undergraduate studies in the Mathematical Engineering Department of the University of Chile.
You can find me at:Mathematical Engineering Department
Universidad de Chile
Beauchef 851, DIM, Fifth Floor,
Santiago, Chile
Projects and Grants.
I am the lead researcher of: Fondecyt Project 1181180.
Approximation And Online Algorithms For Optimization On Matroids, Matchings And Independence Systems (2018-2022)
Older projects:
FONDEF IDeA ID18I10250 on VRP.
Robust management for the dispatch of products from multiple warehouses with variable time windows (2018-2021)
International collaboration project between University of Chile and Max Planck Institute. Conicyt PII20150140.
Fast Approximation Algorithms for Massive Data Sets (2016--2019).
Associated researcher of the former Núcleo Milenio project Information and Coordination in Networks
Fondecyt Project 11130266, Approximation Algorithm for Incremental Selection Problems (2013--2017)
Research
Articles
- Sample-driven optimal stopping: From the secretary
problem to the i.i.d. prophet inequality (with José Correa, Andrés Cristi and Boris Epstein).
Journal version: Mathematics of Operations Research (2023).
MOR DOI - ARXIV - The Two-Sided Game of Googol and Sample-Based Prophet Inequalities (with José Correa, Andrés Cristi and Boris Epstein).
Journal version: Journal of Machine Learning Research 23(113):1−37, 2022.
Conference version: SODA 2020. pp 2066--2081.
JMLR - SODA 2020 Proceedings DOI - ARXIV - Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle. (with Francisco Sanhueza and Waldo Gálvez).
Conference version: WAOA 2021
WAOA Proceedings DOI ARXIV - Avoiding artifacts when varying the number of species in ecological models. (with Pablo Moisset de Espanes and Rodrigo Ramos-Jiliberto)
Ecology Letters 24 (9), 1976-1987. 2021.
Ecology Letters DOI - Authorea - Independent Sets and Hitting Sets of Bicolored Rectangular Families. (with Claudio Telha).
Journal version: Algorithmica 83(6): 1918-1952. 2021.
The conference version of this paper was titled "Jump Number of Two-Directional Orthogonal Ray Graphs." and appeared in IPCO 2011. pp 389--403
Algorithmica DOI - IPCO proceedings DOI - ARXIV - Strong Algorithms for the Ordinal Matroid Secretary Problem. (with Victor Verdugo and Abner Turkieltaub).
Journal version: Mathematics of Operations Research 46(2): 642-673. 2021.
Conference version: SODA 2018, pp. 715--734, 2018.
Math of OR DOI - ARXIV - SODA 2018 Proceedings - ISMP 2018 slides. - The Multiple Traveling Salesman Problem on Spiders. (with Pedro Pérez-Escalona, Ivan Rapaport and Ian Vidal).
SOFSEM 2021. pp 337--348.
SOFSEM 2021 Proceedings DOI - Symmetry Exploitation for Online Machine
Covering with Bounded Migration (with Waldo Gálvez and José Verschae).
Journal Version: ACM Trans. Algorithms 16(4): 43:1-43:22. 2020
Conference Version: ESA 2018. LIPIcs 112, pp. 32:1-32:14. 2018
ACM Trans. Algorithms DOI - ESA Proceedings DOI - ARXIV - The minimum cost query problem on matroids with
uncertainty areas (with Arturo Merino).
ICALP 2019. LIPIcs 132, pp. 83:1--83:14, 2019.
ICALP 2019 Proceedings DOI - ARXIV - LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design (with
Zachary Friggstad, Mohammad R. Salavatipour and Mohsen Rezapour)
Journal Version: Algorithmica. 81-3, pp.1075-1079, 2019.
Conference Version: WADS 2015, LNCS 9214, pp. 373--385, 2015.
Algorithmica DOI - WADS 2015 Proceedings DOI - Robust randomized matchings (with Jannik Matuschke and Martin Skutella).
Journal Version: Mathematics of Operations Research. 43-2, pp. 675-692, 2018.
Conference Version: SODA 2015, pp. 1904--1915, 2015.
MOOR DOI - SODA 2015 Proceedings - ARXIV - SODA SLIDES. - On guillotine cutting sequences (with Fidaa Abed, Parinya Chalermsook, José Correa, Andreas Karrenbauer, Pablo Pérez-Lantero and Andreas Wiese)
APPROX 2015, LIPIcs 40, pp. 1--19, 2015.
APPROX 2015 Proceedings - Improved Analysis of a Max Cut Algorithm Based on Spectral Partitioning.
SIAM Journal on Discrete Mathematics, 29:1, pp. 256--268, 2015.
SIDMA DOI - ARXIV. - Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line: Algorithms and Complexity (with José Correa, Laurent Feuilloley and Pablo Pérez-Lantero).
Journal Version: Discrete & Computational Geometry. 53-2, pp. 344-365, 2015.
Conference Version: LATIN2014, titled "Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line", LNCS 8392, 2014, pp. 35-46.
DCG DOI - LATIN2014 - ARXIV - Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays (with Marcos Kiwi)
Combinatorics, Probability and Computing, 24:special issue 1, 2015.
CPC DOI - ARXIV - TSP Tours in Cubic Graphs: Beyond 4/3
(with José R. Correa and Omar Larré)
Journal Version: SIAM J. Discrete Math. 29-2, pp. 915-939, 2015. Conference Version: ESA 2012, LNCS 7501, 790-801, 2012.
SIDMA DOI - ESA 2012 Proceedings - ARXIV - ESA slides . - A simple PTAS for Weighted Matroid Matching on Strongly Base Orderable Matroids.
Journal Version: Discrete Applied Mathematics, 164:2, pp. 406--412, 2014.
Conference Version: LAGOS2011. Electronic Notes in Discrete Mathematics Vol. 37, 75-80, 2011.
DAM DOI - ENDM DOI - ARXIV - LAGOS slides . - On the rate of convergence of Krasnoselskii-Mann iterations and their connection with sums of Bernoullis (with Roberto Cominetti and José Vaismann)
Israel Journal of Mathematics, 199:2, pp 757-772, 2014.
IJM DOI - ARXIV version. - Advances on Matroid Secretary Problems: Free Order Model and Laminar Case (with Patrick Jaillet and Rico Zenklusen)
IPCO 2013. LNCS 7801, pp. 254-265, 2013. IPCO 2013 Proceedings DOI - ARXIV - IPCO slides - Expanded slides@ULB. - Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations (with Michel X. Goemans)
SIAM Journal of Discrete Mathematics 27:2, pp. 1123-1145, 2013.
SIDMA DOI - ARXIV version - AGCO seminar Slides. - Matroid Secretary Problem in the Random Assignment Model.
Journal Version: SIAM Journal on Computing, 42:1, pp. 178-211, 2013.
Conference Version: SODA2011. pp. 1275-1284, 2011.
SICOMP DOI - SODA 2011 Proceedings DOI - ARXIV - SODA slides - SIAM OP11 Slides. - On a Speculated Relation Between Chvátal-Sankoff Constants of Several Sequences (with Marcos Kiwi)
Combinatorics, Probability and Computing 18:4, pp. 517-532. 2009.
CPC DOI - ARXIV.
- Block Transitivity and Degree Matrices (with Jirí Fiala)
Journal Version: European Journal of Combinatorics Vol. 29:5, pp. 1160-1172. 2008.
Conference Version: 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. Special Issue in Electronic Notes in Discrete Mathematics, 2007, vol. 28, pp. 77–82.
EJC DOI - ENDM DOI
Theses
- Contributions on Secretary Problems, Independent Sets of Rectangles and Related Problems.
PhD Thesis. Department of Mathematics, Massachusetts Institute of Technology. 2011.
You can access a local copy here. Here are also some slides from my defense. - Variantes Aleatorias de la Subsecuencia Común Más Grande.
Mathematical Engineering Thesis. Departamento de Ingeniería Matemática, Universidad de Chile. 2006.
This is my undergraduate thesis. It was written in spanish under the supervision of Marcos Kiwi.
You can access a local copy here.
Training
Engineering Students (year, thesis topic):3. Sebastián Rebolledo (current; online selection on independent systems)
2. Christian von Borries (2014, online maximum matching on bipartite graphs - Repository )
1. Émilien García (2016, secretary problems with forbidden selection times - Repository )
Master Students (year, thesis topic)
14. Fernanda Gabrielli (current, stable matchings with uncertainty)
13. Cristian Palma (current, submodular welfare and machine balancing)
12. Felipe Valdevenito (current, single-choice and matroid secretary problems with oracular advice)
11. Javier Marinkovic (current, online maximum weight matching with samples)
10. Juan Pablo Donoso (2022, fractional multiple knapsack with concave gains - Repository )
9. Kevin Contreras (2022, capacitated sum-of-radii supplier on the line - Repository )
8. Ricardo Arancibia (2021, minimum k-lateness on one machine - Repository )
7. Francisco Sanhueza (2021, vertex-connectivity augmentation on the cycle - Repository )
6. Tomás Martínez (2020 co-supervised w/A. Wiese, Stackelberg minimum spanning tree on complete graphs - Repository )
5. Ian Vidal (2019 co-supervised w/I. Rapaport, multiple TSP on spiders - Repository )
4. Arturo Merino (2018, minimum cost query on matroids with uncertainty - Repository )
3. Abner Turkieltaub (2017, strong variants of the matroid secretary problem - Repository )
2. Waldo Gálvez (2015 co-supervised w/J. Verschae, online machine covering with bounded migration - Repository )
1. Omar Larré (2012 co-supervised w/J. Correa, TSP in cubic graphs - Repository )
Postdoctoral hosting (MPII-Uchile collaboration Project): Krzysztof Fleszar (2016-2017), Kevin Schewior (2016-2017), Andreas Abels (2017-2018), Tim Oosterwijk (2018).
Teaching
Engineering School, University of Chile
Current
MA5201 - Calculability and Computational Complexity 2023-1.Past
MA6150 - Approximation Algorithms 2021-2.2019-2. 2017-2. 2015-2.
MA4702 - Mixed Integer Programming: Theory and Laboratory. 2021-1. 2020-1. 2018-1. 2016-1. 2015-1.
MA5201 - Calculability and Computational Complexity 2017-1.
MA3705 - Combinatorial Algorithms (ex. Combinatorial Optimization) 2020-2. 2014-2.
MA4701 - Combinatorial Optimization 2013-2.
MA4606 - Combinatorics 2022-2 2019-2 2018-2 2016-1 2015-1 2014-1.
MA1101 - Introduction to Algebra. 2022-2. 2022-1. 2019-1. 2018-1. 2016-2. 2016-1. 2014-1. 2012-1.
MA1102 - Linear Algebra. 2021-2.
2015-2.
MA1001 - Introduction to Calculus. 2013-2. 2011-2.
Schools
Lecturer for the course titled Iterative Rounding in Combinatorial Optimization (Redondeo Iterativo en Optimización Combinatorial) at the XIII Spring School CMM-DIM, 2013 - Slides in Spanish.Lecturer for the short course titled Packing and Covering: Blocking duality. (Empaquetamientos y cubrimientos: Dualidad de bloqueo) at the 3rd Winter School on Discrete Mathematics organized by Núcleo Milenio project Information and Coordination in Networks -- Slides in Spanish.
Other courses
In January 2023 I taught an Introductory Course of Combinatorics to middle and high school students in EdVUchile.
I have taught an Introductory Course of Combinatorics for high school teachers in Santiago, Chile. Versions 2007, 2008, 2009 and 2013. These courses were taught as part of the Campeonato Escolar de Matemáticas. CMAT, a math competition for high school students in Chile.
I have also organized courses for math students and math professors from 2014 - 2017 as part of the collaboration project between CMAT and Millenium Nucleus Information and Coordinations in Networks.