Support vector regression based modeling of pier scour using field data

This paper investigates the potential of support vector machines based regression approach to model the local scour around bridge piers using field data. A dataset of consisting of 232 pier scour measurements taken from BSDMS were used for this analysis. Results obtained by using radial basis function and polynomial kernel based Support vector regression were compared with four empirical relation as well as with a backpropagation neural network and generalized regression neural network. A total of 154 data were used for training different algorithms whereas remaining 78 data were used to test the created model. A coefficient of determination value of 0.897 (root mean square error=0.356) was achieved by radial basis kernel based support vector regression in comparison to 0.880 and 0.835 (root mean square error=0.388 and 0.438) by backpropagation neural and generalized regression neural network. Comparisons of results with four predictive equations suggest an improved performance by support vector regression. Results with dimensionless data using all three algorithms suggest a better performance by dimensional data with this dataset. Sensitivity analysis suggests the importance of depth of flow and pier width in predicting the scour depth when using support vector regression based modeling approach.     

基于模糊层次分析法的计算机网络安全评价

根据计算机网络的特点及网络安全涉及的因素,建立计算机网络安全评价的层次结构模型,运用基于三角模糊数的模糊层次分析法实现对网络安全的综合量化评价。实例的计算结果表明模糊层次分析法适用于定性判断的量化综合,它为计算机网络安全评价提供了一种探索性方法。     

Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design

Answering an open question published in Operations Research (54, 73–91, 2006) in the area of network design and logistic optimization, we present the first constant-factor approximation algorithms for the problem combining facility location and cable installation in which capacity constraints are imposed on both facilities and cables. We study the problem of designing a minimum cost network to serve client demands by opening facilities for service provision and installing cables for service shipment. Both facilities and cables have capacity constraints and incur buy-at-bulk costs. This Max SNP-hard problem arises in diverse applications and is shown in this paper to admit a combinatorial 19.84-approximation algorithm of cubic running time. This is achieved by an integration of primal-dual schema, Lagrangian relaxation, demand clustering and bi-factor approximation. Our techniques extend to several variants of this problem, which include those with unsplitable demands or requiring network connectivity, and provide constant-factor approximate algorithms in strongly polynomial time. X. Chen is Visiting Fellow, University of Warwick.     

An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4 ^k n ³) time algorithm for this problem, significantly improving the previous algorithm of time for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n). A preliminary version of this paper was presented at The 10th Workshop on Algorithms and Data Structures (WADS 2007). This work was supported in part by the National Science Foundation under the Grants CCR-0311590 and CCF-0430683.     

Non-Cooperative Tree Creation

In this paper we consider the connection game, a simple network design game with independent selfish agents that was introduced by Anshelevich et al. (Proc. 35th Ann. ACM Symp. Theo. Comp. (STOC), pp. 511–520, 2003). Our study concerns an important subclass of tree games, in which every feasible network is guaranteed to be connected. It generalizes the class of single-source games considered by Anshelevich et al. We focus on the existence, quality, and computability of pure-strategy exact and approximate Nash equilibria. For tree connection games, in which every player holds two terminals, we show that there is a Nash equilibrium as cheap as the optimum network. In contrast, for single-source games, in which every player has at most three terminals, the price of stability is at least k−2, and it is -complete to decide the existence of a Nash equilibrium. Hence, we propose polynomial time algorithms for computing approximate Nash equilibria, which provide relaxed stability and cost efficiency guarantees. For the case of two terminals per player, there is an algorithm to find a (2+ε,1.55)-approximate Nash equilibrium. It can be generalized to an algorithm to find a (3.1+ε,1.55)-approximate Nash equilibrium for general tree connection games. This improves the guarantee of the only previous algorithm for the problem, which returns a (4.65+ε,1.55)-approximate Nash equilibrium. Tightness results for the analysis of all algorithms are derived. Our algorithms use a novel iteration technique for trees that might be of independent interest. This work has appeared in part as an extended abstract at the 31st Symposium on Mathematical Foundations of Computer Science (MFCS 2006) and the 17th International Symposium on Algorithms and Computation (ISAAC 2006). Supported by DFG Research Training Group 1042 “Explorative Analysis and Visualization of Large Information Spaces”.     

The Network as a Storage Device: Dynamic Routing with Bounded Buffers

We study dynamic routing in store-and-forward packet networks where each network link has bounded buffer capacity for receiving incoming packets and is capable of transmitting a fixed number of packets per unit of time. At any moment in time, packets are injected at various network nodes with each packet specifying its destination node. The goal is to maximize the throughput, defined as the number of packets delivered to their destinations. In this paper, we make some progress on throughput maximization in various network topologies. Let n and m denote the number of nodes and links in the network, respectively. For line networks, we show that Nearest-to-Go (NTG), a natural distributed greedy algorithm, is -competitive, essentially matching a known lower bound on the performance of any greedy algorithm. We also show that if we allow the online routing algorithm to make centralized decisions, there is a randomized polylog(n)-competitive algorithm for line networks as well as for rooted tree networks, where each packet is destined for the root of the tree. For grid graphs, we show that NTG has a competitive ratio of while no greedy algorithm can achieve a ratio better than . Finally, for arbitrary network topologies, we show that NTG is -competitive, improving upon an earlier bound of O(mn). An extended abstract appeared in the Proceedings of the 8th Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005, Berkeley, CA, USA, pp. 1–13, Lecture Notes in Computer Science, vol. 1741, Springer, Berlin. S. Angelov is supported in part by NSF Career Award CCR-0093117, NSF Award ITR 0205456 and NIGMS Award 1-P20-GM-6912-1. S. Khanna is supported in part by an NSF Career Award CCR-0093117, NSF Award CCF-0429836, and a US-Israel Binational Science Foundation Grant. K. Kunal is supported in part by an NSF Career Award CCR-0093117 and NSF Award CCF-0429836.     

Multiresolution-based bilinear recurrent neural network

A multiresolution-based bilinear recurrent neural network (MBLRNN) is proposed in this paper. The proposed MBLRNN is based on the BLRNN that has robust abilities in modeling and predicting time series. The learning process is further improved by using a multiresolution-based learning algorithm for training the BLRNN so as to make it more robust for the prediction of time series data. The proposed MBLRNN is applied to the problems of network traffic prediction and electric load forecasting. Experiments and results on both practical problems show that the proposed MBLRNN outperforms both the traditional multilayer perceptron type neural network (MLPNN) and the BLRNN in the prediction accuracy.

Covering a line segment with variable radius discs

The paper addresses the problem of locating sensors with a circular field of view so that a given line segment is under full surveillance, which is termed as the disc covering problem on a line. The cost of each sensor includes a fixed component f, and a variable component that is a convex function of the diameter of the field-of-view area. When only one type of sensor or, in general, one type of disc, is available, then a simple polynomial algorithm solves the problem. When there are different types of sensors, the problem becomes hard. A branch-and-bound algorithm as well as an efficient heuristic are developed for the special case in which the variable cost component of each sensor is proportional to the square of the measure of the field-of-view area. The heuristic very often obtains the optimal solution as shown in extensive computational testing.     

A tabu-search based heuristic for the hub covering problem over incomplete hub networks

Hub location problems deal with finding the location of hub facilities and with the allocation of demand nodes to these located hub facilities. In this paper, we study the single allocation hub covering problem over incomplete hub networks and propose an integer programming formulation to this end. The aim of our model is to find the location of hubs, the hub links to be established between the located hubs, and the allocation of non-hub nodes to the located hub nodes such that the travel time between any origin–destination pair is within a given time bound. We present an efficient heuristic based on tabu search and test the performance of our heuristic on the CAB data set and on the Turkish network.