Yinyu Ye

16 Stowe Lane, Menlo Park, CA 94025, USA

Home (650) 233-8988 and Office (650) 723-7262

http://www.stanford.edu/~yyye

Email: yinyu-ye@stanford.edu

 

 

 

 

1. Education

 

1988: Ph.D. major in Engineering-Economic Systems and minor in Operations Research. Thesis Title ``Interior Algorithms for Linear, Quadratic and Linearly Constrained Convex Programming,'' Stanford University, Stanford, California.  Thesis Advisor Committee (in alphabetic order): Sam Chiu, George Dantzig, David Luenberger, Edison Tse.

1987: Visiting Ph.D. Student, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York. 

1983: M.S. in Engineering-Economic Systems, Stanford  University. 

1982: B.S. in Systems and Control, Huazhong University of  Science and Technology (HUST), Wuhan, The People's Republic of China. 

     

2. Professional Experience

 

04/02---: Professor and Director of the Industrial Affiliates Program of Management Science and Engineering and, by courtesy, Electrical Engineering, Stanford University, Stanford, CA, USA---Mathematical  Programming, Algorithm Design and Analysis, Network and Information  System Applications.

04/06-07/06: Visiting Chair Professor, Tsinghua University, China.

01/98---04/02: Henry B. Tippie Research Professor, Department of Management Sciences and Applied

Mathematical and Computational Sciences, The University of Iowa, Iowa City, Iowa, USA.

12/00---05/01: Visiting Professor, Department of Systems Engineering and Engineering Management, Chinese University of Hong Kong, Hong Kong.

09/98---11/98: Visiting Fellow, Mathematical Science Research Institute, UC Berkeley, California.

09/93---1/98: Professor, Department of Management Sciences, The University of Iowa, Iowa City, Iowa. 

08/93---12/93: Visiting Scientist, Department of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY.

06/93---present: Adjunct Professor, Institute of Applied  Mathematics, the Chinese Academy, Beijing , China.

06/93---present: Adjunct Professor, Department of Mathematics, Fudan University, Shanghai and Huazhong University of Science and Technology, Wuhan, China.

09/90---8/93: Associate Professor, Department of Management Sciences, The University of Iowa, Iowa City, Iowa. 

07/91---8/91: Visiting Scientist, Department of Mathematical and Computational Sciences, Rice University, Houston, TX.

09/88---08/90: Assistant Professor, Department of Management Sciences, The University of Iowa, Iowa City, Iowa. 

11/87---08/88: Research Scientist, Optimization Software Development, Integrated Systems Inc., Santa Clara, California. 

09/86---06/87: Lecturer, Mathematical Programming and Systems  Optimization, Department of Engineering-Economic Systems, Stanford University.

06/83---06/86: Research Assistant, Mathematical Programming, Decision Systems and Network Planning, Department of Engineering-Economic Systems, Stanford University. 

         

3. Publications (singly authored if no author names shown)

 

3.1 Refereed Journal Papers

 

[J112] “Further Relaxations of the SDP Approach to Sensor Network Localization,” (Wang, Song, Boyd and Ye), Working Paper, Management Science and Engineering, Stanford University (September, 2006); to appear in SIAM J. Optimization.

 

[J111] “A Distributed SDP approach for Large-scale Noisy Anchor-free Graph Realization with Applications to Molecular Conformation,” (Biswas, Toh and Ye), posted March 29/05), to appear SIAM Journal on Scientific Computing.

 

[J110] “Finding Equitable Convex Partitions of Points in a Polygon Efficiently,” (Carlsson, Armbruster and Ye), November, 2006, to appear in the ACM Transactions on Algorithms.

 

[J109] “Exchange Market Equilibria with Leontief's Utility: Freedom of Pricing Leads to Rationality,” Theoretical Computer Science, Volume 378, Issue 2, 6 June 2007, Pages 134-142.

 

[J108] ``SPASELOC: AN ADAPTIVE SUBPROBLEM ALGORITHM FOR

SCALABLE WIRELESS SENSOR NETWORK LOCALIZATION,’’ (MICHAEL CARTER, HOLLY JIN, MICHAEL SAUNDERS, and YINYU YE), appeared in SIAM J Optimization Online  (2006).

 

[J107] ``Approximation Algorithms for Metric Facility Location Problems,’’ (M. Mahdian, Y. Ye and J. Zhang), SIAM J Computing 36:2 (2006)  411-432.

 

[J106] “Semidefinite Programming Based Algorithms for Sensor Network Localization,” (Pratik Biswas, Tzu-Chen Liang, Ta-Chung Wang and Yinyu Ye), ACM J on Transactions on Sensor Networks 2:2  (2006) 188-220.

 

[J105] “Semidefinite Programming Approaches for Sensor Network Localization with Noisy Distance Measurements,” (Pratik Biswas, Tzu-Chen Liang, Kim-Chuan Toh, Ta-Chung Wang and Yinyu Ye), IEEE Transactions on Automation Science and Engineering, 3:4  (2006) 360-371.

 

[J104] ``An Improved Algorithm for Approximating the Radii of Point Sets,’’ (Kasturi Varadarajan, S. Venkatesh, Yinyu Ye and Jiawei Zhang),  SIAM J Computing  36:6 (2007) 1764--1776.

 

[J103] “On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming,” (So, Zhang and Ye), 2004; appeared in Math. Programming Online (2006).

 

 [J102] “Lot-sizing scheduling with batch setup times,” (B. Chen, Y. Ye and J. Zhang), Journal of Scheduling, 9:3 (2006) 299 - 310.

 

[J101] “A Path to the Arrow-Debreu Competitive Matket Equilibrium,” 2004, appeared in Math Programming Online (2006).

 

[J100] ``On Solving Fewnomials Over Intervals in Fewnomial Time,’’ (Maurice Rojas and Y. Ye), Journal of Complexity, Volume 21, Issue 1 (Foundations of Computational Mathematics Conference 2002 special issue, 2005) 87-110.

 

[J99] “A new complexity result on solving the Markov decision problem,” Math of OR, 30:3 (2005) 733-749.

 

[J98] “Improved complexity results on solving real-number linear feasibility problems,” 2002, Math Programming, 106:2 (2006) 339-363.

 

[J97] “Theory of Semidefinite Programming for Sensor Network Localization,” (Anthony So and Ye), Mathematical Programming, Series B, 109:367-384, 2007.

[J96] “A Multi-Exchange Local Search Algorithm for the Capacitated Facility Location Problem,” (Zhang, Chen and Ye), Math of OR, 30:2 (2005) 389-403.

 

[J95] ``Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem,’’ (Ageev, Ye and Zhang), SIAM J Discrete Math. 18:1 (2004) 207-217.

 

[J94] ``New results on quadratic minimization,’’ (S. Zhang and Y. Ye), SIAM J. Optimization, 14:1  (2003) 245-267.

 

[J93] “Approximate the 2-Catalog Segmentation Problem Using Semidefinite Programming Relaxations,” (C. Xu, Y. Ye and J. Zhang), Optimization Methods and Software, 18:6 (2003) 705 – 719.

 

[J92] “On some interior-point algorithms for nonconvex quadratic optimization”, (P. Tseng and Y. Ye),

Mathematical Programming, 93 (2003) 217-225.

 

[J91] ``Approximation of dense-n/2-subgraph and the complement of min-bisection,'' (Y. Ye and J. Zhang), JOURNAL OF GLOBAL OPTIMIZATION; JAN 2003; v.25, no.1, p.55-73

 

[J90] “A Note on the Maximization Version of Multi-level Facility Location Problems”, (J. Zhang and Y. Ye),

Operations Research Letters, 30:5 (2002) 333-335.

 

[J89] ``Optimization with a few violated constraints,'' (E.W. Bai, Y. Cho, R. Tempo and Y. Ye), IEEE Trans. on AC 47:7  (2002) 1067-1077.

 

[J88] ``An Approximation Algorithm for Scheduling Two-Parallel Machines with Capacity Constraints,'' (H. Yang, Y. Ye and J. Zhang), Discrete and Applied Mathematics, 130:3 (2003) 449-467.

 

[J87] ``Improved Approximation for Max Set Splitting and Max NAE SAT,'' (J. Zhang, Y. Ye, and Q. Han),

Discrete and Applied Mathematics, 142:1-3 (2004) 133-149.

 

[J86] ``On approximation of Max-Vertex-Cover,''  (Q. Han, Y. Ye, H. Zhang and J. Zhang), European Journal of Operations Research. 143:2 (2002) 342-355.

 

[J85] ``Blind channel equalization using e-approximation algorithms'', (Q. Li, E.W. Bai and Y. Ye),

IEEE Trans. on Signal Processing 49:11 (2001) 2823-2831.

 

 [J84] ``An improved rounding method and semidefinite relaxation for graph partition,'' (Q. Han, Y. Ye, and J. Zhang),

Mathematical Programming 92:3 (2002) 509-535.

 

[J83] ``A .699 approximation algorithm for Max-Bisection,'' Mathematical Programming 90:1 (2001) 101-111.

 

[J82] ``Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems,'' (M. Todd, L. Tuncel, Y. Ye), Mathematical Programming 90:1 (2001) 59-70.

 

[J81] ``Convergence results of analytic center estimator,'' (E. Bai, M. Fu, R. Tempo, and Y. Ye), IEEE Transactions on Automatic Control 45:3 (2000) 569-572.

 

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

 

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

 

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

 

[J77] ``Mixed linear and semidefinite programming for combinatorial and quadratic optimization,'' (S. Benson, Y. Ye, and X. Zhang), Optimization Methods and Software 11&12 (1999) 515-544.

 

[J76] ``Approximating global quadratic optimization with convex quadratic constraints,'' Journal of Global Optimization 15 (1999) 1-17.

 

[J75] ``Approximating quadratic programming with bound and quadratic constraints,'' Mathematical Programming 84 (1999) 219-226.

 

[J74] ``On homotopy-smoothing methods for box constrained variational inequalities,'' (X. Chen and Y. Ye), SIAM J. Control & Optimization 37 (1999) 589-616.

 

[J73] ``On the quadratic convergence of the O(n.5L)-iteration homogeneous and self-dual linear programming algorithm,'' (F. Wu, S. Wu, and Y. Ye), Annals of Operations Research 87 (1999) 393-406.

 

[J72] ``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.

 

[J71] ``Probabilistic analysis of an infeasible interior-point algorithm for linear programming,'' (K. Anstreicher, J. Ji, F. Potra and Y. Ye), Mathematics of Operations Research 24 (1999) 176-192.

 

[J70] ``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.

 

[J69] ``Constrained logarithmic least squares in parameter estimation,'' (E. Bai and Y. Ye), IEEE Transactions on Automatic Control 44:1 (1999) 182-185.

 

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

 

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

 

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

 

[J65] ``Bounded error parameter estimation: a sequential analytic center approach,'' (E. Bai, Y. Ye and R. Tempo),

Transactions on Automatic Control 44:6 (1999) 1107-1117.

 

[J64] ``How partial knowledge helps to solve linear programs,'' Journal of Complexity 12 (1996) 480-491.

 

[J63] ``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.

 

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

 

[J61] ``Complexity analysis of the analytic center cutting plane method that uses multiple cuts,'' Mathematical Programming 78 (1997) 85-104.

 

[J60] ``On the relationship between layered least squares and affine scaling steps,'' (S. Vavasis and Y. Ye), The Mathematics of Numerical Analysis, Lectures in Applied Mathematics 32 (1996) 857-866.

 

[J59] ``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.

 

[J58] ``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.

 

[J57] ``On homogeneous and self-dual algorithm for LCP,'' Mathematical Programming 76 (1997) 211-222.

 

[J56] ``Combining interior-point and pivoting algorithms for linear programming,'' (E. D. Andersen and Y. Ye),

Management Science 42 (1996) 1719-1731.

 

[J55] ``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.

 

[J54] ``Interior-point methods for nonlinear complementarity problem,'' (F. Potra and Y. Ye), Journal of Optimization Theory and Application 88 (1996) 617-642.

 

[J53] ``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.

 

[J52] ``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.

 

[J51] ``A asymptotical O(n..5L)-iteration path-following linear programming algorithm that uses long steps,'' (P. Hung and Y. Ye), SIAM J. Optimization 6 (1996) 570-586.

 

[J50] ``A generalized homogeneous and self-dual linear programming algorithm,'' (X. Xu and Y. Ye), Operations Research Letters 17:2 (1995) 181-190.

 

[J49] ``A simplification of the 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.

 

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

 

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

 

[J46] ``On the von Neumann economic growth problem,'' Mathematics of Operations Research 20 (1995) 617-633.

 

[J45] ``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.

 

[J44] ``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.

 

[J43] ``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.

 

[J42] ``An O(n..5L)-iteration homogeneous and self-dual linear programming algorithm,'' (Y. Ye, M. Todd and S. Mizuno), Mathematics of Operations Research 19 (1994) 53-67.

 

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

 

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

 

[J39] ``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.

 

[J38] ``On quadratic and O(n.5L) convergence of a predictor-corrector algorithm for LCP,''  (Y. Ye and K. Anstreicher), Mathematical Programming 62 (1993) 537-552.

 

[J37] ``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.

 

 [J36] ``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.

 

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

 

[J34] ``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.

 

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

 

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

 

[J31] ``A quadratically convergent O(n.5L)-iteration algorithm for linear programming,'' (Y. Ye, O. Guler, R. Tapia and Y. Zhang), Mathematical Programming 59 (1993) 151-162.

 

[J30] ``Convergence behavior of some interior-point algorithms,'' (O. Guler and Y. Ye), Mathematical Programming 60 (1993) 215-228.

 

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

 

[J28] ``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.

 

[J27] ``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.

  

[J26] ``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.

 

[J25] ``Solutions of P0-matrix linear complementarity problems,'' (P. Pardalos, Y. Ye, C. Han and J. Kaliski), SIAM J. on Matrix Anal. Appl. 14 (Oct. 1993) 1048-1060.

 

[J24] ``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.

  

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

 

[J22] ``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.

 

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

 

[J20] ``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.

 

[J19] ``On affine scaling algorithms for nonconvex quadratic programming,'' Mathematical Programming 56 (1992) 285-300.

 

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

 

[J17] ``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.

 

 [J16] ``Interior-point algorithms for global optimization,'' Annals of Operations Research 25 (1990) 59-74. 

 

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

 

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

 

[J13] ``Containing and shrinking ellipsoids in the path-following algorithm,'' (Y. Ye and M. Todd), Mathematical 

Programming 47 (1990) 1-9.

 

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

 

[J11] ``An O(n3L) potential reduction algorithm for linear programming,'' Mathematical Programming 50 (1991) 239-258.

 

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

 

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

 

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

 

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

  

[J6] ``An extension of Karmarkar's projective algorithm for convex quadratic programming,'' (Y. Ye and E. Tse)

Mathematical Programming 44 (1989) 157-179. 

 

[J5] ``Eliminating columns in the simplex method for linear programming,'' Journal of Optimization Theory and  

Applications 63 (1989) 103-111. 

 

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

 

[J3] ``Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming,'' (Y. Ye and M.

Kojima), Mathematical Programming 39 (1987) 305-317.  

 

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

 

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

    

 

3.3 Book, Refereed Book Chapters/Conference Proceedings Papers

 

C[41] “On Analyzing Semidefinite Programming Relaxations of Complex Quadratic

Optimization Problems,” Anthony Man-Cho So, Yinyu Ye, and Jiawei Zhang, 8-1, Handbook of Approximation Algorithms and Metaheuristics, ed.  Teofilo F. Gonzalez, Chapman & Hall/CRC, 2007.

 

[C40] “Greedy Algorithms for Metric Facility Location Problems,” Anthony Man-Cho So, Yinyu Ye, and Jiawei Zhang, 39-1, Handbook of Approximation Algorithms and Metaheuristics, ed.  Teofilo F. Gonzalez, Chapman & Hall/CRC, 2007.

 

[C39] “Semidefinite Programming for Sensor Network and Graph Localization,” (Ye) In `Robust Optimization-Directed Design' (ed. A.J. Kurdila, P.M. Pardalos, M. Zabarankin), pp. 127-143, Springer, 2006.

 

[C38] “Pari-mutuel Markets: Mechanisms and Performance” (Peters, So and Ye), in WINE’07.

 

[C37] “A Note on Equilibrium Pricing as Convex Optimization” (Chen, Ye, Zhang), in WINE’07.

 

[C36] “Stochastic Combinatorial Optimization with Controllable Risk Aversion Level,”  (So, Zhang and Ye); Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2006), LNCS 4110, pp. 224-235, 2006.

 

[C35] “A Semidefinite Programming Approach to Tensegrity Theory and Realizability of Graphs” (So and Ye), Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 766-775, 2006.

 

[C34] “Leontief Economies Encode Nonzero Sum Two-Player Games” (Codenotti, Saberi, Varadarajan and Ye)

Posted May 20, 2005; research supported by NSF grant DMS-0306611, in SODA’06.

 

[C33] “On Solving Coverage Problems in a Wireless Sensor Network Using Voronoi Diagrams,” (Anthony So and Yinyu Ye), in WINE’05.

 

[C32] “On Exchange Market Equilibria with Leontief's Utility: Freedom of Pricing Leads to Rationality,” posted April 23, 2005; research supported by NSF grant DMS-0306611, in WINE’05.

 

[C31] “Integration of Angle of Arrival Information for Multimodal Sensor Network Localization using Semidefinite Programming,” (Pratik Biswas, Hamid Aghajan and Yinyu Ye),  in the 39th Asilomar Conference on Signals, Systems and Computers, 2005.

 

[C30] “On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations is available,” (So, Zhang and Ye), 2005, in IPCO 2005.

 

[C29] “Market Equilibria for Homothetic, Quasi-Concave Utilities and Economies of Scale in Production,” (Kamal Jain, Vijay V. Vazirani and Yinyu Ye), 2004, in SODA 2005.

 

[C28] “Theory of Semidefinite Programming for Sensor Network Localization,” (Anthony So and Ye), 2004, in SODA 2005.

[C27] ``Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization’’ (P. Biswas and Y.  Ye), in Proceedings of IPSN2004, Berkeley, 2004.

 

[C26] ``MILP Formulation and Polynomial Time Algorithm for an Aircraft Scheduling Problem,’’ (Alexandre M. Bayen, Claire J. Tomlin, Yinyu Ye, and Jiawei Zhang), Proceedings of The 42th IEEE Conference on Decision and Control (CDC) 2003.

 

[C25] ``An Improved Algorithm for Approximating the Radii of Point Sets,’’ (Yinyu Ye and Jiawei Zhang), Proceedings of The 6th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX) LNCS 2764, pp. 178-187,2003.

 

[C24] ``A 2-approximation algorithm for the soft-capacitated facility location problem,’’ (Mohammad Mahdian , Yinyu Ye and Jiawei Zhang), Proceedings of The 6th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), LNCS 2764, pp. 129-140, 2003.

 

[C23] ``Improved Combinatorial Apporixmation Algorithms for the k-Level Facility Location Problem,’’ (Alexander Ageev , Yinyu Ye and Jiawei Zhang), Proceedings of The 30th International Colloquium on Automata, Languages and Programming (ICALP) , LNCS 2719, pp. 145-156, 2003.

 

[C22] “Improved Approximation Algorithms for the Metric Facility Location Problem ,” (M. Mahdian, Y. Ye and J. Zhang),   in Klaus Jansen, Stefano Leonardi and Vijay V. Vazirani (Eds.): 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX 2002 (Rome, Italy, September 17-21, 2002) Proceedings (also Lecture Notes in Computer Science 2462 Springer) 229-242.

 

[C21] ``Semidefinite Programs,'' in A. Kent and J. Williams eds., Encyclopedia of Computer Science and Technology, 44:29 (Marcel Dekker, 2001) 247-361 .

 

[C20]``Semidefinite Programming Relaxations for Nonconvex Quadratic Optimization,’’ (Y. Nesterov, H. Wolkowics, and Y. Ye), in Handbook on Semidefinite Programming (Kluwer, Boston, 2000} 361-420.

 

[C19] ``Approximating Maximum Stable Set and Minimum Graph Coloring Problems

with the Positive Semidefinite Relaxation,'' (Steve Benson  and Y. Ye),  in M. Ferris and J. Pang eds., Applications and Algorithms of Complementarity (Kluwer Academic Publishers, 2000) 1-18.

 

[C18] ``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.

 

[C17] ``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

(Kluwer Academic Publication, 2000) pp. 233-243.

 

 [C16] ``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).

 

[C15] Interior-Point Algorithms: Theory and Analysis, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, monograph, 1997.

 

[C14] ``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.

 

 [C13] ``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.

 

 [C12] ``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).

 

[C11] ``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.

 

[C10] ``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.

 

[C9] ``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.

 

[C8] ``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).

 

[C7] ``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) pp 310-316.

 

[C6] ``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).

 

[C5] ``Interior-point algorithms for solving nonlinear optimization problems,'' (C. Han, P. Pardalos and Y. Ye), COAL Newsletter 19 (1991) 45-54.

 

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

 

[C3] “Interior point algorithms for quadratic programming problems” (P.M. Pardalos, Y. Ye ,and C.-G. Han), Proc. of the Conf. on Optimization Methods and their Applications (in Russian), Nauka, USSR (1990), pp. 194-213.

 

[C2] ``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) 92-112.

 

[C1] ``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. 

      

3.4 Working Papers

 

[W19] “Competitive Communication Spectrum Economy and Equilibrium,” (Ye), Working Paper, Management Science and Engineering, Stanford University (October, 2007).

 

 [W18] “The Fixed-Hub Single Allocation Problem: A Geometric Rounding Approach,” (Dongdong Ge, Ye and Zhang), Working Paper, Management Science and Engineering, Stanford University (March, 2007).


[W17] “A Unified Theorem on SDP Rank Reduction,” (So, Ye and Zhang), Working Paper, Management Science and Engineering, Stanford University (November, 2006).


[W16] “Newsvendor Optimization with Limited Distribution Information,” (Zhu, Zhang and Ye), Working Paper, Management Science and Engineering, Stanford University (November, 2006).

 

[W15] “Solving Min-Max Multi-Depot Vehicle Routing Problem ,” (Carlsson, Ge, Subramaniam, Wu and Ye), Working Paper, Management Science and Engineering, Stanford University (October, 2006).

 

[W14] “A Convex Parimutuel Formulation for Contingent Claim Markets,” (Peters, So and Ye), Working Paper, Management Science and Engineering, Stanford University (October, 2005).

 

 [W13] “A Gradient Search Method to Round the Semidefinite Programming Relaxation Solution for Ad Hoc Wireless Sensor Network Localization,” (Liang, Wang and Ye), posted August 24/04; Report updated 10/1/04 and Demo updated 10/10/04.

[W12] “A distributed method for solving semideinite programs arising from Ad Hoc Wireless Sensor Network Localization,” (Biswas and Ye), posted October/30/03.

[W11] ``An approximation algorithm for scheduling aircraft with holding time’’ (A.~M.~Bayen, C.~J.Tomlin, Y. Ye and Jiawei Zhang) Working Paper, Aeronautics and Astronautics, Stanford University (April, 2003).

 

[W10] ``On the Budgeted MAX-CUT problem and its Application to the Capacitated Two-Parallel Machine Scheduling,'' (J. Zhang and Y. Ye), Working Paper, Department of Management Sciences, The University of  Iowa (March, 2001).

 

 [W9] ``Solving sparse semidefinite programs using the dual scaling algorithm with an iterative solver,'' (C. Choi and Y. Ye), Working Paper, Department of Management Sciences, The University of Iowa (March, 2000).

 

 [W8] ``Computational Optimization Laboratory Positive Semidefinite Programming User Guide,'' (S. Benson, Y. Ye, and X. Zhang), Working Paper, Department of Management Sciences, The University of Iowa (February, 1999).

 

[W7] ``Convergence behavior of the central path for homogeneous and self-dual cones,'' Working Note, Department of Management Sciences, The University of Iowa (December, 1995).

 

[W6] ``A superlinearly convergent O(n.5L)-iteration algorithm for linear programming,'' (Y. Ye, R. Tapia and

Y. Zhang), TR91-22, Department of Mathematical Sciences, Rice University (1991).

 

[W5] ``A low complexity combined phase I-phase II potential reduction algorithm for linear programming,'' Working Paper No. 91-1, College of Business Administration, The University of Iowa (1991).

 

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

 

[W3] ``A `build-up' interior method for linear programming,'' (G. Dantzig and Y. Ye) SOL Report, Department of Operations Research, Stanford University (1990). 

 

[W2] ``Bimatrix equilibrium points and potential functions,''  Working Paper No. 88-16, College of Business Administration, The University of Iowa (1988). 

 

[W1] ``Further development of the interior algorithm for convex quadratic programming,'' manuscript, Stanford University and Integrated Systems Inc., Stanford, CA (1987).

   

4. Students, Courses, and other Professional Contributions

 

Ph.D. Students:

John Kaliski,         1992                                        Anlon Systems Inc., Mankato, Minnesota 

Ronald Bosch       1994   (joint)                          Harvard University, Bio-statistics, School of Public Health

Pi-Fang Huang     1995                                        Taiwan Dong-Hai University

Erling Andersen   1996   (visiting Ph.D.)          Founder of MOSEK.com,  Optimization Software

Tienbin  Qian        1997   (joint)                          Motorola at Arizona, Operations Management Team

Steve Benson       1999                                        Argonne National Lab at Chicago

Jiawei Zhang         2004                        NYU

Anthony So          2007                                        Stanford

Pratik Biswas        2007                                        Stanford

Mark Peters           present                                   Stanford

Dongdong Ge       present                                   Stanford

John Carlsson       present                                   Stanford

Zhishu Zhu           present                                   Stanford

 

Courses listed on http://www.stanford.edu/~yyye/course.html .

 

Computer Sostware/Programs listed on http://www.stanford.edu/~yyye/Col.html .

 

Over 100 invited presentations

 

Patent through Stanford Technology License:

* A SEMI-DEFINITE PROGRAMMING METHOD FOR AD HOC NETWORK NODE LOCALIZATION, 2005

* Convex Parimutuel Call Auction Mechanism (S05-349), 2006

    

5. Professional Affiliations

 

* The Institute For Operations Research and The Management Science

* Society for Industrial and Applied Mathematics.

* Mathematical Programming Society. 

 

  

6. Professional Activities

 

* Elected Vice Chair of the SIAM Activity Group on Optimization (SIAG/OPT), 2008. 

* Plenary speaker at the 19th International Symposium on Mathematical Programming, Rio de Janeiro, 2006.

* Area Editor of Operations Research (2005-), Chief Editor of Optimization & Engineering (2000-) and Pacific Journal of Optimization (2003-).

* Associate Editor of Management Science  (2004-), Mathematics of Operations Research (1998-2001), Optimization Methods and Software (2003-), SIAM Journal on Optimization (1990-1997), Journal of the Operations Research Society of Japan (1998-).

*Selected as a highly cited mathematical researcher on http://www.ISIhighlycited.com 2003

* Distinguished Speaker in High Performance Computation for Engineered Systems (HPCES), MIT, 2002.

* Semi-plenary speaker at the 17th International Symposium on Mathematical Programming, Atlanta, 2000.

 * Section Officer (Linear Programming) of the Institute for Operations Research and the Management Sciences, (1997-2000).

* Co-organizer of the 1999 DIMACS Princeton workshop on discrete optimization.

* Member of the International Advisory Committee for the 15th and 16th International Symposium on Mathematical Programming (1992-1997).

* Topic Coordinator for the 15th International Symposium on Mathematical Programming (1992-1994).

* NSF proposal review panelist (1994,1995,1996, 2000, 2002).

* Referee for Mathematics of Operations Research, Mathematical Programming, SIAM Journals, Operations Research, Linear Algebra and its Applications, and Journal of Optimization Theory and Applications, etc. 

* Reviewer for National Science Foundation, USA; Natural Sciences and Engineering Research Council of Canada, Research Grant Council of Australia, Research Grant Council of Hong Kong, Sciences and Engineering Research Council of Chili.

* The Iowa Business School Faculty Research Committee, 1996-.

* The Iowa Business School Promotion and Tenure Committee, 1995-1996.

* The University of Iowa Vice-President for Research Advisory Committee, 1994-1995.

* Director, the Management Science Computational Optimization Lab, 1994-.

* The University of Iowa Computing Service Committee, 1991-1993.

 

    

7. Present and Past Industrial and Consulting Activities

 

Consultant and research work for various industries, include Boeing (2004-), American Express, etc. (2006-), AT&T (1992-93), Polaris Wireless Inc (2006-), AtRoad, Inc. Fremont (2006-), Barcelona Design Inc,  (1998-2004), Huawei Technologies Co., Ltd. (China) (2005-), TISCO Inc. (China) (2006-), etc on supply chain, dynamic resource allocation, facility location, sensor network localization and routing, financial optimization, circuit design, collection games, project management, task scheduling, etc.

 

     

8. Awards and Funded Research

 

* The recipient of the 2007 Stanford Asian American Faculty of Year Award

* The first recipient of the Farkas Prize of the INFORMS Optimization Society (awarded bi-annually), 2006.

* Elected as an INFORMS Fellow November 6, 2006

* Principle Investigator (1 of 1), NSF Grant for Complexity of Market Equilibrium, 2006-2008.

* BASES Innovators' Challenge First-Place Winners, 2004: Pratik Biswas and Yinyu Ye on sensor network localization.
* BASES Innovators' Challenge First-Place Winners, 2005: Holy Jin, Mike Carter, Mike Saunders and Yinyu Ye on sensor network management.

* Principle Investigator (1 of 2), Game and dynamic decision making, American Express, 2005-2007.

* Principle Investigator (1 of 1), Dynamic Resource Allocation, Boeing Company, 2004-2007.

* Principle Investigator (1 of 1), Stochastic Optimization, Boeing Company, 2004-2007.

* Principle Investigator (1 of 1), NSF Grant for Markov Decision Problem and Linear Programming, 2003-2006.

* Principle Investigator (1 of 1), NSF Grant for Semidefinite Programming and Approximation Algorithms, 1999-2003.

* Principle Organizer (1 of 2), Semidefinite Programming and Large-Scale Discrete Optimization Workshop, DIMACS and Princeton University, 1999.

* Research Fellow, Mathematical Science Research Institute, UC Berkeley, 1998.

* Co-Principal Investigator (1 of 5), NSF Grant for Computational Infrastructure and Equipments, 1998-.  

* Co-Principal Investigator (1 of 4), NSF Grant for Hybrid Optimization for Protein Structure, 1998-1999.  

* Co-Principal Investigator (1 of 4), The University of Iowa Biosciences Initiative Pilot Grant, 1998.  

* Principal Investigator (1 of 1), NSF Grant for computational complexity, 1997-2000.   

* Australian Research Council, The University of New South Wales, 1997.

* The Japan Education Ministry, The Institute of Statistical Mathematics, 1996.

* Principal Investigator (1 of 1), NSF Grant for mathematical programming, 1995-1998.  

* Dutch Organization for Scientific Research (NWO), Delft University, 1994-1997.  

* Obermann Fellowship, 1994.

* The Cornell University Theory Center, 1993-1994.

* Principal Investigator (1 of 1), NSF Grant for linear programming interior-point algorithms, 1993-1995.  

* Award of K. C. WONG Education Foundation, Hong Kong, 1993.

* Principal Investigator (1 of 1), NSF Grant for linear programming, 1990-1992.  

* Principal Investigator (1 of 1), MCI Contract for real time restoration, 1991-1992.

* Principal Investigator (1 of 1), The College Summer Grants, College of Business of Administration, The University of Iowa, 1989-1997.

* Principal Investigator (1 of 2), The Center for Advanced Studies Interdisciplinary Research Grant, The University of Iowa, 1991-1992.

 

Updated January 19, 2008.