327125
Approximation Algorithms for Quadratic Programming
AbstractWe consider the problem of approximating the global minimum of a general quadratic program (QP) with n variables subject to m ellipsoidal constraints. For m=1, we rigorously show that an ∈-minimizer, where error ∈ ∈ (0, 1), can be obtained in polynomial time, meaning that the number of arithmetic operations is a polynomial in n, m, and log(1/∈). For m ≥ 2, we present a polynomial-time (1-
$$\frac{1}{{m^2 }}$$
)-approximation algorithm as well as a semidefinite programming relaxation for this problem. In addition, we present approximation algorithms for solving QP under the box constraints and the assignment polytope constraints.
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.
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.
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.
1476378
Toward an understanding of the motivation of open source software developers
An Open Source Software (OSS) project is unlikely to be successful unless there is an accompanied community that provides the platform for developers and users to collaborate. Members of such communities are volunteers whose motivation to participate and contribute is of essential importance to the success of OSS projects. In this paper, we aim to create an understanding of what motivates people to participate in OSS communities. We theorize that learning is one of the motivational forces. Our theory is grounded in the learning theory of Legitimate Peripheral Participation, and is supported by analyzing the social structure of OSS communities and the co-evolution between OSS systems and communities. We also discuss practical implications of our theory for creating and maintaining sustainable OSS communities as well as for software engineering research and education.
19594900
Reuse-Conducive Development Environments
Despite its well-recognized benefits, software reuse has not met its expected success due to technical, cognitive, and social difficulties. We have systematically analyzed the reuse problem (especially the cognitive and social difficulties faced by software developers who reuse) from a multidimensional perspective, drawing on our long-term research on information retrieval, human-computer interaction, and knowledge-based systems. Based on this analysis, we propose the concept of reuse-conducive development environments, which encourage and enable software developers to reuse through the smooth integration of reuse repository systems and development environments. We have designed, implemented, and evaluated CodeBroker—a reuse-conducive development environment—that autonomously locates and delivers task-relevant and personalized components into the current software development environment. Empirical evaluations of CodeBroker have shown that the system is effective in promoting reuse by enabling software developers to reuse components unknown to them, reducing the difficulties in locating components, and augmenting the programming capability of software developers.
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.
8137126
An active and adaptive reuse repository system
Although software reuse repository systems have been an active research area for more than a decade, one important aspect has not been given enough attention: if software developers make no attempt to reuse, repository systems offer no help and reuse will not happen. Active information delivery, which presents information without being given explicit queries can motivate software developers to reuse. Critical challenges for active delivery systems are the contextualization of delivered information to the development task, and the adaptation of the information to each developer. This paper discusses how to address these challenges and demonstrates the feasibility of implementation through a prototype system.
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.