8002168
Semidefinite programming based algorithms for sensor network localization
An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite program that can be solved efficiently.The basic model is extended in order to account for noisy distance information. In particular, a maximum likelihood based formulation and an interval based formulation are discussed. The SDP solution can then also be used as a starting point for steepest descent based local optimization techniques that can further refine the SDP solution.We also describe the extension of the basic method to develop an iterative distributed SDP method for solving very large scale semidefinite programs that arise out of localization problems for large dense networks and are intractable using centralized methods.The performance evaluation of the technique with regard to estimation accuracy and computation time is also presented by the means of extensive simulations.Our SDP scheme also seems to be applicable to solving other Euclidean geometry problems where points are locally connected.
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.
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.
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.
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.
18302519
Dynamic community: a new conceptual framework for supporting knowledge collaboration in software development
Software development is a knowledge intensive activity and software developers are knowledge workers. Knowledge needed for software development is often distributed among different developers. Supporting efficient knowledge collaboration and transfer is thus essential for software development organizations to remain competitive. This paper proposes a new theory /sub y/namic community to support knowledge collaboration and discusses its application in software development. Dynamic community integrates the traditional knowledge management approach in which knowledge is formalized and accumulated in knowledge repositories, and the community-based knowledge collaboration approach in which knowledge is transferred through informal community participation and human contacts. The dynamic community theory takes into full consideration individual knowledge workers' ever-changing needs for new knowledge as well as the role of social relationship of knowledge workers in effective knowledge collaboration. This paper introduces the dynamic community theory, a general system architecture of sociotechnical environments in support of dynamic community, and its application in software development.
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.
6298363
Supporting reuse by delivering task-relevant and personalized information
Technical, cognitive, and social factors inhibit the widespread success of systematic software reuse. Our research is primarily concerned with the cognitive and social challenges faced by software developers: how to motivate them to reuse and how to reduce the difficulty of locating components from a large reuse repository. Our research has explored a new interaction style between software developers and reuse repository systems enabled by information delivery mechanisms. Instead of passively waiting for software developers to explore the reuse repository with explicit queries, information delivery autonomously locates and presents components by using the developers' partially written programs as implicit queries.We have designed, implemented, and evaluated a system called CodeBroker, which illustrates different techniques to address the essential challenges in information delivery: to make the delivered information relevant to the task-at-hand and personalized to the background knowledge of an individual developer. Empirical evaluations of CodeBroker show that information delivery is effective in promoting reuse.
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.
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.