Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 4 of 4 for “"minimum regret"”.
-
Structure of the Stable Marriage and Stable Roommate Problems and Applications
… prove that a k-optimal matching is the same as a minimum regret matching for high enough k. Finally, Dan Gusfield defines the rotation poset for the stable roommate problem, and uses it to efficiently enumerate all stable roommate assignments.
-
Algorithms for weighted coloring problems
… The objective is to find a coloring with the minimum number of colors. In the first part of the thesis, we studied the weighted version of the problem, where vertices have non-negative weights. In a weighted vertex coloring problem (WVCP) the cost of each color depends on the weights of the …
-
Algorithmic aspects of stable matching problems
… we show that each of the problem of finding a minimum regret and an egalitarian weakly stable matching is NP-hard and that the problem of determining if a (man,woman) pair belongs to a weakly stable matching is NP-complete. We then describe algorithms for each of the problems of finding a …
-
Efficient algorithms for optimal matching problems under preferences
… for the problems of finding an egalitarian, minimum regret and sex equal socially stable matching in the sm context. We extend our study of social stability by considering other variants and restrictions of max smiss and max hrss. We present NP-hardness results for max smiss even under …