Yinyu Ye Complexity theory is the foundation of computer algorithms. The goal of the theory is to develop criteria for measuring effectiveness and efficiency of various algorithms and difficulty of various problems. The term ``complexity'' refers to the amount of resources required by a computation. In this proposal, running time or number of arithmetic operations is the major resource of interest. The aim of the proposal is to further develop the complexity theory of linear programming (LP). In particular, we analyze ``condition'' numbers that determine the degree of difficulty of an LP problem, and ``precondition'' the problem using Partial Knowledge. Therefore, we study whether or not certain kinds of partial knowledge could help in solving this problem and how they impact the complexity of the problem. If such knowledge is helpful and available, then an experienced owner of LP problem instances might be able to use it to solve them more effectively. In general, progress in the area of developing efficient algorithms for solving large-scale optimization problems will be of great importance in improving the efficiency of manufacturing systems, communication networks, aircraft routing, multiple-flow operations, and resources planning. Strengthening research in this area will contribute to the national interest in industrial competitiveness and scientific knowledge. Businesses, large and small, use LP models to optimize telecommunication networks, to schedule traffic flows, to control manufacturing processes, to plan financial investments, to minimize production costs, etc. LP has been the mostly used applied mathematics and computation tool. Historically, research developments on LP have dramatically widened the scope of its applications. Many problems, which were "unsolvable" 15 years ago, are now solved in few minutes and in real time. The anticipated findings and discoveries resulting from this proposed project will strengthen and improve theoretical results and practical performance of LP algorithms further, and may lead to the development of new high-performance algorithms for a variety of computational problems.
