Popular Matching in Roommates Setting is NP-hard.

Sushmita Gupta Pranabendu Misra Saket Saurabh Meirav Zehavi

Published in: CoRR (2018)

Keyphrases

np hard
matching algorithm
approximation algorithms
special case
np complete
optimal solution
lower bound

scheduling problem
matching process
linear programming
worst case
matching scheme
database
face recognition

pattern matching
computer vision
image matching
shape matching
correspondence matching
minimum cost
greedy heuristic

branch and bound algorithm
decision problems
keypoints
feature points
case study
databases
data sets