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).
Interior-point algorithms for solving nonlinear optimization
problems (C. Han, P. Pardalos and Y. Ye), COAL Newsletter, 19 (1991)
45-54.
Top of Publications
/ Ye's Homepage
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