Arrow Research search

Author name cluster

Chandra Nair

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

STOC Conference 2007 Conference Paper

Simple deterministic approximation algorithms for counting matchings

  • Mohsen Bayati
  • David Gamarnik
  • Dimitriy A. Katz
  • Chandra Nair
  • Prasad Tetali

We construct a deterministic fully polynomial time approximationscheme (FPTAS) for computing the total number of matchings in abounded degree graph. Additionally, for an arbitrary graph, weconstruct a deterministic algorithm for computing approximately thenumber of matchings within running time exp(O(√n log 2 n)),where n is the number of vertices.

Details

FOCS Conference 2003 Conference Paper

Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem

  • Chandra Nair
  • Balaji Prabhakar
  • Mayank Sharma

Suppose that there are n jobs and n machines and it costs c/sub ij/ to execute job i on machine j. The assignment problem concerns the determination of a one-to-one assignment of jobs onto machines so as to minimize the cost of executing all the jobs. The average case analysis of the classical random assignment problem has received a lot of interest in the recent literature, mainly due to the following pleasing conjecture of Parisi: The average value of the minimum-cost permutation in an n /spl times/ n matrix with i. i. d. exp(1) entries equals /spl Sigma//sub i=1//sup n/ 1/(i/sup 2/). D. Coppersmith and G. Sorkin (1999) have generalized Parisi's conjecture to the average value of the smallest k-assignment when there are n jobs and m machines. We prove both conjectures based on a common set of combinatorial and probabilistic arguments.

Details
v2026.09.13