A dual version of tardos's algorithm for linear programming |
| |
| Institution: | 1. LabCAV, Laboratory of Advanced Control, University of 8 May 1945 Guelma. BP 401, 24000 Guelma, Algeria;2. LMFN, Laboratoire de Mathématiques Fondamentales et Numériques, Département de Mathématiques, Faculté des Sciences, Université Ferhat Abbas Sétif-1, Algeria;3. Normandie University, UNIHAVRE, LMAH, FR-CNRS-3335, ISCN, 76600 Le Havre, France;1. Graduate School of Decision Science and Technology, Tokyo Institute of Technology, Tokyo, Japan;2. Department of Information and System Engineering, Chuo University, Tokyo, Japan;3. Advanced Optimization Laboratory, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada |
| |
| Abstract: | Recently, Eva Tardos developed an algorithm for solving the linear program min (cx:Ax = b, x ≥ 0 whose solution time is polynomial in the size of A, independent of the sizes of c and b. Her algorithm focuses on the dual LP and employs an approximation of the cost coefficients. Here we adopt what may be called a ‘dual approach’ in that if focuses on the primal LP. This dual approach has some significant differences from Tardo's approach which make the dual approach conceptually simpler. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
