I am an associated researcher in the Center for Mathematical ModelingI am also an associated researcher of the Núcleo Milenio project Information and Coordination in Networks.
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
Mathematical Engineering Department
Universidad de Chile
Beauchef 851, DIM, Fifth Floor,
- Independent sets and hitting sets of bicolored rectangular families (with Claudio Telha).
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.
- 2D Rail Mounted Vehicle Scheduling with Non-Crossing Constraints (with Torsten J. Gellert)
In progress, 2014.
Journals and Conferences
- 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
- On the Integrality Gap of the Connected Facility Location with Buy-at-Bulk Edge Costs Problem (with
Zachary Friggstad, Mohammad R. Salavatipour and Mohsen Rezapour)
Proc. of the 14th International Symposium on Algorithms and Dat Structures (WADS2015), LNCS 9214, pp. 373--385, 2015.
WADS 2015 Proceedings
- Robust randomized matchings (with Jannik Matuschke and Martin Skutella).
Proc. of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2015), pp. 1904--1915, 2015.
SODA 2015 Proceedings - SODA SLIDES.
- 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.
- 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.
StudentsEngineering Students: Christian von Borries (2014), Émilien García (current), Waldo Gálvez (co-supervised, current).
Master Student: Omar Larré (co-supervised, 2012)
Engineering School, University of Chile
Current2015-1: MA4606 - Combinatorics. Go to u-cursos site.
2015-1: MA4702 - Mixed Integer Programming: Theory and Laboratory. Go to u-cursos site.
Past2014-2: MA3705 - Combinatorial Algorithms (equiv. to Combinatorial Optimization). Go to u-cursos site.
2014-1: MA4606 - Combinatorics. Go to u-cursos site.
2014-1: MA1101 - Introduction to Algebra. Go to u-cursos site.
2013-2: MA4701 - Combinatorial Optimization. Go to u-cursos site.
2013-2: MA1001 - Introduction to Calculus. Go to u-cursos site.
2012-1: MA1101 - Introduction to Algebra. Go to u-cursos site.
2011-2: MA1001 - Introduction to Calculus. Go to u-cursos site.
SchoolsLecturer 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.
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.
ConferencesProgram Committee Member of LATIN 2014, The 11th Latin American Theoretical INformatics Symposium.
Local Organizing Committee Member of IPCO 2013, The 16th Conference on Integer Programming and Combinatorial Optimization.
Random SlidesBelow there is a small collection of random slides I have made over the years.
Here are some slides of the informal SPAMS talk I gave titled "Who can write the Bigger Number?"
Here are the slides for another informal SPAMS talk I gave on Max-Min relations in Combinatorics.
Here are the slides for another SPAMS talk I gave on variations of the Secretary Problem.
These are the slides (pdf, odp) for the presentation I gave in 15.099, Special Seminar in Operations Research in Spring 2010 about the nice paper titled Matroid Matching: The Power of Local Search (DOI) by Jon Lee, Maxim Sviridenko and Jan Vondrák.