Explore the vast range of titles available.

In the generalized balanced optimization problem (GBaOP) the objective value is minimized over all feasible subsets S of E  = {1, . . . , m }. We show that the algorithm proposed in Punnen and Aneja (Oper Res Lett 32:27–30, 2004 ) can be modified to ensure that the resulting solution is indeed optimal. This modification is attained at the expense of increased worst-case complexity, but still maintains polynomial solvability of various special cases that are of general interest. In particular, we show that GBaOP can be solved in polynomial time if an associated bottleneck problem can be solved in polynomial time. For the solution of this bottleneck problem, we propose two alternative approaches.

This paper presents a portfolio approach to estimating the average correlation coefficient of a group of stocks which are considered for portfolio analysis. The average correlation coefficient has been shown to produce a better estimate of the future correlation matrix than individual pairwise correlations. The advantage of the approach described here is that it does not require the estimation of pairwise correlations for estimating their average.

We present a model of capacity expansion in which capacity can be either expanded or contracted over time. Our model allows for economies of scale often associated with capacity expansion. Furthermore, we incorporate lump-sum penalty costs incurred when capacity is added to accommodate excess demand on an emergency basis. We use dynamic programming and K-convexity methods to characterize the nature of the optimal policy. We show that an expansion and contraction policy of a \"simple\" form is optimal if the demand distribution function is concave. Furthermore, we provide an example to demonstrate that, if the distribution function for the demand is not concave, one can always choose a set of parameter values for which the problem does not possess a simple optimal policy.

We propose a scheme for generating a weakly chordal graph on n vertices with m edges. In this method, we first construct a tree and then generate an orthogonal layout (which is a weakly chordal graph on the n vertices) based on this tree. In the next and final step, we insert additional edges to give us a weakly chordal graph on m edges. Our algorithm ensures that the graph remains weakly chordal after each edge is inserted. The time complexity of an insertion query is O(n^3) time and an insertion takes constant time. On the other hand, a generation algorithm based on finding a 2-pair takes O(nm) time using the algorithm of Arikati and Rangan [1].

Strongly chordal graphs are a subclass of chordal graphs. The interest in this subclass stems from the fact that many problems which are NP-complete for chordal graphs are solvable in polynomial time for this subclass. However, we are not aware of any algorithm that can generate instances of this class, often necessary for testing purposes. In this paper, we address this issue. Our algorithm first generates chordal graphs, using an available algorithm and then adds enough edges to make it strongly chordal, unless it is already so. The edge additions are based on a totally balanced matrix characterizations of strongly chordal graphs.

Using a connected dominating set (CDS) to serve as the virtual backbone of a wireless sensor network (WSN) is an effective way to save energy and reduce the impact of broadcasting storms. Since nodes may fail due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault tolerant. This could be modeled as a k-connected, m-fold dominating set ((k,m)-CDS). Given a virtual undirected network G=(V,E), a subset C\\subset V is a (k,m)-CDS of G if (i) G[C], the subgraph of G induced by C is k-connected, and (ii) each node in V\\C has at least m neighbors in C. We present a two-phase greedy algorithm for computing a (2,2)-CDS that achieves an asymptotic approximation factor of \\((3+\\ln(\\Delta+2))\\), where \\(\\Delta\\) is the maximum degree of G. This result improves on the previous best known performance factor of \\((4+\\ln\\Delta+2\\ln(2+\\ln\\Delta))\\) for this problem.

The multi-commodity minimum disconnecting set in a given network is of considerable interest in military operations. The present known methods of finding the multi-commodity minimum disconnecting set consist of implicit enumeration techniques or techniques which involve the solution of several specially structured linear integer programs known as set-covering problems. In this paper we present an efficient method of finding the multi-commodity minimum disconnecting set by solving a single set-covering problem. Extensions and computational experience are also discussed.

A portfolio approach is developed for estimating the average of the pairwise correlations among stock returns. The approach does not require the estimation of pairwise correlations for estimating their average. For N securities in one group, the portfolio approach will estimate only N + 1 variances: the variance of N securities and the variance of a portfolio where investment in each security equals the reciprocal of its sample standard deviation. The average correlation coefficient has been shown to produce a better estimate of the future correlation matrix than individual pairwise correlations. It is hoped that the present investigation will generate more interest in the constant correlation model (CCM), which appears to have been ignored despite its advantages. The CCM uses the historical average correlation coefficient for the future.