## 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

Projects:
I am the lead researcher of:

International collaboration project between University of Chile and Max Planck Institute, Conicyt PII20150140 Fast Approximation Algorithms for Massive Data Sets (2016--2018).

Fondecyt Project 1181180, Approximation And Online Algorithms For Optimization On Matroids, Matchings And Independence Systems (2018-2022)

Older projects: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)

My research interest are Combinatorics, Algorithms and Combinatorial Optimization.

From August 2012 to August 2013 I was a Postdoc at the
Combinatorial Optimization & Graph Algorithms Group (COGA)
of TU-Berlin, in Berlin, Germany.
This postdoc position was part of the Research Training Group Methods for Discrete Structures coorganized by the three Berlin Universities:
TU-Berlin, FU-Berlin and
HU-Berlin.

I received a PhD in Mathematics in 2011 at MIT, under the supervision of Professor Michel Goemans.

I am a Mathematical Engineer. 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

## Research

### In progress.

- Independent sets and hitting sets of bicolored rectangular families (with Claudio Telha).

(submitted, 2018).

Conference version titled "Jump Number of Two-Directional Orthogonal Graphs". In Proc. of the 15th Conference on Integer Programming and Combinatorial Optimization, LNCS 6655, 389-403, 2011.

Extended version (ARXIV) IPCO 2011 Proceedings - IPCO slides - Seminario Matematicas Discretas, U.Chile.

### Journals and Conferences

- Strong Algorithms for the Ordinal Matroid Secretary Problem (with Victor Verdugo and Abner Turkieltaub).

Proc. of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2018), pp. 715--734, 2018.

ARXIV - SODA 2018 Proceedings - . - Symmetry exploitation for Online Machine Covering with Bounded Migration (with Waldo Gálvez and José Verschae).

To appear in European symposium on algorithms (ESA2018)

ARXIV. - Robust randomized matchings (with Jannik Matuschke and Martin Skutella).

Journal Version: Math. Oper. Res. 43(2): 675-692 (2018)

Proc. of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2015), pp. 1904--1915, 2015.

Math of OR DOI - ARXIV - SODA 2015 Proceedings - SODA SLIDES. - LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design (with
Zachary Friggstad, Mohammad R. Salavatipour and Mohsen Rezapour)

Journal Version: To appear in Algorithmica (2018)

Proc. of the 14th International Symposium on Algorithms and Data Structures (WADS2015), LNCS 9214, pp. 373--385, 2015.

WADS 2015 Proceedings - On guillotine cutting sequences (with Fidaa Abed, Parinya Chalermsook, José Correa, Andreas Karrenbauer, Pablo Pérez-Lantero and Andreas Wiese)

Proc. of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX2015), LIPIcs 40, pp. 1--19, 2015.

APPROX 2015 Proceedings - 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 . - 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 - 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. - Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays (with Marcos Kiwi)

Combinatorics, Probability and Computing, 24:special issue 1, 2015.

CPC DOI - A preprint entitled "Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs" is available in the ARXIV - Advances on Matroid Secretary Problems: Free Order Model and Laminar Case (with Patrick Jaillet and Rico Zenklusen)

Proc. of the 16th Conference on Integer Programming and Combinatorial Optimization, LNCS 7801, pp. 254-265, 2013. IPCO 2013 Proceedings - EXTENDED ARXIV version - IPCO slides - Expanded slides@ULB. - 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. - 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): Proc. of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms 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)

European Journal of Combinatorics Vol. 29:5, pp. 1160-1172. 2008.

EJC 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

Engineering Students: Christian von Borries (2014), Émilien García (2016),Master Student: Arturo Merino (current), Abner Turkieltaub (2017), Waldo Gálvez (co-supervised, 2015). Omar Larré (co-supervised, 2012)

## Teaching

### Engineering School, University of Chile

#### Current

MA1101 - Introduction to Algebra. 2018-1. MA4702 - Mixed Integer Programming: Theory and Laboratory. 2018-1.#### Past

MA6150 - Approximation Algorithms (2017-2).MA5201 - Calculability and Computational Complexity 2017-1

MA6150 - Approximation Algorithms 2015-2.

MA4702 - Mixed Integer Programming: Theory and Laboratory. 2015-1.

MA3705 - Combinatorial Algorithms (ex. Combinatorial Optimization). 2014-2.

MA4701 - Combinatorial Optimization. 2013-2.

MA4606 - Combinatorics. 2015-1 2014-1.

MA1101 - Introduction to Algebra. 2016-2. 2016-1. 2014-1. 2012-1.

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.