The Experts below are selected from a list of 53109 Experts worldwide ranked by ideXlab platform
Luca Maria Gambardella - One of the best experts on this subject based on the ideXlab platform.
-
a note on the article a robust branch and cut approach for the minimum energy symmetric network Connectivity Problem
Omega-international Journal of Management Science, 2012Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:Abstract In the paper Li et al. [A robust branch-and-cut approach for the minimum-energy symmetric network Connectivity Problem. Omega 2012;40:210–7] it is claimed that a theoretical result appeared in Montemanni and Gambardella [Exact algorithms for the minimum power symmetric Connectivity Problem in wireless networks. Computers and Operations Research 2005;32:2891–904] is wrong. In this note we show that the original result is correct, and that the counter-example used to prove the wrongness of the original result is incorrect.
-
exact algorithms for the minimum power symmetric Connectivity Problem in wireless networks
Computers & Operations Research, 2005Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:In this paper we consider the Problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized.Two mixed integer programming formulations are presented together with some new valid inequalities for the polytopes associated. A preprocessing technique and two exact algorithms based on the formulations previously introduced are also proposed.Comprehensive computational results, which show the effectiveness of the new valid inequalities and of the preprocessing technique are presented. The experiments also show that the exact approaches we propose outperform more complex methods recently appeared in the literature.
-
swarm approach for a Connectivity Problem in wireless networks
IEEE Swarm Intelligence Symposium, 2005Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:We consider the Problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized. Since no central authority (with a global vision of the network) exists in wireless networks, only distributed, swarm approaches can be used. We present a distributed protocol that embeds well-known centralized techniques for power minimization, here used in a local, distributed fashion. The result can be seen as a complex adaptive system (the global network), where global optimization emerges as a result of the behavior of local nodes, each one carrying out a myopic, local optimization. Computational results, proving the effectiveness of the new protocol, are finally presented.
-
power aware distributed protocol for a Connectivity Problem in wireless sensor networks
Lecture Notes in Computer Science, 2005Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:We consider the Problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized. We present a distributed protocol, obtained by extending a Connectivity protocol recently appeared in the literature. The new extended protocol is obtained by using in a local, distributed fashion, well-known centralized techniques for power minimization. The result is a self-organization framework where a set of rules, implemented locally at each node, guarantees global properties, i.e. Connectivity and power expenditure minimization. Preliminary computational results are finally presented. They show that the new extended protocol guarantees a substantial saving in the total transmission power.
-
minimum power symmetric Connectivity Problem in wireless networks a new approach
Mobile and Wireless Communication Networks, 2004Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:We consider the Problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes of the network are connected by bidirectional links and the total power consumption is minimized.
Roberto Montemanni - One of the best experts on this subject based on the ideXlab platform.
-
a note on the article a robust branch and cut approach for the minimum energy symmetric network Connectivity Problem
Omega-international Journal of Management Science, 2012Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:Abstract In the paper Li et al. [A robust branch-and-cut approach for the minimum-energy symmetric network Connectivity Problem. Omega 2012;40:210–7] it is claimed that a theoretical result appeared in Montemanni and Gambardella [Exact algorithms for the minimum power symmetric Connectivity Problem in wireless networks. Computers and Operations Research 2005;32:2891–904] is wrong. In this note we show that the original result is correct, and that the counter-example used to prove the wrongness of the original result is incorrect.
-
exact algorithms for the minimum power symmetric Connectivity Problem in wireless networks
Computers & Operations Research, 2005Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:In this paper we consider the Problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized.Two mixed integer programming formulations are presented together with some new valid inequalities for the polytopes associated. A preprocessing technique and two exact algorithms based on the formulations previously introduced are also proposed.Comprehensive computational results, which show the effectiveness of the new valid inequalities and of the preprocessing technique are presented. The experiments also show that the exact approaches we propose outperform more complex methods recently appeared in the literature.
-
swarm approach for a Connectivity Problem in wireless networks
IEEE Swarm Intelligence Symposium, 2005Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:We consider the Problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized. Since no central authority (with a global vision of the network) exists in wireless networks, only distributed, swarm approaches can be used. We present a distributed protocol that embeds well-known centralized techniques for power minimization, here used in a local, distributed fashion. The result can be seen as a complex adaptive system (the global network), where global optimization emerges as a result of the behavior of local nodes, each one carrying out a myopic, local optimization. Computational results, proving the effectiveness of the new protocol, are finally presented.
-
power aware distributed protocol for a Connectivity Problem in wireless sensor networks
Lecture Notes in Computer Science, 2005Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:We consider the Problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized. We present a distributed protocol, obtained by extending a Connectivity protocol recently appeared in the literature. The new extended protocol is obtained by using in a local, distributed fashion, well-known centralized techniques for power minimization. The result is a self-organization framework where a set of rules, implemented locally at each node, guarantees global properties, i.e. Connectivity and power expenditure minimization. Preliminary computational results are finally presented. They show that the new extended protocol guarantees a substantial saving in the total transmission power.
-
minimum power symmetric Connectivity Problem in wireless networks a new approach
Mobile and Wireless Communication Networks, 2004Co-Authors: Roberto Montemanni, Luca Maria GambardellaAbstract:We consider the Problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes of the network are connected by bidirectional links and the total power consumption is minimized.
Tomoyuki Yamakami - One of the best experts on this subject based on the ideXlab platform.
-
state complexity characterizations of parameterized degree bounded graph Connectivity sub linear space computation and the linear space hypothesis
Theoretical Computer Science, 2019Co-Authors: Tomoyuki YamakamiAbstract:Abstract The linear space hypothesis is a practical working hypothesis, which originally states the insolvability of a restricted 2CNF Boolean formula satisfiability Problem parameterized by the number of Boolean variables. From this hypothesis, it naturally follows that the degree-3 directed graph Connectivity Problem (3DSTCON) parameterized by the number of vertices in a given graph cannot belong to PsubLIN, composed of all parameterized decision Problems computable by polynomial-time, sub-linear-space deterministic Turing machines. This hypothesis immediately implies L≠NL and it was used as a solid foundation to obtain new lower bounds on the computational complexity of various NL search and NL optimization Problems. The state complexity of transformation refers to the cost of converting one type of finite automata to another type, where the cost is measured in terms of the increase of the number of inner states of the converted automata from that of the original automata. We relate the linear space hypothesis to the state complexity of transforming restricted 2-way nondeterministic finite automata to computationally equivalent 2-way alternating finite automata having narrow computation graphs. For this purpose, we present state complexity characterizations of 3DSTCON and PsubLIN. We further characterize a nonuniform version of the linear space hypothesis in terms of the state complexity of transformation.
-
state complexity characterizations of parameterized degree bounded graph Connectivity sub linear space computation and the linear space hypothesis
arXiv: Computational Complexity, 2018Co-Authors: Tomoyuki YamakamiAbstract:The linear space hypothesis is a practical working hypothesis, which originally states the insolvability of a restricted 2CNF Boolean formula satisfiability Problem parameterized by the number of Boolean variables. From this hypothesis, it naturally follows that the degree-3 directed graph Connectivity Problem (3DSTCON) parameterized by the number of vertices in a given graph cannot belong to PsubLIN, composed of all parameterized decision Problems computable by polynomial-time, sub-linear-space deterministic Turing machines. This hypothesis immediately implies L$\neq$NL and it was used as a solid foundation to obtain new lower bounds on the computational complexity of various NL search and NL optimization Problems. The state complexity of transformation refers to the cost of converting one type of finite automata to another type, where the cost is measured in terms of the increase of the number of inner states of the converted automata from that of the original automata. We relate the linear space hypothesis to the state complexity of transforming restricted 2-way nondeterministic finite automata to computationally equivalent 2-way alternating finite automata having narrow computation graphs. For this purpose, we present state complexity characterizations of 3DSTCON and PsubLIN. We further characterize a nonuniform version of the linear space hypothesis in terms of the state complexity of transformation.
-
state complexity characterizations of parameterized degree bounded graph Connectivity sub linear space computation and the linear space hypothesis
Descriptional Complexity of Formal Systems, 2018Co-Authors: Tomoyuki YamakamiAbstract:The linear space hypothesis is a practical working hypothesis, which originally states the insolvability of a restricted 2CNF Boolean formula satisfiability Problem parameterized by the number of Boolean variables. From this hypothesis, it follows that the degree-3 directed graph Connectivity Problem (3DSTCON) parameterized by the number of vertices in a given graph cannot belong to PsubLIN, composed of decision Problems computable by polynomial-time, sub-linear-space deterministic Turing machines. This hypothesis immediately implies L\(\ne \)NL and it was used as a solid foundation to obtain new lower bounds on the computational complexity of various NL search and NL optimization Problems. The state complexity of transformation refers to the cost of converting one type of finite automata to another type, where the cost is measured in terms of the increase of the number of inner states of the converted automata from that of the original automata. We relate the linear space hypothesis to the state complexity of transforming restricted 2-way nondeterministic finite automata to computationally equivalent 2-way alternating finite automata having narrow computation graphs. For this purpose, we present state complexity characterizations of 3DSTCON and PsubLIN. We further characterize a non-uniform version of the linear space hypothesis in terms of the state complexity of transformation.
-
parameterized graph Connectivity and polynomial time sub linear space short reductions
International Workshop on Reachability Problems, 2017Co-Authors: Tomoyuki YamakamiAbstract:We are focused on the solvability/insolvability of the directed s-t Connectivity Problem (DSTCON) parameterized by suitable size parameters m(x) on multi-tape deterministic Turing machines working on instances x to DSTCON by consuming simultaneously polynomial time and sub-linear space, where the informal term “sub-linear” refers to a function of the form \(m(x)^{\varepsilon } \ell (|x|)\) on instances x for a certain absolute constant \(\varepsilon \in (0,1)\) and a certain polylogarithmic function \(\ell (n)\). As natural size parameters, we take the numbers \(m_{ver}(x)\) of vertices and of edges \(m_{edg}(x)\) of a graph cited in x. Parameterized Problems solvable simultaneously in polynomial time using sub-linear space form a complexity class \(\mathrm {PsubLIN}\) and it is unknown whether \(\mathrm {DSTCON}\) parameterized by \(m_{ver}\) belongs to \(\mathrm {PsubLIN}\). Toward this open question, we wish to investigate the relative complexity of \(\mathrm {DSTCON}\) and its natural variants and classify them according to a restricted form of many-one and Turing reductions, known as “short reductions,” which preserve the polynomial-time sub-linear-space complexity. As variants of \(\mathrm {DSTCON}\), we consider the breadth-first search Problem, the minimal path Problem, and the topological sorting Problem. Certain restricted forms of them fall into \(\mathrm {PsubLIN}\). We also consider a stronger version of “sub-linear,” called “hypo-linear.” Additionally, we refer to a relationship to a practical working hypothesis known as the linear space hypothesis.
David P Williamson - One of the best experts on this subject based on the ideXlab platform.
-
a primal dual schema based approximation algorithm for the element Connectivity Problem
Journal of Algorithms, 2002Co-Authors: Kamal Jain, Ion I Mandoiu, Vijay V Vazirani, David P WilliamsonAbstract:The element Connectivity Problem falls in the category of survivable network design Problems-it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edge version is by now well understood from the view-point of approximation algorithms [Williamson et al., Combinatorica 15 (1995) 435-454; Goemans et al., in: SODA '94, 223-232; Jain, Combinatorica 21 (2001) 39-60], but very little is known about the vertex version. In our Problem, vertices are partitioned into two sets: terminals and nonterminals. Only edges and nonterminals can fail--we refer to them as elements--and only pairs of terminals have Connectivity requirements, specifying the number of element-disjoint paths required. Our algorithm achieves an approximation guarantee of factor 2Hk, where k is the largest requirement and Hn = 1 + ½ +... + 1/n. Besides providing possible insights for solving the vertex-disjoint paths version, the element Connectivity Problem is of independent interest, since it models a realistic situation.
-
an iterative rounding 2 approximation algorithm for the element Connectivity Problem
International Conference on Cluster Computing, 2001Co-Authors: L Fleischer, Kamal Jain, David P WilliamsonAbstract:In the survivable network design Problem (SNDP), given an undirected graph and values r/sub ij/ for each pair of vertices i and j, we attempt to find a minimum-cost subgraph such that there are r/sub ij/ disjoint paths between vertices i and j. In the edge connected version of this Problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the Problem (VC-SNDP), the paths must be vertex disjoint. K. Jain et al. (1999) propose a version of the Problem intermediate in difficulty to these two, called the element Connectivity Problem (ELC-SNDP, or ELC). These variants of SNDP are all known to be NP-hard. The best known approximation algorithm for the EC-SNDP has performance guarantee of 2 (K. Jain, 2001), and iteratively rounds solutions to a linear programming relaxation of the Problem. ELC has a primal-dual O (log k) approximation algorithm, where k=max/sub i,j/ r/sub ij/. VC-SNDP is not known to have a non-trivial approximation algorithm; however, recently L. Fleischer (2001) has shown how to extend the technique of K. Jain ( 2001) to give a 2-approximation algorithm in the case that r/sub ij//spl isin/{0, 1, 2}. She also shows that the same techniques will not work for VC-SNDP for more general values of r/sub ij/. The authors show that these techniques can be extended to a 2-approximation algorithm for ELC. This gives the first constant approximation algorithm for a general survivable network design Problem which allows node failures.
-
a primal dual schema based approximation algorithm for the element Connectivity Problem
Symposium on Discrete Algorithms, 1999Co-Authors: Kamal Jain, Ion I Mandoiu, Vijay V Vazirani, David P WilliamsonAbstract:AbstractThe element Connectivity Problem fallsin the category of survivable network design Problems– it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edgeversion is by now well understood from the view-point of approximation algorithms [17, 5, 8],but very little is known about the vertex version. In our Problem, vertices are partitioned intotwo sets: terminals and non-terminals. Only edges and non-terminals can fail – we refer tothem as elements – and only pairs of terminals have Connectivity requirements, specifying thenumber of element-disjoint paths required. Our algorithm achieves an approximation guaranteeof factor 2H k , where k is the largest requirement and H n = 1+ 12 +···+ 1n . Besides providingpossible insights for solving the vertex-disjoint paths version, the element Connectivity Problemis of independent interest, since it models a realistic situation. 1 Introduction Given an undirected graph G = (V,E) with non-negative costs c e
Jiazhen Huo - One of the best experts on this subject based on the ideXlab platform.
-
a robust branch and cut approach for the minimum energy symmetric network Connectivity Problem
Omega-international Journal of Management Science, 2012Co-Authors: Y P Aneja, Jiazhen HuoAbstract:Abstract This paper considers the minimum-energy symmetric network Connectivity Problem (MESNC) in wireless sensor networks. The aim of the MESNC is to assign transmission power to each sensor node such that the resulting network, using only bidirectional links, is connected and the total energy consumption is minimized. We first present two new models of this Problem and then propose new branch-and-cut algorithms. Based on an existing formulation, we present the first model by introducing additional constraints. These additional constraints allow us to relax certain binary variables to continuous ones and thus to reduce significantly the number of binary variables. Our second model strengthens the first one by adding an exponential number of lifted directed-Connectivity constraints. We present two branch-and-cut procedures based on these proposed improvements. The computational results are reported and show that our approaches, using the proposed formulations, can efficiently solve instances with up to 120 nodes, which significantly improve our ability to solve much larger instances in comparison with other exact algorithms in the literature.