Linear Time Local Approximation Algorithm for Maximum Stable Marriage
We consider a two-sided market under incomplete preference lists with ties, where the goal is to find a maximum size stable matching. The problem is APX-hard, and a 3/2-approximation was given by McDermid [1]. This algorithm has a non-linear running time, and, more importantly needs global knowledge...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2013-08-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/6/3/471 |