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
Paper
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
PaperConditional probability tree estimation analysis and algorithms
- Alina Beygelzimer
- John Langford
- et al.
- 2009
- UAI 2009
Conference paperA 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
PaperA universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
- Serge Gaspers
- Gregory B. Sorkin
- 2009
- SODA 2009
Conference paperRobust reductions from ranking to classification
- Maria-Florina Balcan
- Nikhil Bansal
- et al.
- 2008
- Machine Learning
PaperLinear-programming design and analysis of fast algorithms for Max 2-CSP
- Alexander D. Scott
- Gregory B. Sorkin
- 2007
- Discrete Optimization
PaperRandom 2-SAT with prescribed literal degrees
- Colin Cooper
- Alan Frieze
- et al.
- 2007
- Algorithmica (New York)
PaperThe probabilistic relationship between the assignment and asymmetric traveling salesman problems
- Alan Frieze
- Gregory B. Sorkin
- 2006
- SIAM Journal on Computing
PaperSolving 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
Paper