Jan Vondrak
Department of Mathematics
Fine Hall, room 1004
Washington Road
Princeton
NJ 08544
E-mail: jvondrak-at-math-dot-princeton-dot-edu.
I'm a
Postdoctoral teaching fellow in the
Department of Mathematics, Princeton University.
I'm joining the
theory group at IBM Almaden starting from July 2009.
Current research interests
Combinatorial Optimization
Approximation Algorithms
Stochastic Optimization
Extremal and Probabilistic Combinatorics
Here you can download my curriculum vitae.
Papers
Algorithms and optimization
- Uriel Feige, Jan Vondrak:
The Submodular Welfare Problem
with demand queries
full version, submitted (2009).
- Jan Vondrak:
Submodularity and curvature:
the optimal algorithm
submitted (2008).
- Gruia Calinescu, Chandra Chekuri, Martin Pal and Jan Vondrak:
Maximizing a submodular
set function subject to a matroid constraint
to appear in SIAM Journal on Computing,
special issue for STOC 2008.
An older version
appeared in IPCO 2007, 182-196.
- Jan Vondrak:
Optimal approximation for
the Submodular Welfare Problem in the value oracle model
in STOC 2008, 67-74.
- Vahab Mirrokni, Michael Schapira and Jan Vondrak:
Tight information-theoretic lower bounds
for welfare maximization in combinatorial auctions
in EC 2008.
- Uriel Feige, Vahab Mirrokni and Jan Vondrak:
Maximizing non-monotone submodular
functions
in FOCS 2007, 461-471.
- Gruia Calinescu, Chandra Chekuri and Jan Vondrak:
Disjoint bases in a polymatroid
to appear in Random Structures and Algorithms.
- Uriel Feige and Jan Vondrak:
Approximation algorithms
for allocation problems: Improving the factor of 1-1/e
in FOCS 2006, 667-676.
- Michel Goemans and Jan Vondrak:
Stochastic covering and adaptivity
in LATIN 2006, Theoretical informatics, 532-543,
LNCS 3887 (2006).
- Brian Dean, Michel Goemans and Jan Vondrak:
Adaptivity and approximation
for stochastic packing problems
in SODA 2005, 395-404.
- Brian Dean, Michel Goemans and Jan Vondrak:
Approximating the stochastic
knapsack: the benefit of adaptivity,
submitted to Math. of Operations Research;
an extended
abstract appeared in FOCS 2004, 208-217.
Combinatorics
- Benny Sudakov and Jan Vondrak:
Nearly optimal embeddings of trees
submitted (2007).
- Benny Sudakov and Jan Vondrak:
How many random edges make a dense
hypergraph non-2-colorable?
Random Structures and Algorithms 32 (2008), 290-306.
- Noga Alon, Rados Radoicic, Benny Sudakov and Jan Vondrak:
A Ramsey-type result for
the hypercube
Journal of graph theory 53 (2006), 196-208.
- Jan Vondrak:
Shortest-path metric approximation
for random subgraphs
Random structures and algorithms 30:1-2 (2007), 95-104.
- Michel Goemans and Jan Vondrak:
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 Vondrak:
Wide partitions, Latin tableaux,
and Rota's basis conjecture
Advances in Applied Mathematics, 31:2, 334-358 (2003).
- Robert Samal and Jan Vondrak:
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.