Gregory B. Sorkin

Random Struct. Algorithms, 2022

2021

Minimum-Weight Combinatorial Structures Under Random Cost-Constraints.

[BibT_eX]

[DOI]

Electron. J. Comb., 2021

2020

Successive shortest paths in complete graphs with random edge weights.

[BibT_eX]

[DOI]

Stefanie Gerke

Balázs F. Mezei

Random Struct. Algorithms, 2020

2018

The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights.

[BibT_eX]

[DOI]

Wesley Pegden

SIAM J. Discret. Math., 2018

2017

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.

[BibT_eX]

[DOI]

Serge Gaspers

ACM Trans. Algorithms, 2017

2016

The Satisfiability Threshold for <i>k</i>-XORSAT.

[BibT_eX]

[DOI]

Boris G. Pittel

Comb. Probab. Comput., 2016

2015

Phase coexistence and torpid mixing in the 3-coloring model on ℤ<sup>d</sup>.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

Efficient algorithms for three-dimensional axial and planar random assignment problems.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2015

2014

Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets.

[BibT_eX]

[DOI]

Serge Gaspers

CoRR, 2014

2013

Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

VCG Auction Mechanism Cost Expectations and Variances.

[BibT_eX]

[DOI]

Svante Janson

CoRR, 2013

2012

A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.

[BibT_eX]

[DOI]

Serge Gaspers

J. Comput. Syst. Sci., 2012

2011

First-passage percolation on a ladder graph, and the path cost in a VCG auction.

[BibT_eX]

[DOI]

Abraham Flaxman

Random Struct. Algorithms, 2011

2010

Structure of random r-SAT below the pure literal threshold

[BibT_eX]

[DOI]

CoRR, 2010

Average-case performance of heuristics for three-dimensional assignment problems

[BibT_eX]

[DOI]

CoRR, 2010

Average case performance of heuristics for multi-dimensional assignment problems

[BibT_eX]

[DOI]

CoRR, 2010

10441 Abstracts Collection - Exact Complexity of NP-hard Problems.

[BibT_eX]

[DOI]

Proceedings of the Exact Complexity of NP-hard Problems, 31.10. - 05.11.2010, 2010

2009

Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

A tight bound on the collection of edges in MSTs of induced subgraphs.

[BibT_eX]

[DOI]

Angelika Steger

Rico Zenklusen

J. Comb. Theory B, 2009

Conditional Probability Tree Estimation Analysis and Algorithms.

[BibT_eX]

[DOI]

Proceedings of the UAI 2009, 2009

Average-Case Analyses of Vickrey Costs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Robust reductions from ranking to classification.

[BibT_eX]

[DOI]

Mach. Learn., 2008

The Power of Choice in a Generalized Pólya Urn Model.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2008

2007

The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Linear-programming design and analysis of fast algorithms for Max 2-CSP.

[BibT_eX]

[DOI]

Discret. Optim., 2007

Random 2-SAT with Prescribed Literal Degrees.

[BibT_eX]

[DOI]

Colin Cooper

Algorithmica, 2007

2006

Vehicle Routing and Staffing for Sedan Service.

[BibT_eX]

[DOI]

Transp. Sci., 2006

Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2006

Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP

[BibT_eX]

[DOI]

CoRR, 2006

Polynomial Constraint Satisfaction: A Framework for Counting and Sampling CSPs and Other Problems

[BibT_eX]

[DOI]

CoRR, 2006

First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction.

[BibT_eX]

[DOI]

Abraham Flaxman

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

An LP-Designed Algorithm for Constraint Satisfaction.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2006

2005

Embracing the giant component.

[BibT_eX]

[DOI]

Abraham D. Flaxman

Random Struct. Algorithms, 2005

2004

Random MAX SAT, random MAX CUT, and their phase transitions.

[BibT_eX]

[DOI]

Don Coppersmith

Mohammad Taghi Hajiaghayi

Random Struct. Algorithms, 2004

The interlace polynomial of a graph.

[BibT_eX]

[DOI]

Richard Arratia

Béla Bollobás

J. Comb. Theory B, 2004

Strings with Maximally Many Distinct Subsequences and Substrings.

[BibT_eX]

[DOI]

Abraham Flaxman

Aram W. Harrow

Electron. J. Comb., 2004

A Two-Variable Interlace Polynomial.

[BibT_eX]

[DOI]

Richard Arratia

Béla Bollobás

Comb., 2004

2003

Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances.

[BibT_eX]

[DOI]

Alex D. Scott

Proceedings of the Approximation, 2003

2002

Exact Expectations And Distributions For The Random Assignment Problem.

[BibT_eX]

[DOI]

Sven Erick Alm

Comb. Probab. Comput., 2002

A note on random 2-SAT with prescribed literal degrees.

[BibT_eX]

[DOI]

Colin Cooper

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001

Some Notes on Random Satisfiability.

[BibT_eX]

[DOI]

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2001

2000

Gadgets, Approximation, and Linear Programming.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Euler circuits and DNA sequencing by hybridization.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2000

The interlace polynomial: a new graph polynomial.

[BibT_eX]

[DOI]

Richard Arratia

Béla Bollobás

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Optimal myopic algorithms for random 3-SAT.

[BibT_eX]

[DOI]

Dimitris Achlioptas

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Constructive bounds and exact expectations for the random assignment problem.

[BibT_eX]

[DOI]

Don Coppersmith

Random Struct. Algorithms, 1999

1998

Constructing Computer Virus Phylogenies.

[BibT_eX]

[DOI]

J. Algorithms, 1998

The Metropolis Algorithm for Graph Bisection.

[BibT_eX]

[DOI]

Mark Jerrum

Discret. Appl. Math., 1998

1996

Gadgets, Approximation, and Linear Programming (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Biologically Inspired Defenses Against Computer Viruses.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995

1993

Simulated Annealing for Graph Bisection

[BibT_eX]

[DOI]

Mark Jerrum

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1991

Efficient Simulated Annealing on Fractal Energy Landscapes.

[BibT_eX]

[DOI]

Algorithmica, 1991

1987

Asymptotically Perfect Trivial Global Routing: A Stochastic Analysis.

[BibT_eX]

[DOI]

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1987

1982

The planar package planner for system designers.

[BibT_eX]

[DOI]

William R. Heller