{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T06:10:25Z","timestamp":1697868625458},"reference-count":5,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,9,5]],"date-time":"2007-09-05T00:00:00Z","timestamp":1188950400000},"content-version":"vor","delay-in-days":8282,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1985,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Scheduling of meetings is one of the basic functions demanded in office automation. With respect to the automation of this function, the Meeting Timetable Rearrangement problem (MTR) to update a current meeting timetable for an additional meeting has been formulated. However, it has already been shown that MTR is NP\u2010hard. Consequently, we should develop an approximation algorithm or a heuristic algorithm for MTR. Such an algorithm is required to find a feasible solution which satisfies all constraints, but not necessarily an optimal solution. This paper discusses a problem to determine whether or not there exists a feasible solution for a given instance of MTR. First, we show that this problem is NP\u2010complete. That is, there is no polynomial\u2010time approximation algorithm for MTR unless P = NP. This implies that we should develop a heuristic algorithm for MTR. Second, we present a polynomial\u2010time algorithm which finds a feasible solution for a subproblem of MTR. By combining this algorithm and a hill\u2010climbing approach, an efficient heuristic algorithm can be developed.<\/jats:p>","DOI":"10.1002\/scj.4690160309","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T09:48:00Z","timestamp":1183801680000},"page":"77-84","source":"Crossref","is-referenced-by-count":0,"title":["Feasibility problem for meeting timetable rearrangement"],"prefix":"10.1002","volume":"16","author":[{"given":"Kazuo","family":"Sugihara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tohru","family":"Kikuno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noriyoshi","family":"Yoshida","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazunori","family":"Arame","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,9,5]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Fundamentals of Computer Algorithms","author":"Horowitz E.","year":"1978"},{"key":"e_1_2_1_3_2","unstructured":"T.Kikuno N.Yoshida K.SugiharaandK.Arame.Scheduling of meeting in office information systems Proc. COMPSAC1982 pp.318\u2013325(1982)."},{"key":"e_1_2_1_4_2","unstructured":"K.Sugihara T.KikunoandN.Yoshida.Toward the enhancement of facilities of meeting scheduler CSG Tech. Rep. No. 83\u201098 Hiroshima Univ. (1983)."},{"issue":"4","key":"e_1_2_1_5_2","first-page":"361","article-title":"Fundamental considerations on the rearrangement of meeting timetable","volume":"66","author":"Kikuno T.","year":"1983","journal-title":"Trans. I.E.C.E., Japan"},{"key":"e_1_2_1_6_2","unstructured":"T.Kikuno N.Yoshida K.SugiharaandK.Arame.Feasible solutions for meeting timetable rearrangement problem Technical Paper of I.E.C.E. Japan TGAL82\u201079 (1983)."}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690160309","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690160309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T18:22:05Z","timestamp":1697826125000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690160309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,1]]},"references-count":5,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,1]]}},"alternative-id":["10.1002\/scj.4690160309"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690160309","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,1]]}}}