Algorithmic issues in queueing systems and combinatorial counting problems

(cont.) However, these randomized algorithms can never provide proven upper or lower bounds on the number of objects they are counting, but can only give probabilistic estimates. We propose a set of deterministic algorithms for counting such objects for three classes of counting problems. They are interesting both because they give an alternative approach to solving these problems, and because unlike MCMC algorithms, they provide provable bounds on the number of objects. The algorithms we propose are for special cases of counting the number of matchings, colorings, or perfect matchings (permanent), of a graph.

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Katz-Rogozhnikov, Dmitriy A

Advisor dc:contributor.advisor

• David Gamarnik and Dimitris Bertsimas.

• Operations Research Center.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/45945

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/45945