×

zbMATH — the first resource for mathematics

Vondrák, Jan

Compute Distance To:
Author ID: vondrak.jan Recent zbMATH articles by "Vondrák, Jan"
Published as: Vondrak, J.; Vondrak, Jan; Vondrák, J.; Vondrák, Jan
Documents Indexed: 65 Publications since 1982

Publications by Year

Citations contained in zbMATH

52 Publications have been cited 537 times in 301 Documents Cited by Year
Maximizing a monotone submodular function subject to a matroid constraint. Zbl 1234.68459
Calinescu, Gruia; Chekuri, Chandra; Pál, Martin; Vondrák, Jan
63
2011
Maximizing non-monotone submodular functions. Zbl 1230.90198
Feige, Uriel; Mirrokni, Vahab S.; Vondrák, Jan
56
2011
Approximating the stochastic Knapsack problem: the benefit of adaptivity. Zbl 1218.90169
Dean, Brian C.; Goemans, Michel X.; Vondrák, Jan
42
2008
Submodular function maximization via the multilinear relaxation and contention resolution schemes. Zbl 1288.90081
Vondrák, Jan; Chekuri, Chandra; Zenklusen, Rico
31
2011
Maximizing a submodular set function subject to a matroid constraint (extended abstract). Zbl 1136.90449
Calinescu, Gruia; Chekuri, Chandra; Pál, Martin; Vondrák, Jan
28
2007
Optimal approximation for the submodular welfare problem in the value oracle model. Zbl 1231.91094
Vondrak, Jan
24
2008
Multi-budgeted matchings and matroid intersection via dependent rounding. Zbl 1377.90071
Chekuri, Chandra; Vondrák, Jan; Zenklusen, Rico
23
2011
Submodular maximization over multiple matroids via generalized exchange properties. Zbl 1216.68342
Lee, Jon; Sviridenko, Maxim; Vondrák, Jan
22
2010
Submodular maximization by simulated annealing. Zbl 1377.90073
Gharan, Shayan Oveis; Vondrák, Jan
20
2011
Adaptivity and approximation for stochastic packing problems. Zbl 1297.90135
Dean, Brian C.; Goemans, Michel X.; Vondrák, Jan
17
2005
Symmetry and approximability of submodular maximization problems. Zbl 1292.90262
Vondrák, Jan
11
2009
Fast algorithms for maximizing submodular functions. Zbl 1422.68286
Badanidiyuru, Ashwinkumar; Vondrák, Jan
10
2014
Submodularity and curvature: the optimal algorithm. Zbl 1219.68109
Vondrák, Jan
9
2010
Stochastic covering and adaptivity. Zbl 1145.90427
Goemans, Michel; Vondrák, Jan
9
2006
Submodular function maximization via the multilinear relaxation and contention resolution schemes. Zbl 1437.90135
Chekuri, Chandra; Vondrák, Jan; Zenklusen, Rico
8
2014
Matroid matching: the power of local search. Zbl 1310.68243
Lee, Jon; Sviridenko, Maxim; Vondrák, Jan
8
2013
Symmetry and approximability of submodular maximization problems. Zbl 1292.90261
Vondrák, Jan
8
2013
From query complexity to computational complexity. Zbl 1286.68225
Dobzinski, Shahar; Vondrak, Jan
8
2012
The submodular welfare problem with demand queries. Zbl 1213.68703
Feige, Uriel; Vondrák, Jan
8
2010
A Ramsey-type result for the hypercube. Zbl 1111.05067
Alon, Noga; Radoičić, Radoš; Sudakov, Benny; Vondrák, Jan
8
2006
Optimization via enumeration: A new algorithm for the max cut problem. Zbl 0989.90127
Galluccio, Anna; Loebl, Martin; Vondrák, Jan
8
2001
Sperner’s colorings, hypergraph labeling problems and fair division. Zbl 1371.05094
Mirzakhani, Maryam; Vondrák, Jan
7
2015
Multiway cut, pairwise realizable distributions, and descending thresholds. Zbl 1315.68288
Sharma, Ankit; Vondrák, Jan
7
2014
Optimal approximation for submodular and supermodular optimization with bounded curvature. Zbl 1371.90143
Sviridenko, Maxim; Vondrák, Jan; Ward, Justin
6
2015
Is submodularity testable? Zbl 1307.68097
Seshadhri, C.; Vondrák, Jan
6
2014
Local distribution and the symmetry gap: approximability of multiway partitioning problems. Zbl 1421.68217
Ene, Alina; Vondrák, Jan; Wu, Yi
6
2013
A randomized embedding algorithm for trees. Zbl 1231.05274
Sudakov, Benny; Vondrák, Jan
6
2010
Report of the international astronomical union division I working group on precession and the ecliptic. Zbl 1175.70016
Hilton, J. L.; Capitaine, N.; Chapront, J.; Ferrandiz, J. M.; Fienga, A.; Fukushima, T.; Getino, J.; Mathews, P.; Simon, J.-L.; Soffel, M.; Vondrak, J.; Wallace, P.; Williams, J.
6
2006
Limitations of randomized mechanisms for combinatorial auctions. Zbl 1318.91090
Dughmi, Shaddin; Vondrák, Jan
5
2015
On variants of the matroid secretary problem. Zbl 1307.68101
Oveis Gharan, Shayan; Vondrák, Jan
5
2013
Matroid matching: the power of local search. Zbl 1293.05035
Lee, Jon; Sviridenko, Maxim; Vondrak, Jan
5
2010
Submodular maximization over multiple matroids via generalized exchange properties. Zbl 1255.90106
Lee, Jon; Sviridenko, Maxim; Vondrák, Jan
5
2009
Computing the independence polynomial: from the tree threshold down to the roots. Zbl 1403.68351
Harvey, Nicholas J. A.; Srivastava, Piyush; Vondrák, Jan
4
2018
On multiplicative weight updates for concave and submodular function maximization. Zbl 1365.90225
Chekuri, Chandra; Jayram, T. S.; Vondrak, Jan
4
2015
Online submodular welfare maximization: greedy is optimal. Zbl 1425.91198
Kapralov, Michael; Post, Ian; Vondrák, Jan
4
2013
On variants of the matroid secretary problem. Zbl 1307.68100
Oveis Gharan, Shayan; Vondrák, Jan
4
2011
Towards a theory of frustrated degeneracy. Zbl 1089.82015
Loebl, Martin; Vondrák, Jan
4
2003
Optimal approximation for submodular and supermodular optimization with bounded curvature. Zbl 1386.90129
Sviridenko, Maxim; Vondrák, Jan; Ward, Justin
3
2017
Optimal bounds on approximation of submodular and XOS functions by juntas. Zbl 1345.68251
Feldman, Vitaly; Vondrák, Jan
3
2016
Limitations of randomized mechanisms for combinatorial auctions. Zbl 1292.91082
Dughmi, Shaddin; Vondrák, Jan
3
2011
How many random edges make a dense hypergraph non-2-colorable? Zbl 1149.05038
Sudakov, Benny; Vondrák, Jan
3
2008
Covering minimum spanning trees of random subgraphs. Zbl 1108.05082
Goemans, Michel X.; Vondrák, Jan
3
2006
Nearly equal distances and Szemerédi’s regularity lemma. Zbl 1096.52009
Pach, János; Radoičić, Radoš; Vondrák, Jan
3
2006
Wide partitions, Latin tableaux, and Rota’s basis conjecture. Zbl 1029.05049
Chow, Timothy Y.; Fan, C. Kenneth; Goemans, Michel X.; Vondrak, Jan
3
2003
Impossibility results for truthful combinatorial auctions with submodular valuations. Zbl 1426.68119
Dobzinski, Shahar; Vondrák, Jan
2
2016
Hardness of submodular cost allocation: lattice matching and a simplex coloring conjecture. Zbl 1359.68100
Ene, Alina; Vondrák, Jan
2
2014
Communication complexity of combinatorial auctions with submodular valuations. Zbl 1421.68213
Dobzinski, Shahar; Vondrák, Jan
2
2013
An algorithmic proof of the Lovász local lemma via resampling oracles. Zbl 1433.68603
Harvey, Nicholas J. A.; Vondrák, Jan
1
2020
Sperner’s colorings and optimal partitioning of the simplex. Zbl 1384.05188
Mirzakhani, Maryam; Vondrák, Jan
1
2017
Disjoint bases in a polymatroid. Zbl 1205.05039
Călinescu, Gruia; Chekuri, Chandra; Vondrák, Jan
1
2009
On the diameter of separated point sets with many nearly equal distances. Zbl 1107.52011
Pach, János; Radoičić, Radoš; Vondrák, Jan
1
2006
On the direct influence of the planets on the precession and nutation of the Earth’s axis of rotation. Zbl 0488.70012
Vondrak, J.
1
1982
An algorithmic proof of the Lovász local lemma via resampling oracles. Zbl 1433.68603
Harvey, Nicholas J. A.; Vondrák, Jan
1
2020
Computing the independence polynomial: from the tree threshold down to the roots. Zbl 1403.68351
Harvey, Nicholas J. A.; Srivastava, Piyush; Vondrák, Jan
4
2018
Optimal approximation for submodular and supermodular optimization with bounded curvature. Zbl 1386.90129
Sviridenko, Maxim; Vondrák, Jan; Ward, Justin
3
2017
Sperner’s colorings and optimal partitioning of the simplex. Zbl 1384.05188
Mirzakhani, Maryam; Vondrák, Jan
1
2017
Optimal bounds on approximation of submodular and XOS functions by juntas. Zbl 1345.68251
Feldman, Vitaly; Vondrák, Jan
3
2016
Impossibility results for truthful combinatorial auctions with submodular valuations. Zbl 1426.68119
Dobzinski, Shahar; Vondrák, Jan
2
2016
Sperner’s colorings, hypergraph labeling problems and fair division. Zbl 1371.05094
Mirzakhani, Maryam; Vondrák, Jan
7
2015
Optimal approximation for submodular and supermodular optimization with bounded curvature. Zbl 1371.90143
Sviridenko, Maxim; Vondrák, Jan; Ward, Justin
6
2015
Limitations of randomized mechanisms for combinatorial auctions. Zbl 1318.91090
Dughmi, Shaddin; Vondrák, Jan
5
2015
On multiplicative weight updates for concave and submodular function maximization. Zbl 1365.90225
Chekuri, Chandra; Jayram, T. S.; Vondrak, Jan
4
2015
Fast algorithms for maximizing submodular functions. Zbl 1422.68286
Badanidiyuru, Ashwinkumar; Vondrák, Jan
10
2014
Submodular function maximization via the multilinear relaxation and contention resolution schemes. Zbl 1437.90135
Chekuri, Chandra; Vondrák, Jan; Zenklusen, Rico
8
2014
Multiway cut, pairwise realizable distributions, and descending thresholds. Zbl 1315.68288
Sharma, Ankit; Vondrák, Jan
7
2014
Is submodularity testable? Zbl 1307.68097
Seshadhri, C.; Vondrák, Jan
6
2014
Hardness of submodular cost allocation: lattice matching and a simplex coloring conjecture. Zbl 1359.68100
Ene, Alina; Vondrák, Jan
2
2014
Matroid matching: the power of local search. Zbl 1310.68243
Lee, Jon; Sviridenko, Maxim; Vondrák, Jan
8
2013
Symmetry and approximability of submodular maximization problems. Zbl 1292.90261
Vondrák, Jan
8
2013
Local distribution and the symmetry gap: approximability of multiway partitioning problems. Zbl 1421.68217
Ene, Alina; Vondrák, Jan; Wu, Yi
6
2013
On variants of the matroid secretary problem. Zbl 1307.68101
Oveis Gharan, Shayan; Vondrák, Jan
5
2013
Online submodular welfare maximization: greedy is optimal. Zbl 1425.91198
Kapralov, Michael; Post, Ian; Vondrák, Jan
4
2013
Communication complexity of combinatorial auctions with submodular valuations. Zbl 1421.68213
Dobzinski, Shahar; Vondrák, Jan
2
2013
From query complexity to computational complexity. Zbl 1286.68225
Dobzinski, Shahar; Vondrak, Jan
8
2012
Maximizing a monotone submodular function subject to a matroid constraint. Zbl 1234.68459
Calinescu, Gruia; Chekuri, Chandra; Pál, Martin; Vondrák, Jan
63
2011
Maximizing non-monotone submodular functions. Zbl 1230.90198
Feige, Uriel; Mirrokni, Vahab S.; Vondrák, Jan
56
2011
Submodular function maximization via the multilinear relaxation and contention resolution schemes. Zbl 1288.90081
Vondrák, Jan; Chekuri, Chandra; Zenklusen, Rico
31
2011
Multi-budgeted matchings and matroid intersection via dependent rounding. Zbl 1377.90071
Chekuri, Chandra; Vondrák, Jan; Zenklusen, Rico
23
2011
Submodular maximization by simulated annealing. Zbl 1377.90073
Gharan, Shayan Oveis; Vondrák, Jan
20
2011
On variants of the matroid secretary problem. Zbl 1307.68100
Oveis Gharan, Shayan; Vondrák, Jan
4
2011
Limitations of randomized mechanisms for combinatorial auctions. Zbl 1292.91082
Dughmi, Shaddin; Vondrák, Jan
3
2011
Submodular maximization over multiple matroids via generalized exchange properties. Zbl 1216.68342
Lee, Jon; Sviridenko, Maxim; Vondrák, Jan
22
2010
Submodularity and curvature: the optimal algorithm. Zbl 1219.68109
Vondrák, Jan
9
2010
The submodular welfare problem with demand queries. Zbl 1213.68703
Feige, Uriel; Vondrák, Jan
8
2010
A randomized embedding algorithm for trees. Zbl 1231.05274
Sudakov, Benny; Vondrák, Jan
6
2010
Matroid matching: the power of local search. Zbl 1293.05035
Lee, Jon; Sviridenko, Maxim; Vondrak, Jan
5
2010
Symmetry and approximability of submodular maximization problems. Zbl 1292.90262
Vondrák, Jan
11
2009
Submodular maximization over multiple matroids via generalized exchange properties. Zbl 1255.90106
Lee, Jon; Sviridenko, Maxim; Vondrák, Jan
5
2009
Disjoint bases in a polymatroid. Zbl 1205.05039
Călinescu, Gruia; Chekuri, Chandra; Vondrák, Jan
1
2009
Approximating the stochastic Knapsack problem: the benefit of adaptivity. Zbl 1218.90169
Dean, Brian C.; Goemans, Michel X.; Vondrák, Jan
42
2008
Optimal approximation for the submodular welfare problem in the value oracle model. Zbl 1231.91094
Vondrak, Jan
24
2008
How many random edges make a dense hypergraph non-2-colorable? Zbl 1149.05038
Sudakov, Benny; Vondrák, Jan
3
2008
Maximizing a submodular set function subject to a matroid constraint (extended abstract). Zbl 1136.90449
Calinescu, Gruia; Chekuri, Chandra; Pál, Martin; Vondrák, Jan
28
2007
Stochastic covering and adaptivity. Zbl 1145.90427
Goemans, Michel; Vondrák, Jan
9
2006
A Ramsey-type result for the hypercube. Zbl 1111.05067
Alon, Noga; Radoičić, Radoš; Sudakov, Benny; Vondrák, Jan
8
2006
Report of the international astronomical union division I working group on precession and the ecliptic. Zbl 1175.70016
Hilton, J. L.; Capitaine, N.; Chapront, J.; Ferrandiz, J. M.; Fienga, A.; Fukushima, T.; Getino, J.; Mathews, P.; Simon, J.-L.; Soffel, M.; Vondrak, J.; Wallace, P.; Williams, J.
6
2006
Covering minimum spanning trees of random subgraphs. Zbl 1108.05082
Goemans, Michel X.; Vondrák, Jan
3
2006
Nearly equal distances and Szemerédi’s regularity lemma. Zbl 1096.52009
Pach, János; Radoičić, Radoš; Vondrák, Jan
3
2006
On the diameter of separated point sets with many nearly equal distances. Zbl 1107.52011
Pach, János; Radoičić, Radoš; Vondrák, Jan
1
2006
Adaptivity and approximation for stochastic packing problems. Zbl 1297.90135
Dean, Brian C.; Goemans, Michel X.; Vondrák, Jan
17
2005
Towards a theory of frustrated degeneracy. Zbl 1089.82015
Loebl, Martin; Vondrák, Jan
4
2003
Wide partitions, Latin tableaux, and Rota’s basis conjecture. Zbl 1029.05049
Chow, Timothy Y.; Fan, C. Kenneth; Goemans, Michel X.; Vondrak, Jan
3
2003
Optimization via enumeration: A new algorithm for the max cut problem. Zbl 0989.90127
Galluccio, Anna; Loebl, Martin; Vondrák, Jan
8
2001
On the direct influence of the planets on the precession and nutation of the Earth’s axis of rotation. Zbl 0488.70012
Vondrak, J.
1
1982
all top 5

Cited by 610 Authors

10 Feldman, Moran
10 Nagarajan, Viswanath
10 Zenklusen, Rico
6 Buchbinder, Niv
6 Vondrák, Jan
6 Wu, Weili
6 Xu, Dachuan
5 Chekuri, Chandra S.
5 Du, Ding-Zhu
5 Gong, Suning
5 Levin, Asaf
5 Nong, Qingqin
5 Ravi, Ramamoorthi
5 Schwartz, Roy
5 Živný, Stanislav
4 Ahmed, Shabbir
4 Fang, Qizhi
4 Gupta, Anupam
4 Kawase, Yasushi
4 Király, Tamás
4 Naor, Joseph Seffi
4 Sviridenko, Maxim I.
4 Vainer, Aleksander
4 Yoshida, Yuichi
3 Bansal, Nikhil
3 Bérczi, Kristóf
3 Chandrasekaran, Karthekeyan
3 Chong, Edwin Kah Pin
3 Dobzinski, Shahar
3 Ene, Alina
3 Goyal, Vineet
3 Huang, Zhiyi
3 Jeavons, Peter G.
3 Jiménez, Andrea
3 Kleinberg, Robert D.
3 Krivelevich, Michael
3 Kumar, Amit
3 Liu, Yajing
3 Maehara, Takanori
3 Makino, Kazuhisa
3 Megow, Nicole
3 Pezeshki, Ali
3 Roughgarden, Tim
3 Roy, Sambuddha
3 Samotij, Wojciech
3 Shioura, Akiyoshi
3 Singh, Mohit
3 Srinivasan, Aravind
3 Tang, Shaojie
3 Williams, James G.
2 Adamczyk, Marek
2 Awasthi, Pranjal
2 Balogh, József
2 Blado, Daniel
2 Borodin, Allan B.
2 Capitaine, Nicole
2 Chakrabarty, Deeparnab
2 Cohen, David A.
2 Contreras, Iván A.
2 Deshpande, Amol
2 Du, Donglei
2 Dütting, Paul
2 Fang, Jiazhu
2 Feige, Uriel
2 Feldman, Vitaly
2 Feng, Yan
2 Filmus, Yuval
2 Fisch, Ronald
2 Furedi, Zoltan
2 Gaubert, Stéphane
2 Goel, Gagan
2 Grandoni, Fabrizio
2 Guo, Longkun
2 Gupta, Shalmoli
2 Hoefer, Martin
2 Huang, Chien-Chung
2 Huang, Chuanhe
2 Im, Sungjin
2 Iwata, Satoru
2 Jawaid, Syed Talha
2 Jiang, Yanjun
2 Johannsen, Daniel
2 Kakimura, Naonori
2 Kamiński, Marcin Marek
2 Karbasi, Amin
2 Kijima, Shuji
2 Kiwi, Marcos A.
2 Kolmogorov, Vladimir
2 Korula, Nitish
2 Kothari, Pravesh K.
2 Krishnaswamy, Ravishankar
2 Laporte, Gilbert
2 Lee, Jon
2 Li, Jian
2 Li, Jian
2 Lidický, Bernard
2 Lu, Changhong
2 Lucier, Brendan
2 Madan, Vivek
2 Makarychev, Konstantin S.
...and 510 more Authors
all top 5

Cited in 69 Serials

23 Mathematical Programming. Series A. Series B
22 Theoretical Computer Science
18 Algorithmica
17 SIAM Journal on Computing
14 Discrete Applied Mathematics
14 Mathematics of Operations Research
12 SIAM Journal on Discrete Mathematics
10 Operations Research Letters
8 Games and Economic Behavior
8 Journal of Combinatorial Optimization
6 Celestial Mechanics and Dynamical Astronomy
5 Journal of the Operations Research Society of China
4 Discrete Mathematics
4 Information Processing Letters
4 Operations Research
4 Discrete Optimization
3 Journal of Combinatorial Theory. Series B
3 European Journal of Operational Research
3 SIAM Journal on Optimization
3 Combinatorics, Probability and Computing
3 Journal of Machine Learning Research (JMLR)
3 Optimization Letters
2 Artificial Intelligence
2 Communications in Mathematical Physics
2 Journal of Statistical Physics
2 Journal of Combinatorial Theory. Series A
2 Journal of Computer and System Sciences
2 Journal of Optimization Theory and Applications
2 European Journal of Combinatorics
2 Discrete & Computational Geometry
2 Computers & Operations Research
2 Random Structures & Algorithms
2 Japan Journal of Industrial and Applied Mathematics
2 Journal of Global Optimization
2 Linear Algebra and its Applications
2 INFORMS Journal on Computing
2 Theory of Computing Systems
2 Discrete Mathematics, Algorithms and Applications
2 Stochastic Systems
1 American Mathematical Monthly
1 Israel Journal of Mathematics
1 Journal of Mathematical Physics
1 Automatica
1 Memoirs of the American Mathematical Society
1 SIAM Journal on Control and Optimization
1 Advances in Applied Mathematics
1 Graphs and Combinatorics
1 Probability Theory and Related Fields
1 Journal of Computer Science and Technology
1 Information and Computation
1 Asia-Pacific Journal of Operational Research
1 Annals of Operations Research
1 Discrete Event Dynamic Systems
1 Bulletin of the American Mathematical Society. New Series
1 Computational Complexity
1 Opuscula Mathematica
1 Annals of Mathematics and Artificial Intelligence
1 Complexity
1 Constraints
1 Mathematical Methods of Operations Research
1 Journal of Scheduling
1 Journal of Graph Algorithms and Applications
1 Review of Economic Design
1 ACM Journal of Experimental Algorithmics
1 Journal of Discrete Algorithms
1 Algorithms
1 Theory of Computing
1 Computer Science Review
1 SIAM/ASA Journal on Uncertainty Quantification

Citations by Year