排序方式: 共有48条查询结果,搜索用时 192 毫秒
1.
Network coding is a generalization of conventional routing methods that allows a network node to code information flows before forwarding them. While it has been theoretically proved that network coding can achieve maximum network throughput, theoretical results usually do not consider the stochastic nature in information processing and transmission, especially when the capacity of each arc becomes stochastic due to failure, attacks, or maintenance. Hence, the reliability measurement of network coding becomes an important issue to evaluate the performance of the network under various system settings. In this paper, we present analytical expressions to measure the reliability of multicast communications in coded networks, where network coding is most promising. We define the probability that a multicast rate can be transmitted through a coded packet network under a total transmission cost constraint as the reliability metric. To do this, we first introduce an exact mathematical formulation to construct multicast connections over coded packet networks under a limited transmission cost. We then propose an algorithm based on minimal paths to calculate the reliability measurement of multicast connections and analyze the complexity of the algorithm. Our results show that the reliability of multicast routing with network coding improved significantly compared to the case of multicast routing without network coding. 相似文献
2.
With the growth of the Internet, Internet Service Providers (ISPs) try to meet the increasing traffic demand with new technology and improved utilization of existing resources. Routing of data packets can affect network utilization. Packets are sent along network paths from source to destination following a protocol. Open Shortest Path First (OSPF) is the most commonly used intra-domain Internet routing protocol (IRP). Traffic flow is routed along shortest paths, splitting flow at nodes with several outgoing links on a shortest path to the destination IP address. Link weights are assigned by the network operator. A path length is the sum of the weights of the links in the path. The OSPF weight setting (OSPFWS) problem seeks a set of weights that optimizes network performance. We study the problem of optimizing OSPF weights, given a set of projected demands, with the objective of minimizing network congestion. The weight assignment problem is NP-hard. We present a genetic algorithm (GA) to solve the OSPFWS problem. We compare our results with the best known and commonly used heuristics for OSPF weight setting, as well as with a lower bound of the optimal multi-commodity flow routing, which is a linear programming relaxation of the OSPFWS problem. Computational experiments are made on the AT&T Worldnet backbone with projected demands, and on twelve instances of synthetic networks. 相似文献
3.
For a Boolean function
given by a Boolean formula (or a binary circuit) S we discuss the problem of building a Boolean formula (binary circuit) of minimal size, which computes the function g equivalent to
, or -equivalent to
, i.e.,
. In this paper we prove that if P NP then this problem can not be approximated with a good approximation ratio by a polynomial time algorithm. 相似文献
4.
The wireless network jamming problem 总被引:1,自引:0,他引:1
Clayton W. Commander Panos M. Pardalos Valeriy Ryabchenko Stan Uryasev Grigoriy Zrazhevsky 《Journal of Combinatorial Optimization》2007,14(4):481-498
In adversarial environments, disabling the communication capabilities of the enemy is a high priority. We introduce the problem
of determining the optimal number and locations for a set of jamming devices in order to neutralize a wireless communication
network. This problem is known as the wireless network jamming problem. We develop several mathematical programming formulations based on covering the communication nodes and limiting the connectivity
index of the nodes. Two case studies are presented comparing the formulations with the addition of various percentile constraints.
Finally, directions of further research are addressed. 相似文献
5.
In morphological image processing and analysis, a template or structuringelement is applied to an image. Often savings in computation time and abetter fit to the given computer architecture can be achieved by using thetechnique of template decomposition. Researchers have written a multitude ofpapers on finding such decompositions for special classes of templates.Justifying recent integer programming approaches to the morphologicaltemplate decomposition problem in its general form, this paper proves theNP-completeness of this problem. 相似文献
6.
7.
8.
Stanislav?BusyginEmail author Oleg?A.?Prokopyev Panos?M.?Pardalos 《Journal of Combinatorial Optimization》2005,10(1):7-21
Biclustering consists in simultaneous partitioning of the set of samples and the set of their attributes (features) into subsets (classes). Samples and features classified together are supposed to have a high relevance to each other which can be observed by intensity of their expressions. We define the notion of consistency for biclustering using interrelation between centroids of sample and feature classes. We prove that consistent biclustering implies separability of the classes by convex cones. While previous works on biclustering concentrated on unsupervised learning and did not consider employing a training set, whose classification is given, we propose a model for supervised biclustering, whose consistency is achieved by feature selection. The developed model involves solution of a fractional 0–1 programming problem. Preliminary computational results on microarray data mining problems are reported.This research work was partially supported by NSF, NIH and AirForce grants. 相似文献
9.
D. V. Gribanov D. S. Malyshev P. M. Pardalos S. I. Veselov 《Journal of Combinatorial Optimization》2018,36(4):1128-1144
This paper studies a new version of the location problem called the mixed center location problem. Let P be a set of n points in the plane. We first consider the mixed 2-center problem, where one of the centers must be in P, and we solve it in \(O(n^2\log n)\) time. Second, we consider the mixed k-center problem, where m of the centers are in P, and we solve it in \(O(n^{m+O(\sqrt{k-m})})\) time. Motivated by two practical constraints, we propose two variations of the problem. Third, we present a 2-approximation algorithm and three heuristics solving the mixed k-center problem (\(k>2\)). 相似文献
10.