Jan Vondrák
IBM Almaden Research Center
650 Harry Rd
San Jose
CA 95120
E-mail: jvondrak-at-gmail-dot-com.
I'm a Research Staff Member in the
theory group at IBM Almaden.
Current research interests
Combinatorial Optimization
Approximation Algorithms
Stochastic Optimization
Extremal and Probabilistic Combinatorics
Here you can download my curriculum vitae.
Papers
Algorithms and optimization
- Chandra Chekuri, Jan Vondrák, Rico Zenklusen:
Dependent randomized rounding for matroid polytopes and applications
arXiv.org, 0909.4348, 2009.
- Jon Lee, Maxim Sviridenko, Jan Vondrák:
Matroid matching: the power of local search
IBM Research Report, RC24898, 2009.
- Jan Vondrák:
Symmetry and approximability of submodular maximization problems
in FOCS 2009, 651-670.
- Jon Lee, Maxim Sviridenko, Jan Vondrák:
Submodular maximization over multiple matroids via generalized exchange properties
in APPROX 2009, 244-257.
- Jan Vondrák:
Submodularity and curvature: the optimal algorithm
to appear in RIMS Kokyuroku Bessatsu, Kyoto 2008.
- Gruia Calinescu, Chandra Chekuri, Martin Pál and Jan Vondrák:
Maximizing a submodular set function subject to a matroid constraint
to appear in SIAM Journal on Computing,
special issue for STOC 2008.
This paper combines the results of two preceding conference papers:
- Vahab Mirrokni, Michael Schapira and Jan Vondrák:
Tight information-theoretic lower bounds
for welfare maximization in combinatorial auctions
in EC 2008.
- Uriel Feige, Vahab Mirrokni and Jan Vondrák:
Maximizing non-monotone submodular
functions
in FOCS 2007, 461-471.
- Gruia Calinescu, Chandra Chekuri and Jan Vondrák:
Disjoint bases in a polymatroid
to appear in Random Structures and Algorithms.
- Uriel Feige, Jan Vondrák:
The Submodular Welfare Problem with demand queries
full version, submitted, 2009.
- Uriel Feige and Jan Vondrák:
Approximation algorithms
for allocation problems: Improving the factor of 1-1/e
in FOCS 2006, 667-676.
- Michel Goemans and Jan Vondrák:
Stochastic covering and adaptivity
in LATIN 2006, Theoretical informatics, 532-543,
LNCS 3887 (2006).
- Brian Dean, Michel Goemans and Jan Vondrák:
Adaptivity and approximation
for stochastic packing problems
in SODA 2005, 395-404.
- Brian Dean, Michel Goemans and Jan Vondrák:
Approximating the stochastic
knapsack: the benefit of adaptivity,
submitted to Math. of Operations Research;
an extended
abstract appeared in FOCS 2004, 208-217.
Information Theory
Combinatorics
- Benny Sudakov and Jan Vondrák:
A randomized embedding algorithm for trees
to appear in Combinatorica.
- Benny Sudakov and Jan Vondrák:
How many random edges make a dense
hypergraph non-2-colorable?
Random Structures and Algorithms 32 (2008), 290-306.
- Noga Alon, Radoš Radoičić, Benny Sudakov and Jan Vondrák:
A Ramsey-type result for
the hypercube
Journal of graph theory 53 (2006), 196-208.
- Jan Vondrák:
Shortest-path metric approximation
for random subgraphs
Random structures and algorithms 30:1-2 (2007), 95-104.
- Michel Goemans and Jan Vondrák:
Covering minimum spanning trees
of random subgraphs
Random structures and algorithms 29:3 (2006), 257-276.
An extended abstract
appeared in SODA 2004, 927-934.
- Tim Chow, Kenneth Fan, Michel Goemans and Jan Vondrák:
Wide partitions, Latin tableaux,
and Rota's basis conjecture
Advances in Applied Mathematics, 31:2, 334-358 (2003).
- Robert Šámal and Jan Vondrák:
The limit checker number of a graph
Discrete Math. 235, 343-347 (2001).
Discrete Geometry
Max-Cut and Statistical Physics
Theses
- Probabilistic methods in combinatorial
and stochastic optimization, PhD thesis, MIT, 2005.
- Submodularity in combinatorial
optimization, PhD thesis, Charles University,
Prague, 2007.
- Implementation and testing of a new
algorithm for the Max Cut problem,
Master's thesis, Charles University,
Prague, 1999.