Yinyu Ye
Professor of Management Science and Engineering
and, by courtesy, Electrical Engineering
Terman Engineering Center 316
Department of Management Science and Engineering
School of Engineering
Stanford University
Phone: 650 723-7262
Fax: 650 723-1614
The new working paper: Pari-mutuel Markets: Mechanisms and
Performance is available.
Click
PDF file . (Posted May 9, 2008; research supported by NSF DMS-0604513).
The new working paper: Geometric Rounding: A Dependent Rounding Scheme for Allocation Problems is available.
Click for a on-line copy.
(Posted April 18, 2008; research supported by Boeing).
The new working paper:
Parimutuel Betting on Permutations is available.
Click for a on-line copy. (Posted April 15, 2008; research supported by NSF DMS-0604513).
The new working paper:
An interior-point path-following
algorithm for computing a Leontief
economy equilibrium is available.
Click
PDF file . (Posted March 11, 2008; research supported by NSF DMS-0604513).
The new working paper:
A Unified Theorem on SDP Rank Reduction is available.
Click
PDF file . (Posted November 20, 2006; Revised March 11, 2008; research supported by NSF DMS-0604513; to appear in Math of OR).
The new working paper:
Distributionally Robust Optimization under Moment
Uncertainty with Application to Data-Driven Problems is available.
Click
PDF file . (Posted February 20, 2008; research supported by Boeing).
The new working paper:
A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium is available.
Click
PDF file . (Posted February 18, 2008; research supported by NSF DMS-0604513).
Try our new sensor network localization and tracking system
ESDP Matlab Tracking Code; see
Readme File. This code simultaneously localizes and tracks a mass of randomly moving sensors in 2D based on their local distance information.
(Posted November 17 and updated 25, 2007).
The new working paper:
Competitive Communication Spectrum Economy and Equilibrium is available.
Click
PDF file . (Posted October 22, 2007; research supported by NSF DMS-0604513).
The new working paper:
A Note on Equilibrium Pricing as Convex Optimization is available.
Click a
journal version . (Appeared in WINE'07; research supported by NSF DMS-0604513).
The new working paper:
The Fixed-Hub Single Allocation Problem: A Geometric Rounding Approach is available.
Click
PDF file . (Posted October 22, 2007; research supported by Boeing).
My talk at the C&O@40, Waterloo:
A Unified Theorem on SDP Rank Reduction
. (Posted June 23, 2007).
The new working paper:
Further Relaxations of the SDP Approach to Sensor Network Localization is available.
Click
PDF file; and click
Dual ESDP Matlab Code or
ESDP Matlab Code and
Readme File, also
ESDPD Matlab Code and
Dual ESDPD Matlab Code, compare them to full SDP relaxation and other approaches
Full SDP Matlab Code (all need to use Sedumi 1.05 in order to run the demo); also see data of
A sample problem of 500 sensors or
A sample problem of 1000 sensors (Posted September 8 and updated November 25, 2007).
My talk at the 2007 OR Colloquia:
Finding Equitable Convex Partitions of Points and Applications
. (Posted March 5, 2007).
The new working paper:
Finding Equitable Convex Partitions of Points in a Polygon Efficiently is available.
Click
PDF file and
Partition Picture of 2K points . (Posted November 22 and Updated April 7, 2007; research supported by NSF and the Boeing Company; to
appear in The ACM Transactions on Algorithms).
The working paper:
Newsvendor Optimization with Limited Distribution Information is available.
Click
PDF file . (Posted November 18, 2006; research sypported by the Boeing company).
The working paper:
Solving Min-Max Multi-Depot Vehicle Routing Problem is available.
Click
PDF file . (Posted October 25, 2006 and updated May 3, 2007; research sypported by the Boeing company).
My talk at the Plenary Memorial Session of George Dantzig of ISMP 2006, Rio de Janeiro:
Recent Applications of Linear Programming--in Memory of George Dantzig
. (Posted August 7, 2006).
My talk at the HPOPT 2006, Delft and MOPTA 2006, Waterloo:
A Semidefinite Programming Approach to Tensegrity Theory and Graph Realization
. (Posted August 11, 2006).
The working paper:
Stochastic Combinatorial Optimization with Controllable Risk Aversion Level is available.
Click
PDF file . (Posted April 28, 2006; research supported by the Boeing company); appeared APPROX 2006.
The revised working paper:
Approximation Algorithms for Metric Facility Location Problems
. Appeared in SIAM J. Comput., Volume 36, Number 2, p.411-432 (2006).
This is the journal version of "Improved approximation algorithms for metric facility location
problems" of Proceedings of 5th International Workshop on Approximation
Algorithms for Combinatorial Optimization APPROX 2002 and
"A 2-approximation algorithm for the soft-capacitated facility
location problem" of Proceedings of 6th International Workshop on Approximation
Algorithms for Combinatorial Optimization APPROX 2003; (Posted 12/10/02, and updated 1/19/06;
this author and Jiawei Zhang were supported in part by NSF grant DMI-0231600)
The working paper:
A Convex Parimutuel Formulation for Contingent Claim Markets is available.
Click
PDF file . (Posted October 18, 2005; research supported by NSF grants DMS-0306611 and DMS-0604513).
The working paper:
DSDP5: Software for Semidefinite Programming is available. Click
PDF file (Posted September 20, 2005). Also
view independent benchmarks of DSDP5 and other solvers on SDPLIB,
the DIMACS problem set , and some
large SDPs for an idea of its robustness, speed,
and efficiency.
The working paper:
A Semidefinite Programming Approach to Tensegrity Theory and Realizability of Graphs is available.
Click here for the PDF file .
(Posted July 6, 2005, Updated October 11); appeared in SODA'06.
The working paper:
Leontief Economies Encode Nonzero Sum Two-Player Games is available. Click here for the ECCC Report
(Posted May 20, 2005; research supported by NSF grants DMS-0306611 and DMS-0604513); or
the conference version ; appeared in SODA'06.
The working paper:
Exchange Market Equilibria with Leontief's Utility: Freedom of Pricing Leads to
Rationality
is published on-line. Click here for the link to the paper
(Posted April 23, 2005, revised August 5, 2006, to appear in Theoretical Computer Science;
research supported by NSF grants DMS-0306611 and DMS-0604513); also see
the conference version ; appeared in WINE'05.
The working paper:
On Solving Coverage Problems in a Wireless Sensor Network Using Voronoi Diagrams
is available. Click here for the PDF file
(Posted November 28, 2005; research supported by NSF grant DMS-0306611), appeared in WINE'05.
The working paper:
Integration of Angle of Arrival Information for Multimodal Sensor Network Localization using
Semidefinite Programming is available. Click
PDF file . (Posted July 27, 2005); appeared in the 39th Asilomar Conference on Signals, Systems and Computers, 2005.
The working paper: A Distributed SDP approach for Large-scale Noisy Anchor-free Graph
Realization with Applications to Molecular Conformation is available. Click here for the
SIAM on-line publication
(Posted March 29/05 and updated February 14 and October 24, 2007).
The revised working paper:
Market equilibria for homothetic, quasi-concave utilities and
economies of scale in production
is available. Click here for the PDF file .
(Posted 10/18/04 and updated 2/15/07; appeared in SODA 2005; research supported by NSF grant DMS-0306611.)
The working paper:
A Path to the Arrow-Debreu Competitive Market Equilibrium
is available. Click for the MP On-Line
Publication .
(Posted February/23/04, revised final version July 15, 2005; research supported by NSF grant DMS-0306611).
The working paper:
SpaseLoc: An Adaptive Subproblem Algorithm for Scalable Wireless Sensor Network Localization
is available.
Click for the SIAM On-Line
Publication .
The working paper:
Theory of Semidefinite Programming for Sensor Network Localization
is available. Click here for the MP On-Line
Publication . (Posted April/24/04 and updated 10/10/05; appeared in SODA 2005.)
The working paper: On Approximating Complex Quadratic
Optimization Problems via Semidefinite Programming Relaxations
is available. Click for the MP On-Line
Publication . (Posted 1/31/05; appeared in IPCO 2005; updated July 2005, research supported by NSF grant DMS-0306611).
The working paper:
Semidefinite Programming Based Algorithms for Sensor Network Localization
.(Posted 9/10/03 and updated 10/3/05; appeared in IPSN 2004), appeared in ACM J on Transactions on Sensor Networks 2:2 (2006) 188-220.
The working paper:
Semidefinite Programming Approaches for Sensor Network Localization with Noisy Distance Measurements.
(Posted November 9, 2005; research partially supported by IMS of NUS),
appeared in IEEE Transactions on Automation Science and Engineering 3:4 (2006) 360-371.
The working paper:
A New Complexity Result on Solving the Markov Decision Problem
is available. Click for the
Math of OR, 30:3 (2005) 733-749 . (Posted 10/4/02, revised 10/3/04, research supported by NSF grant DMS-0306611.)
The working paper:
Approximating the radii of point sets
is available. Click here for the Postscript file.
(combined journal paper Posted 5/4/05; Research supported in part by NSF grant DMS-0306611;
conference versions in FOCS'02 and APPROX'04; to appear in SIAM Journal on Computing.)
The working paper:
An approximation algorithm for scheduling aircraft with holding time
is available. Click here for the Postscript file.
(Posted 4/3/03, Research supported in part by NSF grant DMI-0231600, appeared in CDC2004.)
The working paper:
MILP formulation and polynomial time algorithm for aircraft scheduling problems
is available and to appear in CDC03. Click here for the Postscript file.
(Posted 3/20/03, Research supported in part by NSF grant DMI-0231600, appeared in CDC2003.)
The BOOK Interior-Point Algorithms: Theory and Analysis has been published. Click here for information and related software .
Education
Ph.D. Engineering Economic Systems and Operations Research , Stanford University
, 1988.
M.S. Engineering Economic Systems , Stanford University
, 1983.
B.S. Systems and Control,
Huazhong University of Science and Technology , Wuhan, China, 1982.
Research Interest
Mathematical Programming
Optimization Algorithm Design and Analysis
Computational Complexity
Operations Research and Its Applications
Click here for my NSF Reports
Here are Courses I am teaching
Photo collection of my Family
Yinyu Ye
Department of Management Science and Engineering
School of Engineering
Stanford University
Stanford, CA 94305
email: yinyu-ye@stanford.edu