About me

I am an Assistant Professor at the Mathematical Engineering Department of the University of Chile.

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

My e-mail address is:



News.

XV Summer School in Discrete Mathematics. January 6 to 10, 2020. Valparaiso, 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)

FONDEF IDeA ID18I10250 on VRP.
Robust management for the dispatch of products from multiple warehouses with variable time windows (2018-2022)


Older projects:

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

  • The Two-Sided Game of Googol and Sample-Based Prophet Inequalities (with José Correa, Andrés Cristi and Boris Epstein).
    Submitted, 2019.
    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
  • Symmetry Exploitation for Online Machine Covering with Bounded Migration (with Waldo Gálvez and José Verschae).
    ESA 2018. LIPIcs 112, pp. 32:1-32:14. 2018
    ESA Proceedings DOI - ARXIV
  • Strong Algorithms for the Ordinal Matroid Secretary Problem (with Victor Verdugo and Abner Turkieltaub).
    SODA 2018, pp. 715--734, 2018.
    ARXIV - SODA 2018 Proceedings - ISMP 2018 slides.
  • 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.



Students

Master Students: Juan Pablo Donoso (current), Tomás Martínez (current), Francisco Sanhueza (current).
Ian Vidal (2019, co-supervised), Arturo Merino (2018), Abner Turkieltaub (2017), Waldo Gálvez (co-supervised, 2015). Omar Larré (co-supervised, 2012)
Engineering Students: Christian von Borries (2014), Émilien García (2016),





Teaching

Engineering School, University of Chile

Current

MA6150 - Approximation Algorithms 2019-2.
MA4606 - Combinatorics 2019-2

Past

MA6150 - Approximation Algorithms 2017-2. 2015-2.
MA4702 - Mixed Integer Programming: Theory and Laboratory. 2018-1. 2016-1. 2015-1.
MA5201 - Calculability and Computational Complexity 2017-1.
MA3705 - Combinatorial Algorithms (ex. Combinatorial Optimization) 2014-2.
MA4701 - Combinatorial Optimization 2013-2.
MA4606 - Combinatorics 2018-2 2016-1 2015-1 2014-1.
MA1101 - Introduction to Algebra. 2019-1.
2018-1. 2016-2. 2016-1. 2014-1. 2012-1.
MA1102 - Linear Algebra. 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

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.

Conferences

Program Committee Member of LATIN 2018, WAOA 2015, LATIN 2014. Local Organizing Committee Member of IPCO 2013, The 16th Conference on Integer Programming and Combinatorial Optimization.