The Experts below are selected from a list of 51186 Experts worldwide ranked by ideXlab platform
Adam Kasperski - One of the best experts on this subject based on the ideXlab platform.
-
Recoverable robust Spanning Tree problem under interval uncertainty representations
Journal of Combinatorial Optimization, 2016Co-Authors: Mikita Hradovich, Adam Kasperski, Paweł ZielińskiAbstract:This paper deals with the recoverable robust Spanning Tree problem under interval uncertainty representations. A strongly polynomial time, combinatorial algorithm for the recoverable Spanning Tree problem is first constructed. This problem generalizes the incremental Spanning Tree problem, previously discussed in literature. The algorithm built is then applied to solve the recoverable robust Spanning Tree problem, under the traditional interval uncertainty representation, in polynomial time. Moreover, the algorithm allows to obtain several approximation results for the recoverable robust Spanning Tree problem under the Bertsimas and Sim interval uncertainty representation and the interval uncertainty representation with a budget constraint.
-
Recoverable robust Spanning Tree problem under interval uncertainty representations
arXiv: Data Structures and Algorithms, 2016Co-Authors: Mikita Hradovich, Adam Kasperski, Paweł ZielińskiAbstract:This paper deals with the recoverable robust Spanning Tree problem under interval uncertainty representations. A polynomial time, combinatorial algorithm for the recoverable Spanning Tree problem is first constructed. This problem generalizes the incremental Spanning Tree problem, previously discussed in literature. The algorithm built is then applied to solve the recoverable robust Spanning Tree problem, under the traditional interval uncertainty representation, in polynomial time. Moreover, the algorithm allows to obtain, under some mild assumptions about the uncertainty intervals,several approximation results for the recoverable robust Spanning Tree problem under the Bertsimas and Sim interval uncertainty representation and the interval uncertainty representation with a budget constraint.
-
The minimum Spanning Tree problem with fuzzy costs
Fuzzy Optimization and Decision Making, 2008Co-Authors: Adam Janiak, Adam KasperskiAbstract:In this paper the minimum Spanning Tree problem in a given connected graph is considered. It is assumed that the edge costs are not precisely known and they are specified as fuzzy intervals. Possibility theory is applied to characterize the optimality of edges of the graph and to choose a Spanning Tree under fuzzy costs.
-
Minmax Regret Minimum Spanning Tree
Discrete Optimization with Interval Data, 1Co-Authors: Adam KasperskiAbstract:In this chapter we discuss Minmax Regret Minimum Spanning Tree. In this problem set E consists of all edges of a given undirected and connected graph G = (V,E). The set of feasible solutions Φ contains all Spanning Trees of G, that is the subsets of |V| − 1 edges that form acyclic subgraphs of G. For every edge e ∈ E there is an interval weight \([\underline{w}_e,\overline{w}_e]\) given. We wish to find a Spanning Tree that minimizes the maximal regret. A sample problem is shown in Figure 6.1. The Spanning Tree in bold is the optimal robust solution in the sample problem and it has the maximal regret equal to 8.
Luca Maria Gambardella - One of the best experts on this subject based on the ideXlab platform.
-
a branch and bound algorithm for the robust Spanning Tree problem with interval data
European Journal of Operational Research, 2002Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:The robust Spanning Tree problem is a variation, motivated by telecommunications applications, of the classic minimum Spanning Tree problem. In the robust Spanning Tree problem edge costs are interval numbers instead of fixed values. Interval numbers model uncertainty about the exact cost values. A robust Spanning Tree is a Spanning Tree whose total cost minimizes the maximum deviation from the optimal Spanning Tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and it is used to drive optimization. In this paper a branch and bound algorithm for the robust Spanning Tree problem is proposed. The method embeds some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted. Computational results obtained by the algorithm are finally presented. They highlight the efficiency of the approach we propose.
Alok Singh - One of the best experts on this subject based on the ideXlab platform.
-
Cutting-plane-based algorithms for two branch vertices related Spanning Tree problems
Optimization and Engineering, 2014Co-Authors: André Rossi, Alok Singh, Shyam SundarAbstract:A branch vertex is a vertex with degree larger than or equal to three. This paper addresses two Spanning Tree problems in an undirected, simple graph. The first one is to find a Spanning Tree that minimizes the number of branch vertices (MBV), and the second one is to find a Spanning Tree that minimizes the degree sum of branch vertices (MDS). These two problems arise in the design of wavelength-division networks (WDN), when the cost of equipments for enabling multicast communication is to be minimized. After investigating the relations of MBV and MDS with the problem of minimizing the number of leaves in a Spanning Tree, new formulations based on ILP are proposed for MBV and MDS, along with two cutting plane algorithms for addressing them. A repair function is also introduced for deriving feasible solutions from the candidate Trees returned at each iteration of the cutting plane algorithm, as well as a Tabu search procedure for further quality improvement. The resulting hybrid approach is shown to outperform pure ILP formulations and heuristic approaches published earlier.
-
New heuristics for two bounded-degree Spanning Tree problems
Information Sciences, 2012Co-Authors: Shyam Sundar, Alok Singh, André RossiAbstract:A vertex v of a connected graph G = (V, E) is called a branch vertex if its degree is greater than two. Pertaining to branch vertices, this paper studies two optimization problems having roots in the domain of optical networks. The first one, referred to as MBV, seeks a Spanning Tree T of G with the minimum number of branch vertices, whereas the second problem, referred to as MDS, seeks a Spanning Tree T of G with the minimum degree sum of branch vertices. Both MBV and MDS are NP-Hard. Two heuristics approaches are presented for each problem. The first approach is a problem specific heuristic, whereas the latter one is a hybrid ant-colony optimization algorithm. Computational results show the effectiveness of our proposed approaches.
-
a swarm intelligence approach to the quadratic minimum Spanning Tree problem
Information Sciences, 2010Co-Authors: Shyam Sundar, Alok SinghAbstract:The quadratic minimum Spanning Tree problem (Q-MST) is an extension of the minimum Spanning Tree problem (MST). In Q-MST, in addition to edge costs, costs are also associated with ordered pairs of distinct edges and one has to find a Spanning Tree that minimizes the sumtotal of the costs of individual edges present in the Spanning Tree and the costs of the ordered pairs containing only edges present in the Spanning Tree. Though MST can be solved in polynomial time, Q-MST is NP-Hard. In this paper we present an artificial bee colony (ABC) algorithm to solve Q-MST. The ABC algorithm is a new swarm intelligence approach inspired by intelligent foraging behavior of honey bees. Computational results show the effectiveness of our approach.
-
Improved heuristics for the bounded-diameter minimum Spanning Tree problem
Soft Computing, 2007Co-Authors: Alok Singh, Ashok K. GuptaAbstract:Given an undirected, connected, weighted graph and a positive integer k , the bounded-diameter minimum Spanning Tree (BDMST) problem seeks a Spanning Tree of the graph with smallest weight, among all Spanning Trees of the graph, which contain no path with more than k edges. In general, this problem is NP-Hard for 4 ≤ k
Roberto Montemanni - One of the best experts on this subject based on the ideXlab platform.
-
a branch and bound algorithm for the robust Spanning Tree problem with interval data
European Journal of Operational Research, 2002Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:The robust Spanning Tree problem is a variation, motivated by telecommunications applications, of the classic minimum Spanning Tree problem. In the robust Spanning Tree problem edge costs are interval numbers instead of fixed values. Interval numbers model uncertainty about the exact cost values. A robust Spanning Tree is a Spanning Tree whose total cost minimizes the maximum deviation from the optimal Spanning Tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and it is used to drive optimization. In this paper a branch and bound algorithm for the robust Spanning Tree problem is proposed. The method embeds some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted. Computational results obtained by the algorithm are finally presented. They highlight the efficiency of the approach we propose.
Shyam Sundar - One of the best experts on this subject based on the ideXlab platform.
-
Cutting-plane-based algorithms for two branch vertices related Spanning Tree problems
Optimization and Engineering, 2014Co-Authors: André Rossi, Alok Singh, Shyam SundarAbstract:A branch vertex is a vertex with degree larger than or equal to three. This paper addresses two Spanning Tree problems in an undirected, simple graph. The first one is to find a Spanning Tree that minimizes the number of branch vertices (MBV), and the second one is to find a Spanning Tree that minimizes the degree sum of branch vertices (MDS). These two problems arise in the design of wavelength-division networks (WDN), when the cost of equipments for enabling multicast communication is to be minimized. After investigating the relations of MBV and MDS with the problem of minimizing the number of leaves in a Spanning Tree, new formulations based on ILP are proposed for MBV and MDS, along with two cutting plane algorithms for addressing them. A repair function is also introduced for deriving feasible solutions from the candidate Trees returned at each iteration of the cutting plane algorithm, as well as a Tabu search procedure for further quality improvement. The resulting hybrid approach is shown to outperform pure ILP formulations and heuristic approaches published earlier.
-
New heuristics for two bounded-degree Spanning Tree problems
Information Sciences, 2012Co-Authors: Shyam Sundar, Alok Singh, André RossiAbstract:A vertex v of a connected graph G = (V, E) is called a branch vertex if its degree is greater than two. Pertaining to branch vertices, this paper studies two optimization problems having roots in the domain of optical networks. The first one, referred to as MBV, seeks a Spanning Tree T of G with the minimum number of branch vertices, whereas the second problem, referred to as MDS, seeks a Spanning Tree T of G with the minimum degree sum of branch vertices. Both MBV and MDS are NP-Hard. Two heuristics approaches are presented for each problem. The first approach is a problem specific heuristic, whereas the latter one is a hybrid ant-colony optimization algorithm. Computational results show the effectiveness of our proposed approaches.
-
a swarm intelligence approach to the quadratic minimum Spanning Tree problem
Information Sciences, 2010Co-Authors: Shyam Sundar, Alok SinghAbstract:The quadratic minimum Spanning Tree problem (Q-MST) is an extension of the minimum Spanning Tree problem (MST). In Q-MST, in addition to edge costs, costs are also associated with ordered pairs of distinct edges and one has to find a Spanning Tree that minimizes the sumtotal of the costs of individual edges present in the Spanning Tree and the costs of the ordered pairs containing only edges present in the Spanning Tree. Though MST can be solved in polynomial time, Q-MST is NP-Hard. In this paper we present an artificial bee colony (ABC) algorithm to solve Q-MST. The ABC algorithm is a new swarm intelligence approach inspired by intelligent foraging behavior of honey bees. Computational results show the effectiveness of our approach.
