36717822
On approximation of max-vertex-cover
Abstract We consider the max-vertex-cover (MVC) problem, i.e., find k vertices from an undirected and edge-weighted graph G =( V , E ), where | V |= n ⩾ k , such that the total edge weight covered by the k vertices is maximized. There is a 3/4-approximation algorithm for MVC, based on a linear programming relaxation. We show that the guaranteed ratio can be improved by a simple greedy algorithm for k >(3/4) n , and a simple randomized algorithm for k >(1/2) n . Furthermore, we study a semidefinite programming (SDP) relaxation based approximation algorithms for MVC. We show that, for a range of k , our SDP-based algorithm achieves the best performance guarantee among the four types of algorithms mentioned in this paper.
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.
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.
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.
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.
17936055
An Empirical User Study of an Active Reuse Repository System
This paper reports an empirical user study of an active reuse repository system. Instead of waiting passively for software developers to initiate the component location process with a well-defined reuse query, active reuse repository systems infer reuse queries from syntactic and semantic cues present in partially constructed programs in development environments, and proactively deliver components that match the inferred reuse queries. The reported empirical user study of an implemented active reuse repository system called CodeBroker shows that active repository systems promote reuse by motivating and enabling software developers to reuse components whose existence is not anticipated, and reducing the cost of reuse through the automation of the component location process.
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.
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.
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.
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.