Rico Zenklusen

Orcid: 0000-0002-7148-9304

Affiliations:
  • ETH Zurich, Department of Mathematics, Switzerland


According to our database1, Rico Zenklusen authored at least 91 papers between 2007 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Better-than-$\frac{4}{3}$-approximations for leaf-to-leaf tree and connectivity augmentation.
Math. Program., September, 2024

Congruency-Constrained TU Problems Beyond the Bimodular Case.
Math. Oper. Res., 2024

Ghost Value Augmentation for k-Edge-Connectivity.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Single-Source Unsplittable Flows in Planar Graphs.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness.
J. ACM, August, 2023

Ghost Value Augmentation for k-ECSS and k-ECSM.
CoRR, 2023

Advances on Strictly Δ-Modular IPs.
CoRR, 2023

A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information.
Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

A Simple Combinatorial Algorithm for Robust Matroid Center.
Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid.
Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Advances on Strictly $\varDelta $-Modular IPs.
Proceedings of the Integer Programming and Combinatorial Optimization, 2023

2022
Reducing Path TSP to TSP.
SIAM J. Comput., June, 2022

A Framework for the Secretary Problem on the Intersection of Matroids.
SIAM J. Comput., 2022

An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint.
Math. Program., 2022

A technique for obtaining true approximations for k-center with covering constraints.
Math. Program., 2022

Better-Than-4/3-Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation.
CoRR, 2022

Local Search for Weighted Tree Augmentation and Steiner Tree.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Fair and Fast k-Center Clustering for Data Summarization.
Proceedings of the International Conference on Machine Learning, 2022

Streaming Submodular Maximization Under Matroid Constraints.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Submodular Maximization Subject to Matroid Intersection on the Fly.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Techniques for Generalized Colorful k-Center Problems.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021
Online Contention Resolution Schemes with Applications to Bayesian Selection Problems.
SIAM J. Comput., 2021

Streaming Submodular Maximization with Matroid and Matching Constraints.
CoRR, 2021

Bridging the gap between tree and connectivity augmentation: unified and stronger approaches.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture.
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

A Better-Than-2 Approximation for Weighted Tree Augmentation.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020
A new contraction technique with applications to congruency-constrained cuts.
Math. Program., 2020

Approximate multi-matroid intersection via iterative refinement.
Math. Program., 2020

2019
Firefighting on Trees Beyond Integrality Gaps.
ACM Trans. Algorithms, 2019

An Improved Analysis of Local Search for Max-Sum Diversification.
Math. Oper. Res., 2019

Submodular Maximization Through the Lens of Linear Programming.
Math. Oper. Res., 2019

Submodular Minimization Under Congruency Constraints.
Comb., 2019

A 1.5-Approximation for Path TSP.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants.
SIAM J. Discret. Math., 2018

Sublinear Bounds for a Quantitative Doignon-Bell-Scarf Theorem.
SIAM J. Discret. Math., 2018

The Submodular Secretary Problem Goes Linear.
SIAM J. Comput., 2018

k-Trails: recognition, complexity, and approximations.
Math. Program., 2018

Chain-constrained spanning trees.
Math. Program., 2018

Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix.
Math. Program., 2018

A Simple <i>O</i>(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem.
Math. Oper. Res., 2018

Improved approximation for tree augmentation: saving by rewiring.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
Hardness and approximation for network flow interdiction.
Networks, 2017

Matroids Are Immune to Braess' Paradox.
Math. Oper. Res., 2017

Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives.
Math. Oper. Res., 2017

Extension complexities of Cartesian products involving a pyramid.
Inf. Process. Lett., 2017

A strongly polynomial algorithm for bimodular integer linear programming.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Local Search for Max-Sum Diversification.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016
Refuting a conjecture of Goemans on bounded degree spanning trees.
Oper. Res. Lett., 2016

Online Contention Resolution Schemes.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Max-Sum Diversity Via Convex Programming.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
Congestion games viewed from M-convexity.
Oper. Res. Lett., 2015

Bulk-Robust combinatorial optimization.
Math. Program., 2015

Approximate dynamic programming for stochastic linear control problems on compact state spaces.
Eur. J. Oper. Res., 2015

An O(1)-Approximation for Minimum Spanning Tree Interdiction.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes.
SIAM J. Comput., 2014

Connectivity interdiction.
Oper. Res. Lett., 2014

New approaches to multi-objective optimization.
Math. Program., 2014

A Simple Order-Oblivious O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem.
CoRR, 2014

Time-Expanded Packings.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Stable Routing and Unique-Max Coloring on Trees.
SIAM J. Discret. Math., 2013

Network design with a discrete set of traffic matrices.
Oper. Res. Lett., 2013

An adaptive routing approach for personal rapid transit.
Math. Methods Oper. Res., 2013

Advances on Matroid Secretary Problems: Free Order Model and Laminar Case.
Proceedings of the Integer Programming and Combinatorial Optimization, 2013

2012
A flow model based on polylinking system.
Math. Program., 2012

A note on chromatic properties of threshold graphs.
Discret. Math., 2012

Bisections above Tight Lower Bounds.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Matroids and integrality gaps for hypergraphic steiner tree relaxations.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Matroidal degree-bounded minimum spanning trees.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011
A New Resource-Constrained Multicommodity Flow Model for Conflict-Free Train Routing and Scheduling.
Transp. Sci., 2011

High-confidence estimation of small <i>s</i>-<i>t</i> reliabilities in directed acyclic networks.
Networks, 2011

A 2-approximation for the maximum satisfying bisection problem.
Eur. J. Oper. Res., 2011

Stochastic convergence of random search methods to fixed size Pareto front approximations.
Eur. J. Oper. Res., 2011

An s-t connection problem with adaptability.
Discret. Appl. Math., 2011

Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Approximation Algorithms for Conflict-Free Vehicle Routing.
Proceedings of the Algorithms - ESA 2011, 2011

2010
Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid.
Discret. Math., 2010

Matching interdiction.
Discret. Appl. Math., 2010

Network flow interdiction on planar graphs.
Discret. Appl. Math., 2010

Optimization with More than One Budget
CoRR, 2010

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Approximation Schemes for Multi-Budgeted Independence Systems.
Proceedings of the Algorithms, 2010

2009
A tight bound on the collection of edges in MSTs of induced subgraphs.
J. Comb. Theory B, 2009

Repair strategies for minimising the risk of cascading failures in electricity networks.
Int. J. Crit. Infrastructures, 2009

Blockers and transversals.
Discret. Math., 2009

An algorithmic framework for wireless information flow.
Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008
Extensions to Network Flow Interdiction on Planar Graphs
CoRR, 2008

2007
Estimation of Small s-t Reliabilities in Acyclic Networks
CoRR, 2007


  Loading...