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.
2615907
Stochastic Combinatorial Optimization with Controllable Risk Aversion Level
Due to their wide applicability and versatile modeling power, stochastic programming problems have received a lot of attention in many communities. In particular, there has been substantial recent interest in 2–stage stochastic combinatorial optimization problems. Two objectives have been considered in recent work: one sought to minimize the expected cost, and the other sought to minimize the worst–case cost. These two objectives represent two extremes in handling risk — the first trusts the average, and the second is obsessed with the worst case. In this paper, we interpolate between these two extremes by introducing an one–parameter family of functionals. These functionals arise naturally from a change of the underlying probability measure and incorporate an intuitive notion of risk. Although such a family has been used in the mathematical finance [11] and stochastic programming [13] literature before, its use in the context of approximation algorithms seems new. We show that under standard assumptions, our risk–adjusted objective can be efficiently treated by the Sample Average Approximation (SAA) method [9]. In particular, our result generalizes a recent sampling theorem by Charikar et al. [2], and it shows that it is possible to incorporate some degree of robustness even when the underlying probability distribution can only be accessed in a black–box fashion. We also show that when combined with known techniques (e.g. [4,14]), our result yields new approximation algorithms for many 2–stage stochastic combinatorial optimization problems under the risk–adjusted setting.
9107374
Market equilibria for homothetic, quasi-concave utilities and economies of scale in production
Eisenberg and Gale (1959) gave a convex program for computing market equilibrium for Fisher's model for linear utility functions, and Eisenberg (1961) generalized this to concave homogeneous functions of degree one. We further generalize to:1. Homothetic, quasi-concave utilities. This also helps extend Eisenberg's result to concave homogeneous functions of arbitrary degree.2. We introduce the notion of a trading cone which enables us to compute market equilibrium in the presence of economies of scale in production provided differential pricing is allowed. Applications to network pricing are provided.
44474419
On the complexity of approximating a KKT point of quadratic programming
We present a potential reduction algorithm to approximate a Karush—Kuhn—Tucker (KKT) point of general quadratic programming (QP). We show that the algorithm is a fully polynomial-time approximation scheme, and its running-time dependency on accuracy ε ∈ (0, 1) is O((l/ε) log(l/ε) log(log(l/ε))), compared to the previously best-known result O((l/ε)2). Furthermore, the limit of the KKT point satisfies the second-order necessary optimality condition of being a local minimizer. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
17282210
An approximation algorithm for scheduling two parallel machines with capacity constraints
We consider the problem of scheduling n independent jobs on two identical parallel machines, with a limit on the number of jobs that can be assigned to each single machine, so as to minimize the total weighted completion time of the jobs. We study a semidefinite programming-based approximation algorithm for solving this problem and prove that the algorithm has a worst case ratio at most 1.1626.
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.
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.
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.
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.
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.
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.