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.
Current research interests
Combinatorial Optimization
Approximation Algorithms
Stochastic Optimization
Extremal and Probabilistic Combinatorics
Here you can download my curriculum vitae.
Papers
Algorithms and optimization
- 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
submitted (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
submitted (2007).
- 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?
to appear in Random structures and algorithms (2007).
- 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