DOI : 10.17577/IJERTV4IS010338
- Open Access
- Total Downloads : 134
- Authors : T. Ramachandran , D. Udayakumar , T. Selvakumar
- Paper ID : IJERTV4IS010338
- Volume & Issue : Volume 04, Issue 01 (January 2015)
- Published (First Online): 23-01-2015
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License:
This work is licensed under a Creative Commons Attribution 4.0 International License
Variants of N – Factor Satisfactory Roommates Problem
T. Ramachandran 1
1 Department of Mathematics, M.V.Muthiah Government Arts College for Women
Dindigul -624001, Tamilnadu, India.
-
Udayakumar 2
2 Department of Mathematics,
Government Arts College, Karur-639005, Tamilnadu, India.
T. Selvakumar 3
3 Department of Mathematics, Chettinad College of Engineering & Technology,
Karur-639114, Tamilnadu, India.
Abstract In this paper we discussed the variants of N-Factor satisfactory roommates problem with suitable examples that gives some interesting result in the case of satisfactory roommates problem.
Keywords N-Factors, Preference Value, Satisfactory value matrix, Satisfactory Level, Roommates problem.
-
INTRODUCTION
The Stable Roommates problem(SRP) is a classical combinatorial problem that has received much attention in the literature [1,2,5,9,10,11].Gale and Shapley were the first two study SRP and they defined an instance I comprises n members pi (i = 1,2,3..n) ,where n is even, each of whom ranks the others in strict order of preference. A matching (M) in I is a set of n/2 disjoint pairs of members
{pi,pj}each of whom prefers the other his partner in the matching M . A Matching M is stable if it admits no blocking pair .A pair (pi,pj)will form a blocking pair in M iff pi and pj are not assigned to each other in M and they either prefer each other to their respective assigned partner in M or are unmatched in M.Gale and Shapley [1] showed that an SRP instance need not admit a stable matching. Irving [9] solved a problem posed by Knuth [10] when he described an O (n2) algorithm that finds a stable matching or reports that none exists, for a given instance of SRP.
The classical satisfactory roommates problem (SFRP) is closely related to the stable roommates problem. In the satisfactory roommates problem each person in the set of even cardinality n ranks the n-1 others in the order of preference. The objective is to find satisfactory matching of roommates problem. This is the partition of the set into n/2 pairs of roommates based on the individual satisfactory level. It is known that some of the instances of the satisfactory roommates problem are unsolvable.
-
N-FACTOR SATISFACTORY ROOMMATES PROBLEM WITH TIES
As mentioned earlier, classical Satisfactory Roommates problem (SFRP) in which complete preference lists will be given for each member of the group. A natural generalization of Satisfactory Roommates problem (SFRP) is called Satisfactory Roommates problem with ties lists (SFRPT) and which is closely related to Stable roommates problem with ties (SRT) [2, 3, 4]. The case arises when each person need not rank all members of his group in strict order. Some of those might be indifferent among certain members of the group, so that preference lists may involve ties. We use SFRPT to stand for the variant of SFRP in which preference lists may include ties. (Henceforth we assume that a tie is of length at least two.) By breaking the ties arbitrarily, an instance of SFRPT becomes an instance of SFRP [13].
In this paper, the N-Factor SFRP [6] extended into N- Factor SFRPT. For the related terminologies such as satisfactory value matrix, satisfactory level, satisfactory matching, assignment model and SMAR algorithm refer [7, 8].
Example 2.1 Here the problem is discussed with 5 different parameters, Consider the problem instance of size 4 based on order of preference.
1
3
2
4
2
(4
3)
1
3
2
4
1
4
1
(2
3)
Preference list based on Parameter A
The Satisfactory value Matrix is Preference list based on Parameter D
1
1
3
SVM = 2 3
3 4
3
4 4
2 3 4
3 4 4
3 3 3
11 4
6 3
11 7
6 6
4 7
1
3
(2
4)
2
4
1
3
3
1
4
2
4
1
(3
2)
The Satisfactory value Matrix is
3 3 6
1 2 3 4
Preference list based on Parameter B 1 2 4 3
2 4 (3 1)
3 (1 2) 4
4 3 1 2
The Satisfactory value Matrix is
1
SVM = 2
3
4
7 6 3
6 3 2
7 2 3
6 3 2
6 2 7
3 3 6
3 3 7
2 2 6
1
SVM = 2
3
4
1 2 3 4
3 7 4
2 6 3
3 4 4
2 3 3
7 4 4
6 3 3
4 4 4
3 3 3
Preference list based on Parameter E 1 2 (4 3)
2 3 4 1
3 1 2 4
4 (1 3) 2
The Satisfactory value Matrix is
Preference list based on Parameter C
1
(4
2)
3
2
1
3
4
3
2
1
4
4
(3
2)
1
The Satisfactory value Matrix is
2
3
4
11
3
7
6
3
6
1
1
SVM = 2
3
4
1 2 3 4
4 3 4
3 2 3
4 5 3
3 3 3
3 5 7
2 3 6
4 3 7
3 3 6
1
SVM = 2
3
4
11 5 7
6 3 6
3 5 7
3 3 6
7 7 7
6 6 6
The sum of all Satisfactory value Matrix is
The Satisfactory value Matrix is
1
SVM = 2
3
4
Result:
1 2 3 4
41 42 40
6 6 6
41 43 38
6 6 6
42 43 36
6 6 6
40 38 36
6 6 6
1
SVM = 2
3
4
1 2 3 4
3 6 3
3 3 3
3 6
3 3
6 4
3 3
3 6 4
3 3 3
The resultant matching for the above instance is (1,
4) and (2, 3).This matching is obtained by using the above five mentioned parameters. The above result shows that the average satisfactory level of matching (1, 4) is 66.6% and for (2, 3) is 71.6 %.
-
N-FACTOR SATISFACTORY ROOMMATES PROBLEM WITH INCOMPLETE LIST
A classical Satisfactory Roommates problem (SFRP) in which complete preference lists will be given for each member of the group. Suppose that a person may declare one or more of the members of the opposite side to be an unacceptable partner, so that the preference list of such a person contains a proper subset of the
Preference list based on Parameter B
1
2
3 4
2
3
1
3
4
2 1
4
3
1
The Satisfactory value Matrix is
2
3
4
5
3
/td> 3
3
3
3
1
member of the opposite side. Then a person can be matched only if they are acceptable to each other [5]. We have already discussed about Satisfactory Roommates problem with incomplete preference list and it is denoted as SFRPI. That is for some member in the group of n members the preference list consists of less than n-1 members. The satisfactory matching for this type of SFRPI problem can be obtained by using SMAR algorithm described in [7].In SFRPI the participant p is acceptable to participant q if p appears on the preference list of q, and unacceptable otherwise. Here the N-Factor SFRP [6] extended into N-Factor SFRPI.
1
SVM = 2
3
4
5 5
3 3
3 5 6
3 3 3
3 6
3 3
EXAMPLE: 3.1 Here the problem is discussed with 5 different parameters, Consider the problem instance of size 4 based on order of preference.
Preference list based on Parameter A 1 3 4 2
2 4 1
3 1 4
4 2 3 1
Preference list based on Parameter C 1 4 3 2
2 1 4
3 4 1
4 3 2 1
The Satisfactory value Matrix is The Satisfactory value Matrix is
1
SVM = 2
3
4
1 2 3 4
4 4 4
3 3 3
4 4
3 3
4 6
3 3
4 4 6
3 3 3
1
SVM = 2
3
4
1 2 3 4
5 5 4
3 3 3
5 4 4
3 3 3
5 4
3 3
4 4
3 3
Preference list based on Parameter D 1 4 3
The sum of all Satisfactory value Matrix is
2
3
4
17
22
19
3
3
3
1
2 3 4
3 2 1 4
4 3 1 2
The Satisfactory value Matrix is
1
SVM = 2
3
17
3
22 15
3 3
15 17
3 3
20
3
1 2 3 4
1 4 5
3 3
4
Result:
19 17 20
3 3 3
SVM = 2
3
4
6 3
3 3
4 6 4
3 3 3
5 3 4
3 3 3
The resultant matching for the above instance is (1, 3) and (2, 4).This matching is obtained by using the above five mentioned parameters. The above result shows that the average satisfactory level of matching (1, 3) is 73.2% and for (2, 4) is 56.6 %.
-
N-FACTOR SATISFACTORY ROOMMATES PROBLEM WITH TIES AND INCOMPLETE LIST
-
Preference list based on Parameter E
|
1 |
3 |
2 4 |
|
2 |
1 |
4 3 |
|
3 |
2 |
1 |
|
4 |
1 |
2 |
Similarly the other natural generalization of Satisfactory Roommates problem (SFRP) is called Satisfactory Roommates problem with ties and incomplete lists (SFRPTI).This is also closely related to Stable Roommates with Ties and Incomplete lists (SRTI)[4,12].The variant of the Satisfactory Roommates problem which incorporates both extensions described above is denoted SFRPTI[13]. Thus an instance I of SFRPTI comprises preference lists, each of which may involve ties and/or unacceptable partners. As observed above, all satisfactory matching for a given instance of SFRPI are of the same size, and all satisfactory matching for a given instance of SFRPT are complete (and therefore of the same size). However, for a given instance of SFRPTI, it is no longer the case that all satisfactory matching need be of the same size. Furthermore, each of the problems of finding a satisfactory matching of maximum or minimum size, given an SFRPTI instance, is NP hard. With this idea we are extending the SFRPTI into N-Factor Satisfactory Roommates problem with Ties and Incomplete list.
Example 4.1 Here the problem is discussed with 5 different parameters, Consider the problem instance of size 4 based on order of preference.
Preference list based on Parameter A
|
1 |
3 |
4 |
|
|
2 |
4 |
3 |
|
|
3 |
2 |
(4 |
1) |
|
4 |
(3 |
1) |
2 |
The Satisfactory value Matrix is
|
2 |
3 |
4 |
||
|
9 |
10 |
8 |
||
|
6 |
6 |
6 |
1
1
9
8
SVM = 2 6 6
3 10 9
6 6
4 8 8 9
6 6 6
The Satisfactory value Matrix is
Preference list based on Parameter D
1
1
SVM = 2
3 9
|
9 |
8 |
8 |
||
|
6 |
6 |
6 |
6
4
2 3 4
9 9
6 6
10 8
6 6
10 8
6 6
1 4 (2 3)
2 3 1
3 1 (4 2)
4 1 3
The Satisfactory value Matrix is
Preference list based on Parameter B 1 2 4
2 (3 4) 1
3 4 2
4 (2 1) 3
1
SVM = 2
3
4
1 2
9
6
9
6
4 9
6 6
11
6
3 4
4 11
6 6
9
6
7
6
7
6
The Satisfactory value Matrix is
Preference list based on Parameter E
1
SVM = 2
3
4
1 2
8
6
8
6
9
6
9 10
3 4
9
6
9 10
6 6
8
6
8
1 2 3
2 (3 4) 1
3 1 4 2
4 (2 3)
The Satisfactory value Matrix is
6 6 6
1 2 3 4
1 8 10
Preference list based on Parameter C
6
|
1 |
3 |
2 |
4 |
SVM = |
|
|
2 |
(4 |
1) |
3 |
||
|
3 |
4 |
1 |
4 |
||
|
4 |
1 |
(3 |
2) |
||
2 8
6
10 7
6 6
10
6
6
7 10
6 6
9
6
9
6
The sum of all Satisfactory value Matrix is V.CONCLUSION
1
SVM = 2
3
4
1 2 3 4
34 33 37
6 6 6
34 35 36
6 6 6
33 30 41
6 6 6
37 36 41
3 6 6
Many researchers described Roommates problem considering only one factor and solved by using their methods so far, in this paper we presented an N-Factor roommates problem and solved it by using SMAR algorithm. The concept is analyzed by solving RP with ties, incomplete list, ties and incomplete list. After examining the results we find that, this algorithm results a matching in which each pair attains maximum satisfactory level. So SMAR results N-Factor Satisfactory matching of roommates problem with all other extended cases.
Result:- The resultant matching for the above instance is (1, 2) and (3, 4).This matching is obtained by using the above five mentioned parameters. The above result shows
that the average satisfactory level of matching (1, 2) is 68.3% and for (3, 4).is 56.6 %.
REFERENCES
-
D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962.
-
Robert W.Irving and David F.Manlove.The Stable Roommate Problem with Ties. Journal of Algorithms 43(1):85-105, 2002.
-
Tamas Fleiner, Robert W.Irving and David F.Manlove. Efficient algorithms for generalized Stable Marriage and Roommates problems. Theoretical Computer Science 381 (2007) 162176.
-
Sandy Scott, A Study Of Stable Marriage Problems With Ties – Ph.D Thesis, University of Glasgow-2005.
-
D. Gusfield and R.W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.
-
T.Ramachandran and T. Selvakumar, N-Factor Satisfactory Roommates problem. Proceedings of International Conference on Mathematical Sciences, 2014, No. 1, pp. 116-118.
-
T. Ramachandran, K. Velusamy and T. Selvakumar, Satisfactory Roommates problem. International journal of Mathematical Archives.2 (9), 2011, 1679-1682.
-
T. Ramachandran, K. Velusamy and T. Selvakumar, Satisfactory Roommates Problem with Incomplete List. International Journal of Computational Science and Mathematics.ISSN 0974-3189 Volume 4, Number 1 (2012), pp. 19-22
-
R.W. Irving. An efficient algorithm for the Stable roommates problem. Journal of Algorithms, 6:577-595, 1985.
-
D.E. Knuth. Stable Marriage and its Relation to Other Combinatorial Problems, volume 10 of CRM Proceedings and Lecture Notes. American Mathematical Society, 1997. English translation of Mariages Stables, Les Presses de L'Universite de Montreal, 1976.
-
A.E. Roth and M.A.O. Sotomayor. Two-sided matching: a study in game-theoretic modeling and analysis, volume 18 of Econometric Society Monographs. Cambridge University Press, 1990.
-
Gregg OMalley, Algorithmic aspects of stable matching problems – Ph.D Thesis. University of Glasgow-2007.
-
T.Ramachandran, D.Udhayakumar and T. Selvakumar, Satisfactory Roommates problem with Ties, Ties and incomplete list. International Journal of Scientific Research, Volume 3, Issue 10, October 2014, ISSN 2277 8179.