Yinyu Ye
KwohTing Li Professor in the School of Engineering and Professor, by courtesy, of Electrical Engineering
Management Science and Engineering
Bio
Yinyu Ye is currently the KwohTing Li Professor in the School of Engineering at the Department of Management Science and Engineering and Institute of Computational and Mathematical Engineering and the Director of the MS&E Industrial Affiliates Program, Stanford University. He received the B.S. degree in System Engineering from the Huazhong University of Science and Technology, China, and the M.S. and Ph.D. degrees in EngineeringEconomic Systems and Operations Research from Stanford University. Ye's research interests lie in the areas of optimization, complexity theory, algorithm design and analysis, and applications of mathematical programming, operations research and system engineering. He is also interested in developing optimization software for various realworld applications. Current research topics include Liner Programming Algorithms, Markov Decision Processes, Computational Game/Market Equilibrium, Metric Distance Geometry, Dynamic Resource Allocation, and Stochastic and Robust Decision Making, etc. He is an INFORMS (The Institute for Operations Research and The Management Science) Fellow, and has received several research awards including the winner of the 2014 SIAG/Optimization Prize awarded every three years to the author(s) of the most outstanding paper, the inaugural 2012 ISMP Tseng Lectureship Prize for outstanding contribution to continuous optimization, the 2009 John von Neumann Theory Prize for fundamental sustained contributions to theory in Operations Research and the Management Sciences, the inaugural 2006 Farkas prize on Optimization, and the 2009 IBM Faculty Award. He has supervised numerous doctoral students at Stanford who received received the 2015 and 2013 Second Prize of INFORMS Nicholson Student Paper Competition, the 2013 INFORMS Computing Society Prize, the 2008 Nicholson Prize, and the 2006 and 2010 INFORMS Optimization Prizes for Young Researchers. Ye teaches courses on Optimization, Network and Integer Programming, Semidefinite Programming, etc. He has written extensively on InteriorPoint Methods, Approximation Algorithms, Conic Optimization, and their applications; and served as a consultant or technical board member to a variety of industries, including MOSEK.
Academic Appointments

Professor, Management Science and Engineering

Professor (By courtesy), Electrical Engineering
Honors & Awards

SIAM Optimization Prize, SIAM (2015)

Lectureship Prize (Inaugural Recipient), ISMP Tseng (2012)

John von Neumann Theory Prize (CoRecipient), INFORMS (2009)

Faculty of the Year Award, Stanford Asian American Society (2007)

Inaugural recipient of the Farkas Prize, INFORMS Optimization Society (2006)

Fellow, INFORMS (November 6, 2006)

Plenary speaker, International Symposium on Mathematical Programming, Berlin (2012)

Plenary speaker, Workshop on Internet and Network Economics (2008)

SemiPlenary speaker, 17th International Symposium on Mathematical Programming, Atlanta (2000)

Area Editor, Optimization & Engineering (2000)

Associate Editor, Mathematics of Operations Research (19982001)

Section Officer (Linear Programming), Institute for Operations Research and the Management Sciences (19972000)

Coorganizer, DIMACS Princeton workshop on discrete optimizatio (1999)
Professional Education

BS, Huazhong University of Science and Technology (HUST), China, Systems and Control (1982)

MS, Stanford University, Engineering Economic Systems (1983)

PhD, Stanford University, Engineering Economic Systems and Operations Research (1988)
201516 Courses
 Linear Programming
MS&E 310 (Aut)  Linear and Nonlinear Optimization
MS&E 211 (Aut) 
Independent Studies (7)
 Advanced Reading and Research
SCCM 499 (Win, Sum)  Directed Reading and Research
MS&E 408 (Aut, Win, Spr, Sum)  Master's Research
CME 291 (Aut, Win, Spr, Sum)  Ph.D. Qualifying Tutorial or Paper
MS&E 300 (Aut, Win, Spr, Sum)  Ph.D. Research
CME 400 (Aut, Win, Spr, Sum)  Problems in Aero/Astro
AA 290 (Win, Spr, Sum)  Undergraduate Directed Study
MS&E 101 (Aut, Win, Spr, Sum)
 Advanced Reading and Research

Prior Year Courses
201415 Courses
 Linear Programming
MS&E 310 (Win)  Linear and Conic Optimization with Applications
CME 336, MS&E 314 (Win)
201314 Courses
 Linear Programming
MS&E 310 (Aut)  Linear and Nonlinear Optimization
MS&E 211 (Aut)  Optimization
MS&E 311 (Win)
201213 Courses
 Linear Programming
MS&E 310 (Aut)  Linear and Conic Optimization with Applications
MS&E 314 (Win)  Linear and Nonlinear Optimization
MS&E 211 (Aut)
 Linear Programming
All Publications

A homogeneous interiorpoint algorithm for nonsymmetric convex conic optimization
MATHEMATICAL PROGRAMMING
2015; 150 (2): 391422
View details for DOI 10.1007/s1010701407731
View details for Web of Science ID 000351522700007

Simultaneous beam sampling and aperture shape optimization for SPORT.
Medical physics
2015; 42 (2): 10121022
Abstract
Station parameter optimized radiation therapy (SPORT) was recently proposed to fully utilize the technical capability of emerging digital linear accelerators, in which the station parameters of a delivery system, such as aperture shape and weight, couch position/angle, gantry/collimator angle, can be optimized simultaneously. SPORT promises to deliver remarkable radiation dose distributions in an efficient manner, yet there exists no optimization algorithm for its implementation. The purpose of this work is to develop an algorithm to simultaneously optimize the beam sampling and aperture shapes.The authors build a mathematical model with the fundamental station point parameters as the decision variables. To solve the resulting largescale optimization problem, the authors devise an effective algorithm by integrating three advanced optimization techniques: column generation, subgradient method, and pattern search. Column generation adds the most beneficial stations sequentially until the plan quality improvement saturates and provides a good starting point for the subsequent optimization. It also adds the new stations during the algorithm if beneficial. For each update resulted from column generation, the subgradient method improves the selected stations locally by reshaping the apertures and updating the beam angles toward a descent subgradient direction. The algorithm continues to improve the selected stations locally and globally by a pattern search algorithm to explore the part of search space not reachable by the subgradient method. By combining these three techniques together, all plausible combinations of station parameters are searched efficiently to yield the optimal solution.A SPORT optimization framework with seamlessly integration of three complementary algorithms, column generation, subgradient method, and pattern search, was established. The proposed technique was applied to two previously treated clinical cases: a head and neck and a prostate case. It significantly improved the target conformality and at the same time critical structure sparing compared with conventional intensity modulated radiation therapy (IMRT). In the head and neck case, for example, the average PTV coverage D99% for two PTVs, cord and brainstem max doses, and right parotid gland mean dose were improved, respectively, by about 7%, 37%, 12%, and 16%.The proposed method automatically determines the number of the stations required to generate a satisfactory plan and optimizes simultaneously the involved station parameters, leading to improved quality of the resultant treatment plans as compared with the conventional IMRT plans.
View details for DOI 10.1118/1.4906253
View details for PubMedID 25652514

Complexity analysis of interior point algorithms for nonLipschitz and nonconvex minimization
MATHEMATICAL PROGRAMMING
2015; 149 (12): 301327
View details for DOI 10.1007/s1010701407535
View details for Web of Science ID 000347830300011

The Value of Stochastic Modeling in TwoStage Stochastic Programs with Cost Uncertainty
OPERATIONS RESEARCH
2014; 62 (6): 13771393
View details for DOI 10.1287/opre.2014.1318
View details for Web of Science ID 000346153600012

A LevenbergMarquardt method with approximate projections
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
2014; 59 (12): 526
View details for DOI 10.1007/s1058901395734
View details for Web of Science ID 000341495800002

Space tensor conic programming
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
2014; 59 (12): 307319
View details for DOI 10.1007/s1058901395770
View details for Web of Science ID 000341495800016

Waterflood management using twostage optimization with streamline simulation
COMPUTATIONAL GEOSCIENCES
2014; 18 (34): 483504
View details for DOI 10.1007/s1059601494044
View details for Web of Science ID 000341492200015

A Dynamic NearOptimal Algorithm for Online Linear Programming
OPERATIONS RESEARCH
2014; 62 (4): 876890
View details for DOI 10.1287/opre.2014.1289
View details for Web of Science ID 000343248400011

Close the Gaps: A LearningWhileDoing Algorithm for SingleProduct Revenue Management Problems
OPERATIONS RESEARCH
2014; 62 (2): 318331
View details for DOI 10.1287/opre.2013.1245
View details for Web of Science ID 000335394200007

Complexity of unconstrained minimization
MATHEMATICAL PROGRAMMING
2014; 143 (12): 371383
View details for DOI 10.1007/s1010701206130
View details for Web of Science ID 000330038300014

Analytical Results and Efficient Algorithm for Optimal Portfolio Deleveraging with Market Impact
OPERATIONS RESEARCH
2014; 62 (1): 195206
View details for DOI 10.1287/opre.2013.1222
View details for Web of Science ID 000332013300013

A Dynamic Algorithm for Facilitated Charging of PlugIn Electric Vehicles
IEEE TRANSACTIONS ON SMART GRID
2013; 4 (4): 17721779
View details for DOI 10.1109/TSG.2012.2233768
View details for Web of Science ID 000328064100004

Newsvendor optimization with limited distribution information
OPTIMIZATION METHODS & SOFTWARE
2013; 28 (3): 640667
View details for DOI 10.1080/10556788.2013.768994
View details for Web of Science ID 000320093700016

On stress matrices of (d+1)lateration frameworks in general position
MATHEMATICAL PROGRAMMING
2013; 137 (12): 117
View details for DOI 10.1007/s1010701104800
View details for Web of Science ID 000313797100001

On affine motions and bar frameworks in general position
LINEAR ALGEBRA AND ITS APPLICATIONS
2013; 438 (1): 3136
View details for DOI 10.1016/j.laa.2012.08.031
View details for Web of Science ID 000312682900004

Beyond Convex Relaxation: A PolynomialTime NonConvex Optimization Approach to Network Localization
2013 PROCEEDINGS IEEE INFOCOM
2013: 24992507
View details for Web of Science ID 000326335202070

THE CUBIC SPHERICAL OPTIMIZATION PROBLEMS
MATHEMATICS OF COMPUTATION
2012; 81 (279): 15131525
View details for Web of Science ID 000305099000011

A FPTAS for computing a symmetric Leontief competitive economy equilibrium
MATHEMATICAL PROGRAMMING
2012; 131 (12): 113129
View details for DOI 10.1007/s1010701003488
View details for Web of Science ID 000299180900006

A variational principle for computing nonequilibrium fluxes and potentials in genomescale biochemical networks
JOURNAL OF THEORETICAL BIOLOGY
2012; 292: 7177
Abstract
We derive a convex optimization problem on a steadystate nonequilibrium network of biochemical reactions, with the property that energy conservation and the second law of thermodynamics both hold at the problem solution. This suggests a new variational principle for biochemical networks that can be implemented in a computationally tractable manner. We derive the Lagrange dual of the optimization problem and use strong duality to demonstrate that a biochemical analogue of Tellegen's theorem holds at optimality. Each optimal flux is dependent on a free parameter that we relate to an elementary kinetic parameter when mass action kinetics is assumed.
View details for DOI 10.1016/j.jtbi.2011.09.029
View details for Web of Science ID 000297450100008
View details for PubMedID 21983269

Price of Correlations in Stochastic Optimization
OPERATIONS RESEARCH
2012; 60 (1): 150162
View details for DOI 10.1287/opre.1110.1011
View details for Web of Science ID 000302113900013

Geometric rounding: a dependent randomized rounding scheme
JOURNAL OF COMBINATORIAL OPTIMIZATION
2011; 22 (4): 699725
View details for DOI 10.1007/s108780109320z
View details for Web of Science ID 000296520200017

The Simplex and PolicyIteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
MATHEMATICS OF OPERATIONS RESEARCH
2011; 36 (4): 593603
View details for DOI 10.1287/moor.1110.0516
View details for Web of Science ID 000296977700001

An interiorpoint pathfollowing algorithm for computing a Leontief economy equilibrium
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
2011; 50 (2): 223236
View details for DOI 10.1007/s1058901093328
View details for Web of Science ID 000295574600003

A note on the complexity of Lp minimization
MATHEMATICAL PROGRAMMING
2011; 129 (2): 285299
View details for DOI 10.1007/s1010701104702
View details for Web of Science ID 000295785000006

An Optimization Approach to Improving Collections of Shape Maps
COMPUTER GRAPHICS FORUM
2011; 30 (5): 14811491
View details for DOI 10.1111/j.14678659.2011.02022.x
View details for Web of Science ID 000293524100012

A Unified Framework for Dynamic Prediction Market Design
OPERATIONS RESEARCH
2011; 59 (3): 550568
View details for DOI 10.1287/opre.1110.0922
View details for Web of Science ID 000292639000003

Statistical ranking and combinatorial Hodge theory
MATHEMATICAL PROGRAMMING
2011; 127 (1): 203244
View details for DOI 10.1007/s101070100419x
View details for Web of Science ID 000288371400009

Computing an Integer Point in a Class of Polytopes
OPERATIONS RESEARCH AND ITS APPLICATIONS: IN ENGINEERING, TECHNOLOGY AND MANAGEMENT
2011; 14: 258263
View details for Web of Science ID 000306631500031

ON EQUILIBRIUM PRICING AS CONVEX OPTIMIZATION
JOURNAL OF COMPUTATIONAL MATHEMATICS
2010; 28 (5): 569578
View details for DOI 10.4208/jcm.1003m0001
View details for Web of Science ID 000281879100001

Semidefinite Relaxation of Quadratic Optimization Problems
IEEE SIGNAL PROCESSING MAGAZINE
2010; 27 (3): 2034
View details for DOI 10.1109/MSP.2010.936019
View details for Web of Science ID 000276819100006

Special Issue in Memory of Alexander Rubinov
PACIFIC JOURNAL OF OPTIMIZATION
2010; 6 (2)
View details for Web of Science ID 000278611300001

Distributionally Robust Optimization Under Moment Uncertainty with Application to DataDriven Problems
OPERATIONS RESEARCH
2010; 58 (3): 595612
View details for DOI 10.1287/opre.1090.0741
View details for Web of Science ID 000278912100006

Dynamic Spectrum Management With the Competitive Market Model
IEEE TRANSACTIONS ON SIGNAL PROCESSING
2010; 58 (4): 24422446
View details for DOI 10.1109/TSP.2009.2039820
View details for Web of Science ID 000275370800048

A novel fluence map optimization model incorporating leaf sequencing constraints
PHYSICS IN MEDICINE AND BIOLOGY
2010; 55 (4): 12431264
Abstract
A novel fluence map optimization model incorporating leaf sequencing constraints is proposed to overcome the drawbacks of the current objective inside smoothing models. Instead of adding a smoothing item to the objective function, we add the total number of monitor unit (TNMU) requirement directly to the constraints which serves as an important factor to balance the fluence map optimization and leaf sequencing optimization process at the same time. Consequently, we formulate the fluence map optimization models for the trailing (left) leaf synchronized, leading (right) leaf synchronized and the interleaf motion constrained nonsynchronized leaf sweeping schemes, respectively. In those schemes, the leaves are all swept unidirectionally from left to right. Each of those models is turned into a linear constrained quadratic programming model which can be solved effectively by the interior point method. Those new models are evaluated with two publicly available clinical treatment datasets including a headneck case and a prostate case. As shown by the empirical results, our models perform much better in comparison with two recently emerged smoothing models (the total variance smoothing model and the quadratic smoothing model). For all three leaf sweeping schemes, our objective dose deviation functions increase much slower than those in the above two smoothing models with respect to the decreasing of the TNMU. While keeping plans in the similar conformity level, our new models gain much better performance on reducing TNMU.
View details for DOI 10.1088/00319155/55/4/023
View details for Web of Science ID 000274206800023
View details for PubMedID 20124655

UNIVERSAL RIGIDITY AND EDGE SPARSIFICATION FOR SENSOR NETWORK LOCALIZATION
SIAM JOURNAL ON OPTIMIZATION
2010; 20 (6): 30593081
View details for DOI 10.1137/090772009
View details for Web of Science ID 000285547100015

The Complexity of Determining the Uniqueness of Tarski's Fixed Point under the Lexicographic Ordering
INTERNET AND NETWORK ECONOMICS
2010; 6484: 455461
View details for Web of Science ID 000290644400038

LOWER BOUND THEORY OF NONZERO ENTRIES IN SOLUTIONS OF l(2)l(p) MINIMIZATION
SIAM JOURNAL ON SCIENTIFIC COMPUTING
2010; 32 (5): 28322852
View details for DOI 10.1137/090761471
View details for Web of Science ID 000283293500030

Universal Rigidity: Towards Accurate and Efficient Localization of Wireless Networks
2010 PROCEEDINGS IEEE INFOCOM
2010
View details for Web of Science ID 000287416300158

Correlation Robust Stochastic Optimization
PROCEEDINGS OF THE TWENTYFIRST ANNUAL ACMSIAM SYMPOSIUM ON DISCRETE ALGORITHMS
2010; 135: 10871096
View details for Web of Science ID 000280699900088

Finding Equitable Convex Partitions of Points in a Polygon Efficiently
ACM TRANSACTIONS ON ALGORITHMS
2010; 6 (4)
View details for DOI 10.1145/1824777.1824792
View details for Web of Science ID 000284382400016

Stochastic Combinatorial Optimization with Controllable Risk Aversion Level
MATHEMATICS OF OPERATIONS RESEARCH
2009; 34 (3): 522537
View details for DOI 10.1287/moor.1090.0390
View details for Web of Science ID 000269484000002

Conceptual formulation on fourdimensional inverse planning for intensity modulated radiation therapy
PHYSICS IN MEDICINE AND BIOLOGY
2009; 54 (13): N255N266
Abstract
Fourdimensional computed tomography (4DCT) offers an extra dimension of 'time' on the threedimensional patient model with which we can incorporate target motion in radiation treatment (RT) planning and delivery in various ways such as in the concept of internal target volume, in gated treatment or in target tracking. However, for all these methodologies, different phases are essentially considered as noninterconnected independent phases for the purpose of optimization, in other words, the 'time' dimension has yet to be incorporated explicitly in the optimization algorithm and fully exploited. In this note, we have formulated a new 4D inverse planning technique that treats all the phases in the 4DCT as one single entity in the optimization. The optimization is formulated as a quadratic problem for disciplined convex programming that enables the problem to be analyzed and solved efficiently. In the proofofprinciple examples illustrated, we show that the temporal information of the spatial relation of the target and organs at risk could be 'exchanged' amongst different phases so that an appropriate weighting of dose deposition could be allocated to each phase, thus enabling a treatment with a tight target margin and a full duty cycle otherwise not achievable by either of the aforementioned methodologies. Yet there are practical issues to be solved in the 4D RT planning and delivery. The 4D concept in the optimization we have formulated here does provide insight on how the 'time' dimension can be exploited in the 4D optimization process.
View details for DOI 10.1088/00319155/54/13/N01
View details for Web of Science ID 000267137200025
View details for PubMedID 19521008

An edgereduction algorithm for the vertex cover problem
OPERATIONS RESEARCH LETTERS
2009; 37 (3): 181186
View details for DOI 10.1016/j.orl.2009.01.010
View details for Web of Science ID 000266360900009

Solving MinMax MultiDepot Vehicle Routing Problem
LECTURES ON GLOBAL OPTIMIZATION
2009; 55: 3146
View details for Web of Science ID 000270995500003

A Unified Framework for Dynamic PariMutuel Information Market Design
10TH ACM CONFERENCE ON ELECTRONIC COMMERCE  EC 2009
2009: 255264
View details for Web of Science ID 000294744400030

BIQUADRATIC OPTIMIZATION OVER UNIT SPHERES AND SEMIDEFINITE PROGRAMMING RELAXATIONS
SIAM JOURNAL ON OPTIMIZATION
2009; 20 (3): 12861310
View details for DOI 10.1137/080729104
View details for Web of Science ID 000277836500009

Budget Allocation in a Competitive Communication Spectrum Economy
EURASIP JOURNAL ON ADVANCES IN SIGNAL PROCESSING
2009
View details for DOI 10.1155/2009/963717
View details for Web of Science ID 000266315900001

Using totalvariation regularization for intensity modulated radiation therapy inverse planning with fieldspecific numbers of segments
PHYSICS IN MEDICINE AND BIOLOGY
2008; 53 (23): 66536672
Abstract
Currently, there are two types of treatment planning algorithms for intensity modulated radiation therapy (IMRT). The beamletbased algorithm generates beamlet intensity maps with high complexity, resulting in large numbers of segments in the delivery after a leafsequencing algorithm is applied. The segmentbased direct aperture optimization (DAO) algorithm includes the physical constraints of the deliverable apertures in the calculation, and achieves a conformal dose distribution using a small number of segments. However, the number of segments is prefixed in most of the DAO approaches, and the typical random search scheme in the optimization is computationally intensive. A regularizationbased algorithm is proposed to overcome the drawbacks of the DAO method. Instead of smoothing the beamlet intensity maps as in many existing methods, we include a totalvariation term in the optimization objective function to reduce the number of signal levels of the beam intensity maps. An aperture rectification algorithm is then applied to generate a significantly reduced number of deliverable apertures. As compared to the DAO algorithm, our method has an efficient form of quadratic optimization, with an additional advantage of optimizing fieldspecific numbers of segments based on the modulation complexity. The proposed approach is evaluated using two clinical cases. Under the condition that the clinical acceptance criteria of the treatment plan are satisfied, for the prostate patient, the total number of segments for five fields is reduced from 61 using the Eclipse planning system to 35 using the proposed algorithm; for the head and neck patient, the total number of segments for seven fields is reduced from 107 to 28. The head and neck result is also compared to that using an equal number of four segments for each field. The comparison shows that using fieldspecific numbers of segments achieves a much improved dose distribution.
View details for DOI 10.1088/00319155/53/23/002
View details for Web of Science ID 000260859000002
View details for PubMedID 18997262

The complexity of equilibria: Hardness results for economies via a correspondence with games
ELSEVIER SCIENCE BV. 2008: 188198
View details for DOI 10.1016/j.tcs.2008.08.007
View details for Web of Science ID 000261416700010

A Unified Theorem on SDP Rank Reduction
MATHEMATICS OF OPERATIONS RESEARCH
2008; 33 (4): 910920
View details for DOI 10.1287/moor.1080.0326
View details for Web of Science ID 000261150000009

Preface
ALGORITHMICA
2008; 52 (1): 12
View details for DOI 10.1007/s0045300790011
View details for Web of Science ID 000258107400001

FURTHER RELAXATIONS OF THE SEMIDEFINITE PROGRAMMING APPROACH TO SENSOR NETWORK LOCALIZATION
SIAM JOURNAL ON OPTIMIZATION
2008; 19 (2): 655673
View details for DOI 10.1137/060669395
View details for Web of Science ID 000260849600008

Parimutuel Betting on Permutations
INTERNET AND NETWORK ECONOMICS, PROCEEDINGS
2008; 5385: 126137
View details for Web of Science ID 000262046200012

A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium
INTERNET AND NETWORK ECONOMICS, PROCEEDINGS
2008; 5385: 3140
View details for Web of Science ID 000262046200003

A distributed SDP approach for largescale noisy anchorfree graph realization with applications to molecular conformation
SIAM JOURNAL ON SCIENTIFIC COMPUTING
2008; 30 (3): 12511277
View details for DOI 10.1137/05062754X
View details for Web of Science ID 000255500500007

Algorithm 875: DSDP5  Software for semidefinite programming
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE
2008; 34 (3)
View details for DOI 10.1145/1356052.1356057
View details for Web of Science ID 000256338400005

Fast aperturebased inverse treatment planning using mixed integer and quadratic optimization
ELSEVIER SCIENCE INC. 2008: S675S675
View details for Web of Science ID 000258805302411

A path to the ArrowDebreu competitive market equilibrium
SPRINGER. 2008: 315348
View details for DOI 10.1007/s1010700600655
View details for Web of Science ID 000247429500014

Exchange market equilibria with Leontief's utility: Freedom of pricing leads to rationality
ELSEVIER SCIENCE BV. 2007: 134142
View details for DOI 10.1016/j.tcs.2007.02.016
View details for Web of Science ID 000247663400002

On approximating complex quadratic optimization problems via semidefinite programming relaxations
SPRINGER. 2007: 93110
View details for DOI 10.1007/s1010700600646
View details for Web of Science ID 000244889700006

A ubiquitin ligase transfers preformed polyubiquitin chains from a conjugating enzyme to a substrate
NATURE
2007; 446 (7133): 333337
Abstract
In eukaryotic cells, many shortlived proteins are conjugated with Lys 48linked ubiquitin chains and degraded by the proteasome. Ubiquitination requires an activating enzyme (E1), a conjugating enzyme (E2) and a ligase (E3). Most ubiquitin ligases use either a HECT (homologous to E6associated protein C terminus) or a RING (really interesting new gene) domain to catalyse polyubiquitination, but the mechanism of E3 catalysis is poorly defined. Here we dissect this process using mouse Ube2g2 (E2; identical at the amino acid level to human Ube2g2) and human gp78 (E3), an endoplasmic reticulum (ER)associated conjugating system essential for the degradation of misfolded ER proteins. We demonstrate by expressing recombinant proteins in Escherichia coli that Ube2g2/gp78mediated polyubiquitination involves preassembly of Lys 48linked ubiquitin chains at the catalytic cysteine of Ube2g2. The growth of Ube2g2anchored ubiquitin chains seems to be mediated by an aminolysisbased transfer reaction between two Ube2g2 molecules that each carries a ubiquitin moiety in its active site. Intriguingly, polyubiquitination of a substrate can be achieved by transferring preassembled ubiquitin chains from Ube2g2 to a lysine residue in a substrate.
View details for DOI 10.1038/nature05542
View details for Web of Science ID 000244892900049
View details for PubMedID 17310145

Theory of semidefinite programming for sensor network localization
SPRINGER. 2007: 367384
View details for DOI 10.1007/s1010700600401
View details for Web of Science ID 000243908500008

Parimutuel markets: Mechanisms and performance
INTERNET AND NETWORK ECONOMICS, PROCEEDINGS
2007; 4858: 8295
View details for Web of Science ID 000252182500011

Approximating the radii of point sets
SIAM JOURNAL ON COMPUTING
2007; 36 (6): 17641776
View details for DOI 10.1137/050627472
View details for Web of Science ID 000246299400012

Semidefinite programming approaches for sensor network localization with noisy distance measurements
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING
2006; 3 (4): 360371
View details for DOI 10.1109/TASE.2006.877401
View details for Web of Science ID 000241124200003

Improved complexity results on solving realnumber linear feasibility problems
MATHEMATICAL PROGRAMMING
2006; 106 (2): 339363
View details for DOI 10.1007/s1010700506107
View details for Web of Science ID 000235062200007

Lotsizing scheduling with batch setup times
JOURNAL OF SCHEDULING
2006; 9 (3): 299310
View details for DOI 10.1007/s1095100682657
View details for Web of Science ID 000237397600006

Semidefinite Programming Based Algorithms for Sensor Network Localization
ACM TRANSACTIONS ON SENSOR NETWORKS
2006; 2 (2)
View details for Web of Science ID 000205012900003

Stochastic combinatorial optimization with controllable risk aversion level  (Extended abstract)
APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES
2006; 4110: 224235
View details for Web of Science ID 000240348600020

A Semidefinite Programming Approach to Tensegrity Theory and Realizability of Graphs
PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACMSIAM SYMPOSIUM ON DISCRETE ALGORITHMS
2006: 766775
View details for Web of Science ID 000281596300084

Distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
MULTISCALE OPTIMIZATION METHODS AND APPLICATIONS
2006; 82: 6984
View details for Web of Science ID 000234830500002

Area Editors' Statements
OPERATIONS RESEARCH
2006; 54 (1): 510
View details for DOI 10.1287/opre.1050.0269
View details for Web of Science ID 000235596200002

SpaseLoc: An adaptive subproblem algorithm for scalable wireless sensor network localization
SIAM JOURNAL ON OPTIMIZATION
2006; 17 (4): 11021128
View details for DOI 10.1137/040621600
View details for Web of Science ID 000244631800007

Approximation algorithms for metric facility location problems
SIAM JOURNAL ON COMPUTING
2006; 36 (2): 411432
View details for DOI 10.1137/S0097539703435716
View details for Web of Science ID 000240043700006

Leontief Economies Encode Nonzero Sum TwoPlayer Games
PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACMSIAM SYMPOSIUM ON DISCRETE ALGORITHMS
2006: 659667
View details for Web of Science ID 000281596300072

A new complexity result on solving the Markov decision problem
MATHEMATICS OF OPERATIONS RESEARCH
2005; 30 (3): 733749
View details for DOI 10.1287/moor.1050.0149
View details for Web of Science ID 000231792300011

A multiexchange local search algorithm for the capacitated facility location problem
MATHEMATICS OF OPERATIONS RESEARCH
2005; 30 (2): 389403
View details for DOI 10.1287/moor.1040.0125
View details for Web of Science ID 000230035200007

On solving univariate sparse polynomials in logarithmic time
ACADEMIC PRESS INC ELSEVIER SCIENCE. 2005: 87110
View details for DOI 10.1016/j.jco.2004.03.004
View details for Web of Science ID 000226701700005

On solving coverage problems in a wireless sensor network using Voronoi diagrams
INTERNET AND NETWORK ECONOMICS, PROCEEDINGS
2005; 3828: 584593
View details for Web of Science ID 000234851600058

Computing the ArrowDebreu competitive market equilibrium and its extensions
ALGORITHMIC APPLICATIONS IN MANAGEMENT, PROCEEDINGS
2005; 3521: 35
View details for Web of Science ID 000230475100002

Semidefinite programming algorithms for sensor network localization using angle information
2005 39TH ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS AND COMPUTERS, VOLS 1 AND 2
2005: 220224
View details for Web of Science ID 000238142000040

On approximating complex quadratic optimization problems via semidefinite programming relaxations
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, PROCEEDINGS
2005; 3509: 125135
View details for Web of Science ID 000230361400010

Theory of Semidefinite Programming for Sensor Network Localization
PROCEEDINGS OF THE SIXTEENTH ANNUAL ACMSIAM SYMPOSIUM ON DISCRETE ALGORITHMS
2005: 405414
View details for Web of Science ID 000281595800046

Exchange market equilibria with Leontief's utility: Freedom of pricing leads to rationality
INTERNET AND NETWORK ECONOMICS, PROCEEDINGS
2005; 3828: 1423
View details for Web of Science ID 000234851600003

Improved approximations for max set splitting and max NAE SAT
DISCRETE APPLIED MATHEMATICS
2004; 142 (13): 133149
View details for DOI 10.1016/j.dam.2002.07.001
View details for Web of Science ID 000223098000011

A multiexchange local search algorithm for the capacitated facility location problem  (Extended abstract)
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, PROCEEDINGS
2004; 3064: 219233
View details for Web of Science ID 000222230000017

Improved combinatorial approximation algorithms for the klevel facility location problem
SIAM JOURNAL ON DISCRETE MATHEMATICS
2004; 18 (1): 207217
View details for DOI 10.1137/S0895480102417215
View details for Web of Science ID 000224348700015

Semidefinite programming for ad hoc wireless sensor network localization
IPSN '04: THIRD INTERNATIONAL SYMPOSIUM ON INFORMATION PROCESSING IN SENSOR NETWORKS
2004: 4654
View details for Web of Science ID 000222055900006

Approximating the 2catalog segmentation problem using semidefinite programming relaxations
TAYLOR & FRANCIS LTD. 2003: 705719
View details for DOI 10.1080/10556780310001634082
View details for Web of Science ID 000187296300007

An approximation algorithm for scheduling two parallel machines with capacity constraints
DISCRETE APPLIED MATHEMATICS
2003; 130 (3): 449467
View details for DOI 10.1016/S0166218X(02)006017
View details for Web of Science ID 000185241300006

An improved algorithm for approximating the radii of point sets
APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION
2003; 2764: 178187
View details for Web of Science ID 000185994700016

Improved combinatorial approximation algorithms for the klevel facility location problem
AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS
2003; 2719: 145156
View details for Web of Science ID 000185145700013

New results on quadratic minimization
SIAM JOURNAL ON OPTIMIZATION
2003; 14 (1): 245267
View details for DOI 10.1137/S105262340139001X
View details for Web of Science ID 000185130700010

A 2approximation algorithm for the softcapacitated facility location problem
APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION
2003; 2764: 129140
View details for Web of Science ID 000185994700012

A note on the maximization version of the multilevel facility location problem
OPERATIONS RESEARCH LETTERS
2002; 30 (5): 333335
View details for Web of Science ID 000178894600007

An improved rounding method and semidefinite programming relaxation for graph partition
MATHEMATICAL PROGRAMMING
2002; 92 (3): 509535
View details for DOI 10.1007/s101070100288
View details for Web of Science ID 000176303700007

Improved approximation algorithms for metric facility location problems
APPROXIMATION ALGORITHMS FOR COMBINATORIAL OPTIMIZATION, PROCEEDINGS
2002; 2462: 229242
View details for Web of Science ID 000187294200020
 On smoothing methods for the P0 matrix linear complementarity problem SIAM J. Optimization 2001; 11: 341363

Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation
COMPLEMENTARITY: APPLICATIONS, ALGORITHMS AND EXTENSIONS
2001; 50: 117
View details for Web of Science ID 000168052500001
 Blind Channel Equalization and Approximation Algorithms IEEE Trans. on Signal Processing 2001; 49 (11): 28232831
 A .699approximation algorithm for MaxBisection Mathematical Programming 2001; 90: 101111
 An efficient algorithm for minimizing a sum of Pnorms SIAM J. Optimization 2000; 10: 551579
 A simplification to ``A PrimalDual Interior Point Method Whose Running Time Depends Only on the Constraint Matrix'' High Performance Optimization, Applied Optimization 33 edited by Zhang, et al, S. 2000: 233243
 Application of Semidefinite Programming to Circuit Partitioning Approximation and Complexity in Numerical Optimization edited by Pardalos, P. Kluwer Academics Publishers. 2000: 130136
 Convergence results of analytic center estimator Analytic center approach to bounded error parameter IEEE Transactions on Automatic Control 2000
 Solving largescale sparse semidefinite programs for combinatorial optimization SIAM J. Optimization 2000; 10: 443461
 Probabilistic Analysis of an Infeasible PrimalDual Algorithm for Linear Programming Mathematics of Operations Research 1999; 24: 176192
 On HomotopySmoothing Methods for Variational Inequalities SIAM J. Control & Optimization 1999; 37: 589616
 Infeasiblestart primaldual methods and infeasibility detectors for nonlinear programming problems Mathematical Programming 1999; 84: 227267
 On a homogeneous algorithm for the monotone complementarity problem Mathematical Programming 1999; 84: 375400
 Bounded Error Parameter Estimation: A Sequential Analytic Center Approach IEEE Transactions on Automatic Control 1999; 6 (44): 11071117
 Constrained Logarithmic Least Squares in Parameter Estimation IEEE Transactions on Automatic Control 1999; 1 (44): 182185
 A computational study of the homogeneous algorithm for largescale convex optimization Computational Optimization and Applications 1998; 10: 243269
 Semidefinite Relaxations, Multivariate Normal Distributions, and Order Statistics Handbook of Combinatorial Optimization edited by Du, D., Z., Pardalos, P.M. Kluwer Academic Publishers. 1998: 119
 On the complexity of approximating a KKT point of quadratic programming Mathematical Programming 1998; 80: 195212
 Approximation algorithms for quadratic programming Journal of Combinatorial Optimization 1998; 1 (2): 2950
 Approximate Farkas lemmas and stopping rules for iterative infeasiblepoint algorithms for linear programming Mathematical Programming 1998; 81: 122
 An infeasible interiorpoint algorithm for solving primal and dual geometric programs Mathematical Programming 1997; 76: 155182
 Complexity analysis of the analytic center cutting plane method that uses multiple cuts Mathematical Programming 1997; 78: 85104
 On homogeneous and selfdual algorithm for LCP Mathematical Programming 1997; 76: 211222
 On a homogeneous algorithm for a monotone complementarity problem with nonlinear equality constraints Complementarity and variational Problems: State of the art edited by Ferris, Michael, C., Pang, J. SIAM. 1997: 111
 Improved complexity using higherorder correctors for primaldual Dikin affine scaling Mathematical Programming 1997; 76: 117130
 Efficient algorithms for minimizing a sum of Euclidean norms with applications SIAM J. Optimization 1997; 7: 10171036
 A primaldual interiorpoint method whose running time depends only on the constraint matrix Mathematical Programming 1996; 74: 79120
 Interiorpoint methods for nonlinear complementarity problem Journal of Optimization Theory and Application 1996; 68
 How partial knowledge helps to solve linear programs Journal of Complexity 1996; 12: 480491
 Complexity analysis of an interiorpoint cutting plane method for convex feasibility problem SIAM J. Optimization 1996; 6: 638652
 Combining interiorpoint and pivoting algorithms for linear programming Management Science 1996; 42: 17191731
 A lower bound on the number of iterations of longstep and polynomial interiorpoint linear programming algorithms Annals of Operations Research 1996; 62: 233252
 A asymptotical O(√nL) iteration pathfollowing linear programming algorithm that uses long steps SIAM J. Optimization 1996; 6: 570586
 Identifying an optimal basis in linear programming Annals of Operations Research 1996; 62: 565572
 A simplified homogeneous and selfdual linear programming algorithm and its implementation Annals of Operations Research 1996; 62: 151172
 A surface of analytic centers and infeasibleinteriorpoint algorithms for linear programming Mathematics of Operations Research 1995; 20: 135162
 On the von Neumann economic growth problem Mathematics Operations Research 1995; 20: 617633
 Condition numbers for polyhedra with real number data Operations Research Letters 1995; 17: 209214
 A generalized homogeneous and selfdual linear programming algorithm Operations Research Letters 1995; 17
 On the convergence of the iteration sequence in primaldual interiorpoint methods Mathematical Programming 1995; 68: 141154
 The optimal choice of inputs under time of use pricing, fixed proportions technology and adjustment costs: an application to industrial firms Management Sciences 1995; 41: 16791692
 A convergent algorithm for quantile regression with smoothing splines Computational Statistics & Data Analysis 1995; 19: 613630
 Specially structured uncapacitated facility location problems Operations Research 1995; 43: 661669
 Combining binary search and Newton's method to compute real roots for a class of real functions Journal of Complexity 1994; 10: 271280
 A genuine quadratically convergent polynomial interior point algorithm for linear programming Advances in Optimization and Approximation edited by Du, D., Sun, J. Kluwer Academic Publishers, Boston. 1994: 1
 On the complexity of a column generation algorithm for convex or quasiconvex feasibility problems Large Scale Optimization: State of the Art edited by Hager, W., Hearn, D., Pardalos, P. Kluwer Academic Publishers, Boston. 1994: 182191
 A complexity analysis for interiorpoint algorithms based on Karmarkar's potential functions SIAM J. on Optimization 1994; 4: 512520
 Toward probabilistic analysis of interiorpoint algorithms for linear programming Mathematics of Operations Research 1994; 19: 3852
 An $O(\sqrt{n}L)$iteration homogeneous and selfdual linear programming algorithm Mathematics of Operations Research 1994; 19: 5367
 An accelerated interiorpoint method whose running time depends only on $A$ 1994
 A decomposition variant of the potential reduction algorithm for linear programming Management Science 1993; 39: 757776
 Minimal adjustment costs, factor demands, and seasonal timeofuse electricity rates Resource and Energy Economics 1993; 15: 313335
 On finding an interior point on the optimal face of linear programs Mathematical Programming 1993; 62: 497516
 Average performance of a selfdual interiorpoint algorithm for linear programming Complexity in Numerical Optimization edited by Pardalos, P. World Scientific, New Jersey. 1993: 115
 Translation cuts for convex minimization Complexity in Numerical Optimization edited by Pardalos, P. World Scientific, New Jersey. 1993: 5773
 Solutions of $P_0$matrix linear complementarity problems SIAM J. on Matrix Anal. Appl. 1993; 14: 10481060
 Nearboundary behavior of the primaldual potential reduction algorithm for linear programming Mathematical Programming 1993; 58: 243255
 An extension of the potential reduction algorithm for solving LCP with priority goals Linear Algebra and its Applications 1993; 193: 3550
 A quadratically convergent polynomial interiorpoint algorithm for solving entropy optimization problems SIAM J. on Optimization 1993; 3: 843860
 On quadratic and $O(\sqrt{n}L)$ convergence of a predictor corrector algorithm for LCP Mathematical Programming 1993; 62: 537552
 On adaptivestep primaldual interiorpoint algorithms for linear programming Mathematics of Operations Research 1993; 18: 964981
 A quadratically convergent $O(\sqrt{n}L)$iteration algorithm for linear programming Mathematical Programming 1993; 59: 151162
 A fully polynomialtime approximation algorithm for computing a stationary point of the general LCP Mathematics of Operations Research 1993; 18: 334345
 Convergence behavior of some interiorpoint algorithms Mathematical Programming 1993; 60: 215228
 Extensions of the potential reduction algorithm for linear programming Journal of Optimization Theory and Applications 1992; 193: 3550
 On the Qorder of convergence of interiorpoint algorithms for linear programming edited by Fang, W. 1992
 A further result on potential reduction algorithm for the Pmatrix linear complementarity problem Advances in Optimization and Parallel Computing, edited by Pardalos, P. NorthHolland, NY. 1992: 1
 A new complexity result on minimization of a quadratic function with a sphere constraint Recent Advances in Global Optimization edited by Floudas, C., Pardalos, P. Princeton University Press, NJ. 1992: 1
 On affine scaling algorithms for nonconvex quadratic programming Mathematical Programming 1992; 56: 285300
 Comparative analysis of affine scaling algorithms for linear programming Mathematical Programming 1992; 52: 405414
 A potential reduction algorithm allowing column generation SIAM J. on Optimization 1992; 2: 720
 On the finite convergence of interiorpoint algorithms for linear programming Mathematical Programming 1992; 57: 325335
 Implementation of interiorpoint algorithms for some entropy optimization problems Optimization Methods and Software 1992; 1: 7180
 An interior point potential reduction algorithm for the linear complementarity problem Mathematical Programming 1992; 54: 267279
 A class of LCPs solvable in polynomial time Linear Algebra and its Applications 1991; 152: 317
 Interiorpoint algorithms for quadratic programming Recent Developments in Mathematical Programming edited by Kumar, S. Gordon \& Breach Scientific Publishers, Philadelphia. 1991: 1
 On some efficient interior point methods for nonlinear convex programming Linear Algebra and its Applications 1991; 152: 169189
 Interiorpoint algorithms for solving nonlinear optimization problems COAL Newsletter 1991; 19: 4554
 Convergence behavior of Karmarkar's projective algorithm for solving a simple linear program Operations Research Letters 1991; 10: 389393
 An $O(n^3L)$ potential reduction algorithm for linear programming Mathematical Programming 1991; 50: 239258
 Algorithms for the solution of quadratic knapsack problems Linear Algebra and its Applications 1991; 152: 6991
 A class of projective transformations for linear programming SIAM J. on Computing 1990; 19: 457466
 A centered projective algorithm for linear programming Mathematics of Operations Research 1990; 15: 508529
 Computational aspects of an interior point algorithm for quadratic programming problems with box constraints LargeScale Numerical Optimization edited by Coleman, T., F., Li, Y. SIAM, Philadelphia. 1990: 1
 Interiorpoint algorithms for global optimization Annals of Operations Research 1990; 25: 5974
 Containing and shrinking ellipsoids in the pathfollowing algorithm Mathematical Programming 1990; 47: 19
 A ``builddown'' scheme for linear programming Mathematical Programming 1990; 46: 6172
 Recovering optimal basic variables in Karmarkar's polynomial algorithm for linear programming Mathematics of Operations Research 1990; 15: 564571

AN EXTENSION OF KARMARKAR PROJECTIVE ALGORITHM FOR CONVEX QUADRATICPROGRAMMING
MATHEMATICAL PROGRAMMING
1989; 44 (2): 157179
View details for Web of Science ID A1989AE14900003
 An extension of Karmarkar's projective algorithm for convex quadratic programming Mathematical Programming 1989; 44: 157179
 Eliminating columns in the simplex method for linear programming Journal of Optimization Theory and Applications 1989; 63: 103111

RECOVERING OPTIMAL DUAL SOLUTIONS IN KARMARKARS POLYNOMIAL ALGORITHM FOR LINEARPROGRAMMING
MATHEMATICAL PROGRAMMING
1987; 39 (3): 305317
View details for Web of Science ID A1987L163200006

KARMARKAR ALGORITHM AND THE ELLIPSOID METHOD
OPERATIONS RESEARCH LETTERS
1987; 6 (4): 177182
View details for Web of Science ID A1987K479100005
 Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming Mathematical Programming 1987; 39: 305317
 A conclusion on `missing number' in ergodic exponents of $s\times s$ stochastic matrices Journal of Huazhong University of Science and Technology 1983; 2
 Directed graphs, linear Diophantine equations, and ergodic problems of stochastic matrices, English Edit. Journal of Huazhong University of Science and Technology 1982; 2