Lecture Notes in Computer Science
2 primary works
Book 538
A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems
by Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, and Akiko Yoshise
Published 25 September 1991
Following Karmarkar's 1984 linear programming algorithm,
numerous interior-point algorithms have been proposed for
various mathematical programming problems such as linear
programming, convex quadratic programming and convex
programming in general. This monograph presents a study of
interior-point algorithms for the linear complementarity
problem (LCP) which is known as a mathematical model for
primal-dual pairs of linear programs and convex quadratic
programs. A large family of potential reduction algorithms
is presented in a unified way for the class of LCPs where
the underlying matrix has nonnegative principal minors
(P0-matrix). This class includes various important
subclasses such as positive semi-definite matrices,
P-matrices, P*-matrices introduced in this monograph, and
column sufficient matrices. The family contains not only the
usual potential reduction algorithms but also path following
algorithms and a damped Newton method for the LCP. The main
topics are global convergence, global linear convergence,
and the polynomial-time convergence of potential reduction
algorithms included in the family.
numerous interior-point algorithms have been proposed for
various mathematical programming problems such as linear
programming, convex quadratic programming and convex
programming in general. This monograph presents a study of
interior-point algorithms for the linear complementarity
problem (LCP) which is known as a mathematical model for
primal-dual pairs of linear programs and convex quadratic
programs. A large family of potential reduction algorithms
is presented in a unified way for the class of LCPs where
the underlying matrix has nonnegative principal minors
(P0-matrix). This class includes various important
subclasses such as positive semi-definite matrices,
P-matrices, P*-matrices introduced in this monograph, and
column sufficient matrices. The family contains not only the
usual potential reduction algorithms but also path following
algorithms and a damped Newton method for the LCP. The main
topics are global convergence, global linear convergence,
and the polynomial-time convergence of potential reduction
algorithms included in the family.
Book 3521
The papers in this volume were presented at the 1st International Conference on Algorithmic Applications in Management (AAIM 2005), held June 22-25, 2005 in Xi'an, China. The topics cover algorithmic applications in most manageme- related areas. Submissions to the conference this year were conducted electronically. A - tal of 140 papers were submitted, of which 46 were accepted. The papers were evaluated by an international Program Committee consisting of Franz Aur- hammer, Sergey Bereg, Danny Z. Chen, Jian Chen, Zhixiang Chen, Edith - hen, Xiaotie Deng, Michael Goldwasser, Jason Hartline, Wen-Lian Hsu, Haijun Huang, Minghui Jiang, Ellis Johnson, Naoki Katoh, Masakazu Kojima, Moh- mad Mahdian, Nimrod Megiddo, Zhongping Qin, Panos Pardalos, Chung Keung Poon, Bruce Reed, Shouyang Wang, Peter Widmayer, Yinfeng Xu, Frances Yao, Yinyu Ye and Binhai Zhu. The submitted papers were from Canada, Chile, China, Finland, Germany, Hong Kong, Iran, Israel, Japan, Korea, Malaysia, Mexico, Netherlands, Singapore, UK and USA. Each paper was evaluated by at least two Program Committee members, assisted in some cases by subreferees.
In addition to selected papers, the conference also included two invited presentations, by Ellis Johnson and Yinyu Ye, and two invited papers, by Xujin Chen et al. and Siu-Wing Cheng et al. We thank all the people who made this meeting possible: the authors for s- mitting papers, the Program Committee members and external referees (listed on the pages that follows) for their excellent work, and the two invited speakers.
In addition to selected papers, the conference also included two invited presentations, by Ellis Johnson and Yinyu Ye, and two invited papers, by Xujin Chen et al. and Siu-Wing Cheng et al. We thank all the people who made this meeting possible: the authors for s- mitting papers, the Program Committee members and external referees (listed on the pages that follows) for their excellent work, and the two invited speakers.