# Selected Papers

## Recent Working Papers

New results on quadratic minimization . Posted 5/30/01. This work is supported by NSF grants DMI-9908077 and DMS-9703490.

On Solving Fewnomials Over Intervals in Fewnomial Time . Posted 8/22/01. This work is supported by DMS-9703490.

An Approximation Algorithm for the Two-Parallel Machines Scheduling Problem with Capacity Constraints . This work is supported by NSF grants DMI-9908077 and DMS-9703490 (2000).

is available. Click here for the Improved Approximation for Max Set Splitting and Max NAE SAT . Revised 1/20/02. This work is supported by NSF grants DMI-9908077 and DMS-9703490 (2000).

is available. Click here for the Solving Sparse Semidefinite Programs Using the Dual Scaling Algorithm with an Iterative Solver . This work is supported by NSF grants DMI-9908077 and DMS-9703490 (2000).

.586 Approximation of Dense-n/2-Subgraph and .602 Approximation of the Complement of Min-Bisection (Ye and Zhang) Working Paper, Department of Management Sciences, The University of Iowa (May 1999).

Convergence behavior of the central path for homogeneous and self-dual cones (Y. Ye), Working Note, Department of Management Sciences, The University of Iowa (December, 1995).

Approximating quadratic programming with bound constraints Working Paper, Department of Management Sciences, The University of Iowa (Mar, 1997).

Top of Publications / Ye's Homepage

## Forthcoming Publications

An Improved Rounding Method and Semidefinite Programming Relaxation for Graph Partition (Han, Ye and Zhang), Working Paper, Department of Management Sciences, The University of Iowa (1999), to appear in Mathematical Programming.
Top of Publications / Ye's Homepage

## Publications

Blind Channel Equalization and Approximation Algorithms (Li, Bai and Ye) IEEE Trans. on Signal Processing 49:11 (2001) 2823-2831.

A .699-approximation algorithm for Max-Bisection (Y. Ye), Mathematical Programming 90 (2001) 101-111.

Approximating Maximum Stable Set and Minimum Graph Coloring Problems with the Positive Semidefinite Relaxation (Benson and Ye), in M. Ferris and J. Pang eds., Applications and Algorithms of Complementarity (Kluwer Academic Publishers, 2000) 1-18.

Application of Semidefinite Programming to Circuit Partitioning (C. Choi and Y. Ye), in P. Pardalos eds., Approximation and Complexity in Numerical Optimization (Kluwer Academics Publishers, 2000) 130-136.

Convergence results of analytic center estimator Analytic center approach to bounded error parameter (E. Bai, M. Fu, R. Tempo, and Y. Ye), IEEE Transactions on Automatic Control, March (2000).

Solving large-scale sparse semidefinite programs for combinatorial optimization (S. Benson, Y. Ye, and X. Zhang), SIAM J. Optimization 10 (2000) 443-461.

A simplification to A Primal-Dual Interior Point Method Whose Running Time Depends Only on the Constraint Matrix'' (S. Vavasis and Y. Ye), in S. Zhang et al, eds., High Performance Optimization, Applied Optimization 33 (2000) 233-243.

On smoothing methods for the P0 matrix linear complementarity problem (X. Chen and Y. Ye), SIAM J. Optimization 11 (2001) 341-363.

An efficient algorithm for minimizing a sum of P-norms (G. Xue and Y. Ye), SIAM J. Optimization 10 (2000) 551-579.

Approximating global quadratic optimization with convex quadratic constraints (Ye), Journal of Global Optimization 15 (1999) 1-17.

Mixed Linear and Semidefinite Programming for Combinatorial and Quadratic Optimization (Benson, Ye and Zhang), Optimization Methods and Software 11&12 (1999) 515-544.

On Homotopy-Smoothing Methods for Variational Inequalities (X. Chen and Y. Ye), SIAM J. Control & Optimization 37 (1999) 589-616.

On a homogeneous algorithm for the monotone complementarity problem (E. Andersen and Y. Ye), Mathematical Programming 84 (1999) 375-400.

Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems (Yu. Nesterov, M.J. Todd, and Y. Ye), Mathematical Programming 84, (1999) 227-267.

Approximating quadratic programming with bound and quadratic constraints (Ye) Mathematical Programming 84, (1999) 219-226.

Bounded Error Parameter Estimation: A Sequential Analytic Center Approach (E. Bai, Y. Ye and R. Tempo), IEEE Transactions on Automatic Control 44:6, (1999) 1107-1117.

Probabilistic Analysis of an Infeasible Primal--Dual Algorithm for Linear Programming (K. Anstreicher, J. Ji, F. Potra and Y. Ye), Mathematics of Operations Research 24, (1999) 176-192.

Constrained Logarithmic Least Squares in Parameter Estimation (E. Bai and Y. Ye), IEEE Transactions on Automatic Control 44:1, (1999) 182-185.

Semidefinite Relaxations, Multivariate Normal Distributions, and Order Statistics (D. Bertsimas and Y. Ye), Handbook of Combinatorial Optimization (Vol. 3), D.-Z. Du and P.M. Pardalos (Eds.) pp. 1-19, (1998 Kluwer Academic Publishers).

Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming (M. J. Todd and Y. Ye), Mathematical Programming 81, (1998) 1-22.

Approximation algorithms for quadratic programming (M. Fu, Z.-Q. Luo, and Y. Ye), Journal of Combinatorial Optimization 2(1) (1998) 29-50.

A computational study of the homogeneous algorithm for large-scale convex optimization (E. Andersen and Y. Ye), Computational Optimization and Applications 10, (1998) 243-269.

On the complexity of approximating a KKT point of quadratic programming (Y. Ye), Mathematical Programming 80, (1998) 195-212.

On a homogeneous algorithm for a monotone complementarity problem with nonlinear equality constraints (E. Andersen and Y. Ye), in Michael C. Ferris and Jong-Shi Pang, eds., Complementarity and variational Problems: State of the art (SIAM, 1997) pp. 1-11.

Complexity analysis of the analytic center cutting plane method that uses multiple cuts (Y. Ye), Mathematical Programming 78, (1997) 85-104.

Efficient algorithms for minimizing a sum of Euclidean norms with applications (G. Xue and Y. Ye), SIAM J. Optimization 7, (1997) 1017-1036.

An infeasible interior-point algorithm for solving primal and dual geometric programs (K. O. Kortanek, X. Xu, and Y. Ye), Mathematical Programming 76, (1997) 155-182.

On homogeneous and self-dual algorithm for LCP (Y. Ye), Mathematical Programming 76, (1997) 211-222.

Improved complexity using higher-order correctors for primal-dual Dikin affine scaling (B. Jansen, C. Roos, T. Terlaky and Y. Ye), Mathematical Programming 76, (1997) 117-130.

How partial knowledge helps to solve linear programs (Y. Ye), Journal of Complexity 12, (1996) 480-491.

Combining interior-point and pivoting algorithms for linear programming (E. D. Andersen and Y. Ye), Management Science 42, (1996) 1719-1731.

A primal-dual interior-point method whose running time depends only on the constraint matrix (S. Vavasis and Y. Ye), Mathematical Programming 74, (1996) 79-120.

A asymptotical $O(\sqrt{n}L)$-iteration path-following linear programming algorithm that uses long steps (P. Hung and Y. Ye), SIAM J. Optimization 6, (1996) 570-586.

Complexity analysis of an interior-point cutting plane method for convex feasibility problem (J. Goffin, Z. Luo and Y. Ye), SIAM J. Optimization 6, (1996) 638-652.

Interior-point methods for nonlinear complementarity problem (F. Potra and Y. Ye), Journal of Optimization Theory and Application 68, 1996.

A simplified homogeneous and self-dual linear programming algorithm and its implementation (X. Xu, P. Hung and Y. Ye), Annals of Operations Research 62, (1996) 151-172.

A lower bound on the number of iterations of long-step and polynomial interior-point linear programming algorithms (M. Todd and Y. Ye), Annals of Operations Research 62, (1996) 233-252.

Identifying an optimal basis in linear programming (S. Vavasis and Y. Ye), Annals of Operations Research 62, (1996) 565-572.

Condition numbers for polyhedra with real number data (S. Vavasis and Y. Ye), Operations Research Letters 17, (1995) 209-214.

A generalized homogeneous and self-dual linear programming algorithm (X. Xu and Y. Ye), Operations Research Letters 17, (1995).

On the von Neumann economic growth problem, Mathematics Operations Research 20, (1995) 617-633.

A convergent algorithm for quantile regression with smoothing splines (R. J. Bosch, Y. Ye, and G. G. Woodworth), Computational Statistics & Data Analysis 19, (1995) 613-630.

Specially structured uncapacitated facility location problems (P. Jones, T. Lowe, G. Muller, N. Xu, Y. Ye, and J. Zydiak), Operations Research 43, (1995) 661-669.

A surface of analytic centers and infeasible-interior-point algorithms for linear programming (S. Mizuno, M. Todd, and Y. Ye), Mathematics of Operations Research 20, (1995) 135-162.

An $O(\sqrt{n}L)$-iteration homogeneous and self-dual linear programming algorithm (Y. Ye, M. Todd and S. Mizuno), Mathematics of Operations Research 19, (1994) 53-67.

Combining binary search and Newton's method to compute real roots for a class of real functions, Journal of Complexity 10, (1994) 271-280.

Average performance of a self-dual interior-point algorithm for linear programming (K. Anstreicher, J. Ji, F. Potra and Y. Ye), in P. Pardalos eds., Complexity in Numerical Optimization, (World Scientific, New Jersey, 1993) pp. 1-15.

Toward probabilistic analysis of interior-point algorithms for linear programming, Mathematics of Operations Research 19, (1994) 38-52.

On the convergence of the iteration sequence in primal-dual interior-point methods (R. Tapia, Y. Zhang and Y. Ye), Mathematical Programming 68, (1995) 141-154.

On quadratic and $O(\sqrt{n}L)$ convergence of a predictor- corrector algorithm for LCP (Y. Ye and K. Anstreicher), Mathematical Programming 62, (1993) 537-552.

A complexity analysis for interior-point algorithms based on Karmarkar's potential functions (J. Ji and Y. Ye), SIAM J. on Optimization 4, (1994) 512-520.

Translation cuts for convex minimization, (J. Burke A. Goldstein, P. Tseng and Y. Ye), in P. Pardalos eds., Complexity in Numerical Optimization, (World Scientific, New Jersey, 1993) pp. 57-73.

The optimal choice of inputs under time of use pricing, fixed proportions technology and adjustment costs: an application to industrial firms (Y. Spector, A. Tishler and Y. Ye), Management Sciences 41, (1995) 1679-1692.

A decomposition variant of the potential reduction algorithm for linear programming (J. Kaliski and Y. Ye), Management Science 39, (1993) 757-776.

Minimal adjustment costs, factor demands, and seasonal time-of-use electricity rates (A. Tishler and Y. Ye), Resource and Energy Economics 15, (1993) 313-335.

On finding an interior point on the optimal face of linear programs (S. Mehrotra and Y. Ye), Mathematical Programming 62, (1993) 497-516.

On the finite convergence of interior-point algorithms for linear programming, Mathematical Programming 57, (1992) 325-335.

A quadratically convergent $O(\sqrt{n}L)$-iteration algorithm for linear programming (Y. Ye, O. G\"uler, R. Tapia and Y. Zhang), Mathematical Programming 59, (1993) 151-162.

Convergence behavior of some interior-point algorithms (O. G\"uler and Y. Ye), Mathematical Programming 60, (1993) 215-228.

A fully polynomial-time approximation algorithm for computing a stationary point of the general LCP, Mathematics of Operations Research 18, (1993) 334-345.

A quadratically convergent polynomial interior-point algorithm for solving entropy optimization problems (F. Potra and Y. Ye), SIAM J. on Optimization 3, (1993) 843-860.

On adaptive-step primal-dual interior-point algorithms for linear programming (S. Mizuno, M. Todd and Y. Ye), Mathematics of Operations Research 18, (1993) 964-981.

A further result on potential reduction algorithm for the P-matrix linear complementarity problem, in P. Pardalos eds., Advances in Optimization and Parallel Computing, (North-Holland, NY, 1992).

Implementation of interior-point algorithms for some entropy optimization problems (C. Han, P. Pardalos and Y. Ye), Optimization Methods and Software 1, (1992) 71-80.

Solutions of $P_0$-matrix linear complementarity problems (P. Pardalos, Y. Ye, C. Han and J. Kaliski), SIAM J. on Matrix Anal. Appl. 14, (Oct. 1993) 1048-1060.

Near-boundary behavior of the primal-dual potential reduction algorithm for linear programming (Y. Ye, K. Kortanek, J. Kaliski and S. Huang), Mathematical Programming 58, (1993) 243-255.

A new complexity result on minimization of a quadratic function with a sphere constraint, in C. Floudas and P. Pardalos eds., Recent Advances in Global Optimization, (Princeton University Press, NJ, 1992).

A potential reduction algorithm allowing column generation, SIAM J. on Optimization 2, (1992) 7-20.

Convergence behavior of Karmarkar's projective algorithm for solving a simple linear program (J. Kaliski and Y. Ye), Operations Research Letters 10, (1991) 389-393.

Comparative analysis of affine scaling algorithms for linear programming, Mathematical Programming 52, (1992) 405-414.

An extension of the potential reduction algorithm for solving LCP with priority goals (J. Kaliski and Y. Ye), Linear Algebra and its Applications 193, (1993) 35-50.

On affine scaling algorithms for nonconvex quadratic programming, Mathematical Programming 56, (1992) 285-300.

Extensions of the potential reduction algorithm for linear programming, Journal of Optimization Theory and Applications 72, (1992) 487-498.

On some efficient interior point methods for nonlinear convex programming (K. Kortanek, F. Potra and Y. Ye), Linear Algebra and its Applications 152, (1991) 169-189.

Interior-point algorithms for quadratic programming, in S. Kumar ed., Recent Developments in Mathematical Programming, (Gordon \& Breach Scientific Publishers, Philadelphia, 1991).

Computational aspects of an interior point algorithm for quadratic programming problems with box constraints (C. Han, P. Pardalos and Y. Ye), in T.~F. Coleman and Y. Li eds., Large-Scale Numerical Optimization, (SIAM, Philadelphia, 1990).

Interior-point algorithms for global optimization, Annals of Operations Research 25, (1990) 59-74.

A class of LCPs solvable in polynomial time (Y. Ye and P. Pardalos), Linear Algebra and its Applications 152, (1991) 3-17.

Algorithms for the solution of quadratic knapsack problems (P. Pardalos, C. Han and Y. Ye), Linear Algebra and its Applications 152, (1991) 69-91.

Containing and shrinking ellipsoids in the path-following algorithm (Y. Ye and M. Todd), Mathematical Programming 47, (1990) 1-9.

A class of projective transformations for linear programming, SIAM J. on Computing 19, (1990) 457-466.

An $O(n^3L)$ potential reduction algorithm for linear programming, Mathematical Programming 50, (1991) 239-258.

An interior point potential reduction algorithm for the linear complementarity problem (M. Kojima, N. Megiddo and Y. Ye), Mathematical Programming 54, (1992) 267-279.

A centered projective algorithm for linear programming (M. Todd and Y. Ye), Mathematics of Operations Research 15, (1990) 508-529.

Recovering optimal basic variables in Karmarkar's polynomial algorithm for linear programming, Mathematics of Operations Research 15, (1990) 564-571.

A build-down'' scheme for linear programming, Mathematical Programming 46, (1990) 61-72.

An extension of Karmarkar's algorithm and the trust region method for quadratic programming, in Progress in Mathematical Programming, N. Megiddo ed., Springer-Verlag New York (1989) 49-63.

An extension of Karmarkar's projective algorithm for convex quadratic programming (Y. Ye and E. Tse), Mathematical Programming 44, (1989) 157-179.

Eliminating columns in the simplex method for linear programming, Journal of Optimization Theory and Applications 63, (1989) 103-111.

Karmarkar's algorithm and the ellipsoid method, Operations Research Letters 4, (1987) 177-182.

Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming (Y. Ye and M. Kojima), Mathematical Programming 39, (1987) 305-317.

A conclusion on `missing number' in ergodic exponents of $s\times s$ stochastic matrices, Journal of Huazhong University of Science and Technology 2, (1983).

Directed graphs, linear Diophantine equations, and ergodic problems of stochastic matrices, English Edit., Journal of Huazhong University of Science and Technology 2, (1982).

An accelerated interior-point method whose running time depends only on $A$ (S. Vavasis and Y. Ye), Proc. of the Twenty-Sixth ACM Symposium on Theory of Computing, (1994) 512-521.

A genuine quadratically convergent polynomial interior point algorithm for linear programming (Z.-Q. Luo and Y. Ye) in Ding-Zhu Du and Jie Sun, eds., Advances in Optimization and Approximation (Kluwer Academic Publishers, Boston, 1994).

On the complexity of a column generation algorithm for convex or quasiconvex feasibility problems,'' (J. Goffin, Z. Luo and Y. Ye), in W. Hager, D. Hearn and P. Pardalos eds., Large Scale Optimization: State of the Art (Kluwer Academic Publishers, Boston, 1994) pp. 182-191.

On the Q-order of convergence of interior-point algorithms for linear programming,'' in Wu Fang, ed., Proc. of the 1992 Symp. on Applied Mathematics (Institute of Applied Mathematics, Chinese Academy of Sciences, 1992).

## Working Papers

On the quadratic convergence of the $O(\sqrt{n}L)$-iteration homogeneous and self-dual linear programming algorithm (F. Wu, S. Wu, and Y. Ye), manuscript, Academia Sinica and the University of Iowa (1992).

A superlinearly convergent $O(\sqrt{n}L)$-iteration algorithm for linear programming (Y. Ye, R. Tapia and Y. Zhang), TR91-22, Department of Mathematical Sciences, Rice University (1991).

A build-up interior-point method for linear programming: affine scaling form (G. Dantzig and Y. Ye), Department of Management Science, University of Iowa (1991).

An $O(\sqrt{n}L)$-Iteration Combined Phase I-Phase II Potential Reduction Algorithm for Linear Programming unpublished manuscript, College of Business Administration, The University of Iowa (1990).

Line search in potential reduction algorithms for linear programming, Working Paper, College of Business Administration, The University of Iowa (1989).

Further development of the interior algorithm for convex quadratic programming, unpublished manuscript, Stanford University and Integrated Systems Inc., Stanford, CA (1987).

Top of Publications / Ye's Homepage