Search

In this paper the robust spanning tree problem and the relative robust spanning tree problem on an arbitrary graph, whose edge costs vary over a finite set, are considered. All possible combinations of the edge cost form the scenario set. We show that the absolute robust spanning tree problem is polynomially solvable. The relative robust spanning tree problem, when the edge cost of each edge varies over a specified interval, is known to be NP-complete. Status of the relative robust spanning tree problem with edge costs varying over a finite set of values is open. Two local search algorithms, TREE and STAGE2 have been designed for this problem. For graphs with upto 12 nodes our results matched exactly with the optimal solution. For, graphs with 15 nodes computing the exact solution was becoming intractable.

In this paper, we study linear constraint systems in which each constraint is a fractional Horn constraint. A constraint is fractional Horn, if it can be written in the form: ∑ i = 1 n a i ⋅ x i ≥ c , where each a i is integral, c is integral, at most one of the a i s is positive, and all negative a i s are equal to −1. A conjunction of fractional Horn constraints is called a Fractional Horn Constraint Systems (FHS). FHSs generalize a number of specialized constraint systems such as Difference Constraint Systems (DCS) and Horn Constraint Systems (HCS). We know that the problem of checking lattice point feasibility in DCSs and HCSs is in P. In contrast, we show that the problem of checking lattice point feasibility in FHSs is NP-complete. We then study a sub-class of fractional Horn constraint systems called Binary Fractional Horn Constraint Systems (BFHS). In a BFHS, each constraint has at most two non-zero coefficients. In this case, we show that the problem of checking integer feasibility is in P. Furthermore, we establish several properties of the least integer point and the least linear point of a BFHS, if they exist.

In this paper, we investigate variants of cutting plane proof systems for a class of integer programs called Horn constraint systems (HCS). Briefly a system of linear inequalities \(\mathbf{A \cdot x \ge b}\) is called a Horn constraint system, if each entry in \(\mathbf{A}\) belongs to the set \(\{0,1,-1\}\) and furthermore there is at most one positive entry per row. Our focus is on deriving refutations i.e., proofs of unsatisfiability of such programs in variants of the cutting plane proof system. Horn systems generalize Horn formulas, i.e., CNF formulas with at most one positive literal per clause. A Horn system which results from rewriting a Horn clausal formula is called a Horn clausal constraint system (HClCS). The cutting plane calculus (CP) is a well-known calculus for deciding the unsatisfiability of propositional CNF formulas and integer programs. Usually, CP consists of the addition rule (ADD) and the division rule (DIV). We show that the cutting plane calculus with the addition rule only (CP-ADD) does not require constraints of the form \(0 \le x_i \le 1\). We also investigate the existence of read-once refutations in Horn clausal constraint systems in the cutting plane proof system. We show that read-once refutations are incomplete and furthermore the problem of checking for the existence of a read-once refutation in an arbitrary Horn clausal system is NP-complete.

An important first step when deploying a wireless ad hoc network is neighbor discovery in which every node attempts to determine the set of nodes it can communicate with in one wireless hop. In the recent years, cognitive radio (CR) technology has gained attention as an attractive approach to alleviate spectrum congestion. A cognitive radio transceiver can operate over a wide range of frequencies, possibly scanning multiple frequency bands. A cognitive radio node can opportunistically utilize unused wireless spectrum without interference from other wireless devices in its vicinity. Due to spatial variations in frequency usage and hardware variations in radio transceivers, different nodes in the network may perceive different subsets of frequencies available to them for communication. This heterogeneity in the available channel sets across the network increases the complexity of solving the neighbor discovery problem in a cognitive radio network. In this work, we design and analyze several randomized algorithms for neighbor discovery in such a (heterogeneous) network under a variety of assumptions (e.g. maximum node degree known or unknown) for both synchronous and asynchronous systems under minimal knowledge. We also show that our randomized algorithms are naturally suited to tolerate unreliable channels and adversarial attacks., 54 pages, 5 figures, 1 table, 6 algorithms, accepted in Journal of Parallel and Distributed Computing

In this paper, we study linear constraint systems in which each constraint is a fractional Horn constraint. A constraint is fractional horn, if it can be written in the form: \(\sum _{i=1}^{n}a_{i}\cdot x_{i}\ge c\), where the \(a_{i}\) and c are integral, and at most one of the \(a_{i}>0\) and all negative \(a_{i}\) are equal to \(-1\). A conjunction of fractional Horn constraints is called a Fractional Horn Systems (FHS). FHSs generalize a number of specialized constraint systems such as Difference Constraint Systems and Horn Constraint Systems. We show that the problem of checking linear feasibility in these systems is in P, whereas the problem of checking lattice point feasibility is NP-complete. We then study a sub-class of fractional horn systems called Binary fractional horn systems (BFHS) in which each constraint has at most two non-zero coefficients with at most one being positive. In this case, we show that the problem of lattice point feasibility is in P.

In data centers, data replication is the primary method used to ensure availability of customer data. To avoid correlated failure, cloud storage infrastructure providers model hierarchical failure domains using a tree, and avoid placing a large number of data replicas within the same failure domain (i.e. on the same branch of the tree). Typical best practices ensure that replicas are distributed across failure domains, but relatively little is known concerning optimization algorithms for distributing data replicas. Using a hierarchical model, we answer how to distribute replicas across failure domains optimally. We formulate a novel optimization problem for replica placement in data centers. As part of our problem, we formalize and explain a new criterion for optimizing a replica placement. Our overall goal is to choose placements in which correlated failures disable as few replicas as possible. We provide two optimization algorithms for dependency models represented by trees. We first present an $O(n + \rho \log \rho)$ time dynamic programming algorithm for placing $\rho$ replicas of a single file on the leaves (representing servers) of a tree with $n$ vertices. We next consider the problem of placing replicas of $m$ blocks of data, where each block may have different replication factors. For this problem, we give an exact algorithm which runs in polynomial time when the skew, the difference in the number of replicas between the largest and smallest blocks of data, is constant., Comment: 64 pages, 9 figures. Preprint submission to Theoretical Computer Science

In this work, we consider the problem of placing replicas in a data center or storage area network, represented as a digraph, so as to lexico-minimize a previously proposed reliability measure which minimizes the impact of all failure events in the model in decreasing order of severity. Prior work focuses on the special case in which the digraph is an arborescence. In this work, we consider the broader class of multitrees: digraphs in which the subgraph induced by vertices reachable from a fixed node forms a tree. We parameterize multitrees by their number of “roots” (nodes with in-degree zero), and rule out membership in the class of fixed-parameter tractable problems (FPT) by showing that finding optimal replica placements in multitrees with 3 roots is NP-hard. On the positive side, we show that the problem of finding optimal replica placements in the class of untangled multitrees is FPT, as parameterized by the replication factor \(\rho \) and the number of roots k. Our approach combines dynamic programming (DP) with a novel tree decomposition to find an optimal placement of \(\rho \) replicas on the leaves of a multitree with n nodes and k roots in \(O(n^2\rho ^{2k+3})\) time.

In this paper, we design and analyze a simple, greedy algorithm for checking the linear and integer feasibility of a class of linear programs called Horn programs. This algorithm, which we term the “Lifting Algorithm”, runs in time O ( m ⋅ n 2 ) on a Horn system (Horn program) with m constraints and n variables. The Lifting Algorithm is a variant of the Stressing Algorithm which was proposed for checking the feasibility of Difference Constraint systems. Inasmuch as Horn constraints subsume difference constraints, and all known algorithms for the problem of checking feasibility of Difference Constraint Systems run in time Ω ( m ⋅ n ) , the running time of our algorithm is only a factor n worse than the best known running time for checking the feasibility of Difference Constraint Systems. Horn programs arise in a number of application areas including econometrics and program verification; consequently, their study is well-motivated. An important feature of our algorithm is that it uses only one operator, viz., addition. We also show that our algorithm can identify the linear and lattice point feasibility of Extended Horn Systems in O ( m ⋅ n 2 ) time.

Multi point relay (MPR) selection problem aims at improving energy efficiency by minimizing the number of relay nodes for a network wide broadcast operation in wireless ad hoc and sensor networks. If a relay node misses a broadcast packet, a large number of nodes reachable via this relay node may end up missing this broadcast packet. Therefore, improving broadcast reliability in an energy efficient way becomes an interesting task for those broadcast applications that benefit from an increased level of reliability. In this paper, we propose three incremental heuristics to select MPR nodes so as to provide 2-coverage to all 2-hop neighbors of a broadcasting node. Our heuristics are built on our former exact solution to 1-coverage MPR problem. Our simulation based evaluations show that the proposed heuristics can provide very good accuracy level for 2-coverage MPR problem.

In this paper, we consider a practical problem, called Minimum Forwarding Set Problem (MFSP), that emerges within the context of implementing (energy efficient) communication protocols for wireless ad hoc or sensor networks. For a given node v, MFSP asks for a minimum cardinality subset of 1-hop neighbors of v to cover v's 2-hop neighbors. MFSP problem is also known as multi-point relay (MPR) problem. It is shown to be an NP-complete problem for its general case that does not consider the coverage characteristics of wireless transmissions. In this paper, we present two polynomial time algorithms to solve the MFSP problem under disk coverage model for wireless transmissions. In our earlier work, we presented a polynomial time algorithm for this problem under unit disk coverage model. In the current work, we present several observations on the geometric characteristics of wireless transmissions under disk coverage model and build two alternative dynamic programming based solutions with different run time and space complexities to the problem. Disk coverage model is a more general model because it allows nodes to use arbitrary power levels for transmissions. As a result, the presented algorithms provide a more practical solution that can be used as a building block for energy efficient communication protocols designed for wireless ad hoc and sensor networks.

Motivated by applications in software programming, we consider the problem of covering a graph by a feasible labeling. Given an undirected graph G=(V,E), two positive integers k and t, and an alphabet @S, a feasible labeling is defined as an assignment of a set L"v@?@S to each vertex v@?V, such that (i) |L"v|@?k for all v@?V and (ii) each label @a@?@S is used no more than t times. An edge e={i,j} is said to be covered by a feasible labeling if L"i@?L"j 0@?. G is said to be covered if there exists a feasible labeling that covers each edge e@?E. In general, we show that the problem of deciding whether or not a tree can be covered is strongly NP-complete. For k=2, t=3, we characterize the trees that can be covered and provide a linear time algorithm for solving the decision problem. For fixed t, we present a strongly polynomial algorithm that solves the decision problem; if a tree can be covered, then a corresponding feasible labeling can be obtained in time polynomial in k and the size of the tree. For general graphs, we give a strongly polynomial algorithm to resolve the covering problem for k=2, t=3.

This paper studies the strong minimum energy topology design problem in wireless sensor networks. The objective is to assign transmission power to each sensor node in a directed wireless sensor network such that the induced directed graph topology is strongly connected and the total energy consumption is minimized. A topology is defined to be strongly connected if there exists a communication path between each ordered pair of sensor nodes. This topology design problem with sensor nodes defined on a plane is an NP-Complete problem. We first establish a lower bound on the optimal power consumption. We then provide three formulations for a more general problem defined on a general directed graph. All these formulations involve an exponential number of constraints. Second formulation is stronger than the first one. Further, using the second formulation, we lift the connectivity constraints to generate stronger set of constraints that yield the third formulation. These lifted cuts turn out to be extremely helpful in developing an effective branch-and-cut algorithm. A series of experiments are carried out to investigate the performance of the proposed branch-and-cut algorithm. These computational results over 580 instances demonstrate the effectiveness of our approach.

A cognitive radio node is a radio device capable of operating over multiple channels. As a result, a network consisting of one or more cognitive radio nodes can adapt to varying channel availability in its geographical region by dynamically changing the channel (or channels) nodes are using for communication. We investigate the problem of designing a fast deterministic algorithm for neighbor discovery in an undirected network consisting of one or more cognitive radio nodes when different nodes may have different subsets of channels available for communication at their location. We say that a neighbor discovery algorithm is fast if its time-complexity is polynomial in actual network-size. We prove that it is impossible to devise a fast algorithm to solve the neighbor discovery problem if nodes are neither size-aware nor collision-aware. When nodes are collision-aware, we present a fast algorithm for neighbor discovery with time-complexity of O(pmlogn), where p denotes the actual number of nodes present in the network, n denotes the size of space used for assigning labels to the nodes, and m denotes the number of channels over which nodes can operate. Our algorithm has the desirable property that every node knows when the neighbor discovery has completed and, moreover, all nodes terminate at the same time. When nodes are size-aware, we use a gossiping algorithm for a single-channel network with large labels that was proposed recently to derive a fast adaptive algorithm for neighbor discovery. We also investigate the neighbor discovery problem when the network may be directed. Finally, we describe a way to speed up neighbor discovery when nodes are collision-aware and channel availability sets of neighboring nodes do not vary significantly.

Network-wide broadcast (simply broadcast) is a frequently used operation in wireless ad hoc networks (WANETs). One promising practical approach for energy-efficient broadcast is to use localized algorithms to minimize the number of nodes involved in the propagation of the broadcast messages. In this context, the minimum forwarding set problem (MFSP) (also known as multipoint relay (MPR) problem) has received a considerable attention in the research community. Even though the general form of the problem is shown to be NP-complete, the complexity of the problem has not been known under the practical application context of ad hoc networks. In this paper, we present a polynomial time algorithm to solve the MFSP for wireless network under unit disk coverage model. We prove the existence of some geometrical properties for the problem and then propose a polynomial time algorithm to build an optimal solution based on these properties. To the best of our knowledge, our algorithm is the first polynomial time solution to the MFSP under the unit disk coverage model. We believe that the work presented in this paper will have an impact on the design and development of new algorithms for several wireless network applications including energy-efficient multicast, broadcast, and topology control protocols for WANETs and sensor networks.

Restoration of disrupted traffic is critical in today's high-speed self-healing telecommunication networks. A restoration scheme dynamically discovers alternate paths bypassing the failed component. This paper presents an (online) improved quasi-path restoration (IQPR) scheme. IQPR is derived from the two-commodity max-flow algorithm. The running time complexity of IQPR is O(|V|3). Therefore, IQPR is computationally more efficient and more scalable than path restoration (PR). IQPR is faster (in restoration speed) and less complex than PR, and more economical (in spare capacity requirement) than link restoration (LR). Thus, it provides a good alternative to PR when quick restoration of disrupted traffic is desired. The (offline) spare capacity planning problem deals with the allocation of spare capacity to each link in the network, such that the spare capacity requirement is minimized, while guaranteeing the desired level of restoration in the event of a link failure. The spare capacity allocation problems for LR, original quasi-path restoration (OQPR), IQPR, link-disjoint path restoration (LDPR) and PR are formulated as integer linear programming problems. Numerical results illustrate that the restoration schemes studied can be sorted from the least efficient to the most efficient (in the spare capacity requirement) in the following order: LR, OQPR, IQPR, LDPR and PR. The experimental analysis shows that network topology and demand patterns have a significant impact on the spare capacity savings offered by one scheme over the other. Merits and demerits of these schemes are also discussed.

A recently developed data separation/classification method, called isotonic separation, is applied to breast cancer prediction. Two breast cancer data sets, one with clean and sufficient data and the other with insufficient data, are used for the study and the results are compared against those of decision tree induction methods, linear programming discrimination methods, learning vector quantization, support vector machines, adaptive boosting, and other methods. The experiment results show that isotonic separation is a viable and useful tool for data classification in the medical domain.

A new model describing dependencies among system components as a directed graph is presented and used to solve a novel replica placement problem in data centers. A criterion for optimizing replica placements is formalized and explained. In this work, the optimization goal is to choose placements in which correlated failure events disable as few replicas as possible. A fast optimization algorithm is given for dependency models represented by trees. The main contribution of the paper is an $$On + \rho \log \rho $$On+i¾?logi¾? dynamic programming algorithm for placing $$\rho $$i¾? replicas on a tree with n vertices.

Data classification and prediction problems are prevalent in many domains. The need to predict to which class a particular data point belongs has been seen in areas such as medical diagnosis, credit rating, Web filtering, prediction, and stock rating. This has led to strong interest in developing systems that can accurately classify data and predict outcome. The classification is typically based on the feature values of objects being classified. Often, a form of ordering relation, defined by feature values, on the objects to be classified is known. For instance, the objects belonging to one class have larger (or smaller) feature values than do those in the other class. Exploiting this characteristic of isotonicity, we propose a data-classification method called isotonic separation based on linear programming, especially network programming. The paper also addresses an extension of the isotonic-separation method for continuous outcome prediction. Applications of the isotonic separation for discrete outcome prediction and its extension for continuous outcome prediction are shown to illustrate its applicability.

In the context of q-route flows in an undirected network with non-negative edge capacities, for integer values of q⩾2, we consider two problems of both theoretical and practical interest. The first problem focuses on investigating the existence and construction of a cut-tree. For q=2, we show that a cut-tree always exists and can be constructed in strongly polynomial time. However, for q⩾3, in general, a cut-tree does not exist and we establish this through a counter-example. The second problem addresses the issue of checking if a given matrix R is 2-realizable—that is, checking if there exists an undirected, simple network with non-negative edge capacities such that the non-diagonal elements of R are precisely the maximum 2-route flow values between corresponding pairs of nodes in the network. We provide a complete characterization of 2-realizable matrices and using this characterization, we prove that the problem of testing if a given matrix is 2-realizable is, in general, NP-complete.

Outcome prediction based on historical data has been of practical and theoretical interest in many disciplines. A common type of outcome prediction is binary or discrete outcome prediction, as found in medical diagnosis and firm bankruptcy prediction. The prediction problem studied in this paper is outcome time prediction, or prognosis. Prognosis in medicine refers to a prediction of probable outcome of a disease for a patient. Patient data used as the basis for disease prognosis are usually censored because some of the patients have not experienced the outcome of the disease at the time of prognosis. A mathematical-programming approach, called isotonic prediction, is developed for the purpose of such prognosis tasks. The proposed technique is different from well-known statistical survival analysis methods, such as Kaplan-Meier product-limit estimation and Cox's regression, in that it predicts individual patients' survival time frame. Two medical applications are presented to show the applicability of the proposed isotonic prediction technique.