Local distribution and the symmetry gap: Approximability of multiway partitioning problems
- Alina Ene
- Jan Vondrák
- et al.
- 2013
- SODA 2013
Conference paper
Publications
40 results for Jan Vondrák
Online submodular welfare maximization: Greedy is optimal
- Michael Kapralov
- Ian Post
- et al.
- 2013
- SODA 2013
Conference paperMultituple deletion propagation: Approximations and complexity
- Benny Kimelfeld
- Jan Vondrák
- et al.
- 2013
- VLDB
PaperRepresentation, approximation and learning of submodular functions using low-rank decision trees
- Vitaly Feldman
- Pravesh Kothari
- et al.
- 2013
- JMLR
PaperMaximizing conjunctive views in deletion propagation
- Benny Kimelfeld
- Jan Vondrák
- et al.
- 2012
- ACM TODS
PaperIs submodularity testable?
- C. Seshadhri
- Jan Vondrák
- 2012
- Algorithmica
PaperThe computational complexity of truthfulness in combinatorial auctions
- Shahar Dobzinski
- Jan Vondrák
- 2012
- EC 2012
Conference paperFrom query complexity to computational complexity
- Shahar Dobzinski
- Jan Vondrak
- 2012
- STOC 2012
Conference paperMaximizing a monotone submodular function subject to a matroid constraint
- Gruia Calinescu
- Chandra Chekuri
- et al.
- 2011
- SIAM Journal on Computing
PaperOn principles of egocentric person search in social networks
- Sara Cohen
- Benny Kimelfeld
- et al.
- 2011
- VLDS 2011
Conference paper