The search functionality is under construction.

Author Search Result

[Author] Kazuya OKAMOTO(1hit)

1-1hit
  • A -Approximation Algorithm for the Stable Marriage Problem

    Kazuo IWAMA  Shuichi MIYAZAKI  Kazuya OKAMOTO  

     
    INVITED PAPER

      Vol:
    E89-D No:8
      Page(s):
    2380-2387

    An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio for an arbitrarily positive constant c, where N denotes the number of men in an input.