書式設定,書式設定,第 2,第 3,第 4,第 5,2007/5/14,全体会議,*,書式設定,書式設定,第 2,第 3,第 4,第 5,2007/5/14,全体会議,*,特定領域全体会議,A10,班,変移要素間関係条件組合最適化,研究組織：,宮野英次（九州工業大学）,廣瀬英雄（九州工業大学）,朝廣雄一（九州産業大学）,2007/5/14,1,全体会議,特定領域全体会議A10班変移要素間関係条件,目標,最適化,2007/5/14,2,全体会議,，静的，固定的,，未知情報,目標最適化2007/5/142全体会議，静的,論文会議録,Y.Asahiro,E.Miyano,and S.Shimoirisa.K-collect tours for moving objects with release time and deadline,Proc World Multi-Conf Systems,Cybernetics and Informatics,2005.,Y.Asahiro,.Simple greedy methods for DNA word design.Proc World Multi-Conf Systems,Cybernetics and Informatics,2005.,H.Hirose,.Optimal boundary finding method for the bumpy regions.Proc Int.Federation of Operational Research Societies Conference,2005.,Y.Asahiro,E.Miyano,and S.Shimoirisa.Pickup and delivery for moving objects on broken lines,Proc Italian Conference on Theoretical Computer Science(ICTCS),2005.,Y.Asahiro,E.Miyano,H.Ono,and K.Zenmyo.Graph orientation algorithms to minimize the maximum outdegree.Proc Computing:Australasian Theory Symp(CATS),2006.,H.Hirose,T.Yukizane,E.Miyano,.The bump hunting method using the genetic algorithm and the extreme-value statistics with application to a messy customer database.Proc Hawaii Int.Conference on Statistics,Mathematics and Related Fields,2006.,2007/5/14,3,全体会議,論文会議録Y.Asahiro,E.Miyano,a,論文会議録,Y.Asahiro,T.Furukawa,K.Ikegami,and,E.Miyano,.How to pack directed acyclic graphs into small blocks.Proc Int.Conference on Algorithms and Complexity(CIAC),2006.,H.Hirose,T.Yukizane,and,E.Miyano,.Boundary detection for bumps using the Ginis index in messy classification problems.Proc Int Conference on Cybernetics and Information Technologies,Systems and Applications,2006.,T.Yukizane,S.Ohi,E.Miyano,and,H.Hirose,.The bump hunting method using the genetic algorithm with the extreme-value statistics.IEICE Trans on Information and Systems,2006.,Y.Kiyonari,E.Miyano,and,S.Miyazaki,.Computational complexity issues in university interview timetabling.Proc Int Conference on the Practice and Theory of Automated Timetabling(PATAT),2006.,Y.Asahiro,T.Horiyama,K.Makino,H.Ono,T.Sakuma,and,M.Yamashita,.How to collect balls moving in the Euclidean plane.Discrete Applied Mathematics,2006.,2007/5/14,4,全体会議,論文会議録Y.Asahiro,T.Furukawa,論文会議録,Y.Asahiro,E.Miyano,S.Miyazaki,and T.Yoshimuta.Weighted nearest neighbor algorithms for the graph exploration problem on cycles.Proc Conference on Current Trends in Theory and Practice of Informatics(SOFSEM),2007.,H.Hirose,S.Ohi,T.Yukizane.Assessment of the prediction accuracy in the bump hunting procedure.Proc Hawaii Int Conf Statistics,Mathematics,and Related Fields,2007.,Y.Asahiro,E.Miyano,H.Ono,and K.Zenmyo.Graph orientation algorithms to minimize the maximum outdegree.International Journal of Foundation of Computer Science,2007.,Y.Asahiro,J.Jansson,E.Miyano,H.Ono,and K.Zenmyo.Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree.Proc Conf on Algorithmic Aspects in Information and Management(AAIM),2007.,K.Iwama,E.Miyano,and,H.Ono,.Drawing borders efficiently.Proc Int Conf on FUN with Algorithms(FUN),2007.,Y.Asahiro,E.Miyano,and S.Shimoirisa.Grasp and delivery for moving objects on broken lines.Theory of Computing Systems,to appear.,2007/5/14,5,全体会議,論文会議録Y.Asahiro,E.Miyano,S,経路最適化,2007/5/14,6,全体会議,経路最適化2007/5/146全体会議,静的,TSP,（巡回問題）,固定点,移動距離,最小化問題,制約（，平面，三角不等式，）,2007/5/14,7,全体会議,静的TSP（巡回問題）200,動的,低速移動,TSP,低速移動点,移動距離,最小化問題,制約（軌跡，移動点個数，）,2007/5/14,8,全体会議,動的低速移動TSP2007/5/148全体,動的,低速移動,TSP,低速移動点,移動距離,最小化問題,制約（軌跡，移動点個数，）,Chalasani,Motwani,Rao,IWAFR(1996),Helvig,Robins,Zelikovsky.ESA(1998),Hammar and Nilsson,ICALP(1999),2007/5/14,9,全体会議,動的低速移動TSP Chalasani,（課題）,動的,+,高速移動,TSP,高速移動点,個数,最大化,問題,2007/5/14,10,全体会議,（課題）動的+高速移動TSP2007/5,（課題）,動的,+,Y.Asahiro,E.Miyano,and S.Shimoirisa.Grasp and delivery for moving objects on broken lines.,Theory of Computing Systems,to appear.,条件：,容量制約：,移動軌跡：折線上,結果：,直線移動場合,O(,n,log n,),時間,一度以上曲場合,MAXSNP,困難,2,近似,記事：,朝廣，小野，宮野，山下移動物体回収問題電子情報通信学会誌,2007,年,3,月号,2007/5/14,11,全体会議,（課題）動的+Y.Asahiro,E,（課題）,TSP,局所情報,移動距離,最小化問題,制約,A,B,5,10,?,?,2007/5/14,12,全体会議,未知,（課題）TSPAB510?20,（課題）,TSP,局所情報,移動距離,最小化問題,制約,A,B,5,10,C,20,?,?,2007/5/14,13,全体会議,未知,（課題）TSPAB510C20?,（課題）,TSP,局所情報,移動距離,最小化問題,制約,A,B,5,10,C,20,?,?,40,D,前進,or,後退,2007/5/14,14,全体会議,（課題）TSPAB510C20?,（課題）,Y.Asahiro,E.Miyano,S.Miyazaki,and T.Yoshimuta.Weighted nearest neighbor algorithms for the graph exploration problem on cycles,SOFSEM2007,.,前進,or,後退？,ALG(),If,（前進距離）後退距離，,Then,後退,Else,前進,既知,前進距離,後退距離,2007/5/14,15,全体会議,（課題）Y.Asahiro,E.Mi,（課題）,Y.Asahiro,E.Miyano,S.Miyazaki,and T.Yoshimuta.Weighted nearest neighbor algorithms for the graph exploration problem on cycles,SOFSEM2007,.,前進,or,後退？,ALG(3),If 3,（前進距離）後退距離，,Then,後退,Else,前進,既知,10,25,2007/5/14,16,全体会議,後退,（課題）Y.Asahiro,E.Mi,（課題）,Y.Asahiro,E.Miyano,S.Miyazaki,and T.Yoshimuta.Weighted nearest neighbor algorithms for the graph exploration problem on cycles,SOFSEM2007,.,前進,or,後退？,ALG(),If,（前進距離）後退距離，,Then,後退,Else,前進,既知,前進距離,後退距離,Rosenkrantz,Stearns,Lewis.,SIAM J Comp,(1997),ALG(1),(,log