First-passage percolation on a ladder graph, and the path cost in a VCG auction
- Abraham Flaxman
- David Gamarnik
- et al.
- 2011
- Random Structures and Algorithms
Publications
31 results for Gregory B. Sorkin
Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
- Alexander D. Scott
- Gregory B. Sorkin
- 2009
- ACM Transactions on Algorithms
Conditional probability tree estimation analysis and algorithms
- Alina Beygelzimer
- John Langford
- et al.
- 2009
- UAI 2009
A tight bound on the collection of edges in MSTs of induced subgraphs
- Gregory B. Sorkin
- Angelika Steger
- et al.
- 2009
- Journal of Combinatorial Theory. Series B
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
- Serge Gaspers
- Gregory B. Sorkin
- 2009
- SODA 2009
Robust reductions from ranking to classification
- Maria-Florina Balcan
- Nikhil Bansal
- et al.
- 2008
- Machine Learning
Linear-programming design and analysis of fast algorithms for Max 2-CSP
- Alexander D. Scott
- Gregory B. Sorkin
- 2007
- Discrete Optimization
Random 2-SAT with prescribed literal degrees
- Colin Cooper
- Alan Frieze
- et al.
- 2007
- Algorithmica (New York)
The probabilistic relationship between the assignment and asymmetric traveling salesman problems
- Alan Frieze
- Gregory B. Sorkin
- 2006
- SIAM Journal on Computing
Solving sparse random instances of Max Cut and Max 2-CSP in linear expected time
- Alexander D. Scott
- Gregory B. Sorkin
- 2006
- Combinatorics Probability and Computing