       Kitahara Tomonari Last modified date：2019.04.16 Graduate School

E-Mail Phone
092-642-2469
Academic Degree
Doctor of Engineering
Country of degree conferring institution (Overseas)
No
Field of Specialization
Mathematical Programming, Operations Research
Total Priod of education and research career in the foreign country
00years00months
Research
Research Interests
• Theoretical properties of linear programming algorithms
keyword : Linear programming problem, algorithm, the simplex method, mathematical programming
2018.04.
Academic Activities
Papers
 1 Tomonari Kitahara and Noriyoshi Sukegawa, A simple projection algorithm for linear programming problems, Algorithmica, 10.1007/s00453-018-0436-3, 2018.03, Fujishige et al. propose the LP-Newton method, a new algorithm for linear programming problem (LP). They address LPs which have a lower and an upper bound for each variable, and reformulate the problem by introducing a related zonotope. The LP-Newton method repeats projections onto the zonotope by Wolfe’s algorithm. For the LP-Newton method, Fujishige et al. show that the algorithm terminates in a finite number of iterations. Furthermore, they show that if all the inputs are rational numbers, then the number of projections is bounded by a polynomial in L, where L is the input length of the problem. In this paper, we propose a modification to their algorithm using a binary search. In addition to its finiteness, if all the inputs are rational numbers and the optimal value is an integer, then the number of projections is bounded by L+1, that is, a linear bound.. 2 Tomonari Kitahara, Shinji Mizuno, and Jianming Shi, The LP-Newton method for standard form linear programming problems, Operations Research Letters, 41, 426-429, 2013.09. 3 Tomonari Kitahara and Takashi Tsuchiya, A simple variant of the Mizuno-Todd-Ye predictor-corrector algorithm and its objective-function-free complexity, SIAM Journal on Optimization, 23, 1890-1903, 2013.09. 4 Tomonari Kitahara and Shinji Mizuno, A bound for the number of basic solutions generated by the simplex method, Mathematical Programming, 137, 579-586, 2013.02. 5 Tomonari Kitahara and Shinji Mizuno, On the number of solutions generated by the dual simplex method, Operations Research Letters, 40, 172-174, 2012.05.
Presentations
Membership in Academic Society
• The Operations Research Society of Japan 