6952873
Leontief economies encode nonzero sum two-player games
We consider Leontief exchange economies, i.e., economies where the consumers desire goods in fixed proportions. Unlike bimatrix games, such economies are not guaranteed to have equilibria in general. On the other hand, they include suitable restricted versions which always have equilibria.We give a reduction from two-player games to a special family of Leontief exchange economies, which are guaranteed to have equilibria, with the property that the Nash equilibria of any game are in one-to-one correspondence with the equilibria of the corresponding economy.Our reduction exposes a potential hurdle inherent in solving certain families of market equilibrium problems: finding an equilibrium for Leontief economies (where an equilibrium is guaranteed to exist) is at least as hard as finding a Nash equilibrium for two-player nonzero sum games.As a corollary of the one-to-one correspondence, we obtain a number of hardness results for questions related to the computation of market equilibria, using results already established for games [17]. In particular, among other results, we show that it is NP-hard to say whether a particular family of Leontief exchange economies, that is guaranteed to have at least one equilibrium, has more than one equilibrium.Perhaps more importantly, we also prove that it is NP-hard to decide whether a Leontief exchange economy has an equilibrium. This fact should be contrasted against the known PPAD-completeness result of [30], which holds when the problem satisfies some standard sufficient conditions that make it equivalent to the computational version of Brouwer's Fixed Point Theorem.On the algorithmic side, we present an algorithm for finding an approximate equilibrium for some special Leontief economies, which achieves quasi-polynomial time whenever each trader does not demand too much more of any good than some other good.
206798229
On affine scaling algorithms for nonconvex quadratic programming
We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a “hard” problem, we show that the problem with an ellipsoidal constraint is “easy”. When the “hard” QP is solved by successively solving the “easy” QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.
12762926
Theory of semidefinite programming for Sensor Network Localization
AbstractWe analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior-point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we show, for the first time, that these networks can be localized in polynomial time. We also give a simple and efficient criterion for checking whether a given instance of the localization problem has a unique realization in
$$\mathcal{R}^2$$ using graph rigidity theory. Finally, we introduce a notion called strong localizability and show that the SDP model will identify all strongly localizable sub-networks in the input network.
6954893
How Partial Knowledge Helps to Solve Linear Programs
We present results on how partial knowledge helps to solve linear programs. In particular, if a linear system,Ax=bandx?0, has an interior feasible point, then we show that finding a feasible point to this system can be done inO(n2.5c(A)) iterations by the layered interior-point method, and each iteration solves a least-squares problem, wherenis the dimension of vectorxandc(A) is the condition number of matrixAdefined by Vavasis and Ye. This complexity bound is reduced by a factornfrom that when this property does not exists. We also present a result for solving the problem using a little strong knowledge.
10134807
A semidefinite programming approach to tensegrity theory and realizability of graphs
Recently, Connelly and Sloughter [14] have introduced the notion of d-realizability of graphs and have, among other things, given a complete characterization of the class of 3-realizable graphs. However, their work has left open the question of finding an algorithm for realizing those graphs. In this paper, we resolve that question by showing that the semidefinite programming (SDP) approach of [11, 32] can be used for realizing 3-realizable graphs. Specifically, we use SDP duality theory to show that given a graph G and a set of lengths on its edges, the optimal dual multipliers of a certain SDP give rise to a proper equilibrium stress for some realization of G. Using this result and the techniques in [14, 31], we then obtain a polynomial time algorithm for (approximately) realizing 3-realizable graphs. Our results also establish a little-explored connection between SDP and tensegrity theories and allow us to derive some interesting properties of tensegrity frameworks.
9510976
An interior point potential reduction algorithm for the linear complementarity problem
AbstractThe linear complementarity problem (LCP) can be viewed as the problem of minimizingxTy subject toy=Mx+q andx, y⩾0. We are interested in finding a point withxTy  0. The algorithm proceeds by iteratively reducing the potential function
$$f(x,y) = \rho \ln x^T y - \Sigma \ln x_j y_j ,$$
 where, for example,ρ=2n. The direction of movement in the original space can be viewed as follows. First, apply alinear scaling transformation to make the coordinates of the current point all equal to 1. Take a gradient step in the transformed space using the gradient of the transformed potential function, where the step size is either predetermined by the algorithm or decided by line search to minimize the value of the potential. Finally, map the point back to the original space.A bound on the worst-case performance of the algorithm depends on the parameterλ*=λ*(M, ε), which is defined as the minimum of the smallest eigenvalue of a matrix of the form
$$(I + Y^{ - 1} MX)(I + M^T Y^{ - 2} MX)^{ - 1} (I + XM^T Y^{ - 1} )$$
 whereX andY vary over the nonnegative diagonal matrices such thateTXYe ⩾ε andXjjYjj⩽n2. IfM is a P-matrix,λ* is positive and the algorithm solves the problem in polynomial time in terms of the input size, |log ε|, and 1/λ*. It is also shown that whenM is positive semi-definite, the choice ofρ = 2n+
$$\sqrt {2n} $$
 yields a polynomial-time algorithm. This covers the convex quadratic minimization problem.
12123304
Integrating active information delivery and reuse repository systems
Although software reuse can improve both the quality and productivity of software development, it will not do so until software developers stop believing that it is not worth their effort to find a component matching their current problem. In addition, if the developers do not anticipate the existence of a given component, they will not even make an effort to find it in the first place.
Even the most sophisticated and powerful reuse repositories will not be effective if developers don't anticipate a certain component exists, or don't deem it worthwhile to seek for it. We argue that this crucial barrier to reuse is overcome by integrating active information delivery, which presents information without explicit queries from the user, and reuse repository systems. A prototype system, CodeBroker, illustrates this integration and raises several issues related to software reuse.
1677204
Personalizing Delivered Information in a Software Reuse Environment
Browsing- and querying-oriented schemes have long served as the principal techniques for software developers to locate software components from a component repository for reuse. Unfortunately, the problem remains that software developers simply will not actively search for components when they are unaware that they need components or that relevant components even exist. Thus, to assist software developers in making full use of large component repositories, information access need to be complemented by information delivery. Effective delivery of components calls for the personalization of the components to the task being performed and the knowledge of the user performing it.We have designed, implemented, and evaluated the CodeBroker system to support personalized component delivery to increase the usefulness of a Java software reuse environment.
1538182
Information delivery in support of learning reusable software components on demand
An inherent dilemma exists in the design of high-functionality applications (such as repositories of reusable software components). In order to be useful, high-functionality applications have to provide a large number of features, creating huge learning problems for users. We address this dilemma by developing intelligent interfaces that support learning on demand by enabling users to learn new features when they are needed during work. We support learning on demand with information delivery by identifying learning opportunities of which users might not be aware. The challenging issues in implementing information delivery are discussed and techniques to address them are illustrated with the CodeBroker system. CodeBroker supports Java programmers in learning reusable software components in the context of their normal development environments and practice by proactively delivering task-relevant and personalized information. Evaluations of the system have shown its effectiveness in supporting learning on demand.
17120633
Promoting Reuse with Active Reuse Repository Systems
Software component-based reuse is difficult for software developers to adopt because first they must know what components exist in a reuse repository and then they must know how to retrieve them easily. This paper describes the concept and implementation of active reuse repository systems that address the above two issues. Active reuse repository systems employ active information delivery mechanisms to deliver potentially reusable components that are relevant to the current development task. They can help software developers reuse components they did not even know existed. They can also greatly reduce the cost of component location because software developers need neither to specify reuse queries explicitly, nor to switch working contexts back and forth between development environments and reuse repository systems.
17341139
Context-aware browsing of large component repositories
The paper proposes a novel approach to locating software components from a large component repository: context-aware browsing. Without any explicit input from software developers, this approach automatically locates and presents a list of software components that could possibly be used in the current development situation. This automation of the component location process not only greatly reduces the search space of components so that software developers can easily browse and choose the desired components, but also enables software developers to use components whose existence they do not even anticipate. A software agent that supports context-aware browsing has been developed and evaluated.