网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

Steiner problem in Halin networks

The Steiner problem in networks is concerned with the determination of a minimum cost subnetwork connecting some (not necessarily all) vertices of an underlying network. The decision version of the Steiner problem is known to be NP-complete. However, if the underlying network is outerplanar or series-parallel, linear time algorithms have been developed.In this paper a linear time algorithm for the Steiner problem in Halin networks is presented. This result provides another example where the recursive structure of the underlying network leads to an efficient algorithm. Furthermore, the result is of interest from the network design point of view, since Halin networks are nontrivial generalizations of tree and ring networks.     

The newsvendor problem with unknown distribution

Newsvendor theory assumes that the decision-maker faces a knowndistribution. But in real-life situations, demand distribution is not alwaysknown. In the experimental study which this paper presents, half of theparticipants assuming the newsvendor role were unaware of the underlying demanddistribution, while the other half knew the demand distribution. Participantshad to decide how many papers to order each day (for 100 days). The experimentalfindings indicate that subjects who know the demand distribution behavedifferently to those who do not. However, interestingly enough, knowing thedemand distribution does not necessarily lead the subject closer to the optimalsolution or improve profits. It was found that supply surplus at a certainperiod strongly affects the order quantity towards the following period, despitethe knowledge of the demand distribution.     

Generalized steiner problem in series-parallel networks

The generalized Steiner problem (GSP) is concerned with the determination of a minimum cost subnetwork of a given network where some (not necessarily all) vertices satisfy certain pairwise (vertex or edge) connectivity requirements. The GSP has applications to the design of water and electricity supply networks, communication networks and other large-scale systems where connectivity requirements ensure the communication between the selected vertices when some vertices and/or edges can become inoperational due to scheduled maintenance, error, or overload. The GSP is known to be NP-complete. In this paper we show that if the subnetwork is required to be respectively biconnected and edge-biconnected, and the underlying network is series-parallel, both problems can be solved in linear time.     

Generalized steiner problem in outerplanar networks

The generalized Steiner problem (GSP) is concerned with the determination of a minimum cost subnetwork of a given network where some (not necessarily all) vertices satisfy certain pairwise (vertex or edge) connectivity requirements.The GSP has applications to the design of water and electricity supply networks, communication networks and other large-scale systems where connectivity requirements ensure the communication between the selected vertices when some vertices and/or edges can become inoperational due to scheduled maintenance, error, or overload.The GSP is known to beNP-complete. In this paper we show that if the subnetwork is required to be biconnected or respectively edge-biconnected, and the underlying network is outerplanar, the GSP can be solved in linear time.     

The capacitated distribution and waste disposal problem

We study the problem of the simultaneous design of a distribution network with plants and waste disposal units, and the coordination of product flows and waste flows within this network. The objective is to minimize the sum of fixed costs for opening plants and waste disposal units, and variable costs related to product and waste flows. The problem is complicated by (i) capacity constraints on plants and waste disposal units, (ii) service requirements (i.e. production must cover total demand) and (iii) waste, arising from production, to be disposed of at waste disposal units. We discuss alternative mathematical model formulations for the two-level distribution and waste disposal problem with capacity constraints. Lower bounding and upper bounding procedures are analyzed. The bounds are shown to be quite effective when embedded in a standard branch and bound algorithm. Finally, the results of a computational study are reported.     

Minimum power multicasting problem in wireless networks

In this paper we deal with the minimum power multicasting (MPM) problem in wireless ad-hoc networks. By using an appropriate choice of the decision variables and by exploiting the topological properties of the problem, we are able to define an original formulation based on a Set Covering model. Moreover, we propose for its solution two exact procedures that include a preprocessing technique that reduces the huge number of the model’s constraints. We also report some experimental results carried out on a set of randomly generated test problems.     

The multicriteria p-facility median location problem on networks

In this paper we discuss the multicriteria p-facility median location problem on networks with positive and negative weights. We assume that the demand is located at the nodes and can be different for each criterion under consideration. The goal is to obtain the set of Pareto-optimal locations in the graph and the corresponding set of non-dominated objective values. To that end, we first characterize the linearity domains of the distance functions on the graph and compute the image of each linearity domain in the objective space. The lower envelope of a transformation of all these images then gives us the set of all non-dominated points in the objective space and its preimage corresponds to the set of all Pareto-optimal solutions on the graph. For the bicriteria 2-facility case we present a low order polynomial time algorithm. Also for the general case we propose an efficient algorithm, which is polynomial if the number of facilities and criteria is fixed.     

Frequency assignment problem in networks with limited spectrum

Central European Journal of Operations Research - The frequency assignment problem (FAP) asks for assigning frequencies (channels) in a wireless network from the available radio spectrum to the...     

树状网络上的Web代理服务器最优放置问题

一般网络上Web代理服务器(Web proxy)最优放置问题是一个NP困难问题.此文讨论树状网络上的最优放置问题,改进了已有结果,得到了一个时间复杂度为O(nhk)的多项式时间算法,这里n为网络结点数,h为树的高度,而k为要放置的代理服务器个数.     

The problem of averaging random structures in terms of distribution functions

A new approach to solving averaging problems for micro-inhomogeneous continua, based on a restatement of the problem in terms of distribution functions, is described. Problems having a variational structure are considered. It is shown that, in terms of distribution functions, they reduce to the problem of minimizing a linear functional, having the meaning of the expectation value of the energy, in a set of distribution functions which is distinguished by an infinite number of linear constants. These constraints express certain matching conditions and contain multipoint distribution functions of the random characteristics of the medium. The constraints form an unlinked chain, the break of which at the n-th step contains only n-point distribution functions. In view of this, a sequence of approximate problems arises.     

Thep-facility ordered median problem on networks

In this paper we deal with the ordered median problem: a family of location problems that allows us to deal with a large number of real situations which does not fit into the standard models of location analysis. Moreover, this family includes as particular instances many of the classical location models. Here, we analyze thep-facility version of this problem on networks and our goal is to study the structure of the set of candidate points to be optimal solutions. The research of the authors is partially financed by Spanish research grants BFM2001-2378, BFM2001-4028, BFM2004-0909 and HA2003-0121.     

Discrete sensor placement problems in distribution networks

We consider the problem of placing sensors in a network to detect and identify thesource of any contamination. We consider two variants of this problem:

(1) sensor-constrained: we are allowed a fixed number of sensors and want to minimize contaminationdetection time; and

(2) time-constrained: we must detect contamination within a given time limit and want to minimize the number of sensors required.

Our main results are as follows. First, we give a necessary and sufficient condition for source identification.Second, we show that the sensor and time constrained versions of the problem are polynomially equivalent. Finally, we show that the sensor-constrained version of the problem is polynomially equivalent to the asymmetric k-center problem and that the time-constrained version of the problem is polynomially equivalent to the dominating set problem.     

Efficient content distribution in social-aware hybrid networks

Internet usage is increasing in two dimensions: the time users spend online and the amount of data they send and receive. The result is an increasing stress for the Internet infrastructure. Current developments like the trend towards video on demand and IPTV introduce even more bandwidth intensive services, which amplifies the demand for an efficient content delivery model. This article presents such a model which incorporates social awareness and is based on the combination of complementary networks, referred to as a hybrid network. Its applicability is further investigated and discussed by means of a YouTube video request analysis.     

Estimating completion-time distribution in stochastic activity networks

This paper deals with simulation-based estimation of the probability distribution for completion time in stochastic activity networks. These distribution functions may be valuable in many applications. A simulation method, using importance-sampling techniques, is presented for estimation of the probability distribution function. Separating the state space into two sets, one which must be sampled and another which need not be, is suggested. The sampling plan of the simulation can then be decided after the probabilities of the two sets are adjusted. A formula for the adjustment of the probabilities is presented. It is demonstrated that the estimator is unbiased and the upper bound of variance minimized. Adaptive sampling, utilizing the importance sampling techniques, is discussed to solve problems where there is no information or more than one way to separate the state space. Examples are used to illustrate the sampling plan.     

值分布论中的一个极值问题

一 、 引 言 设f(z)是z面上的半纯函数,本文将采用大家熟知的R.Nevanlinna理论中的经典记号及其意义,如 log~+|f(re~(iθ))|,m(r,f),N(r,f),T(r,f),…。 在半纯函数值分布论中Nevanlinna猜想是一个引人注目的问题。对半纯函数f(z),其阶λ是有限数,置(以下总这样表示)。     

A turning restriction design problem in urban road networks

Turning restriction is one of the commonest traffic management techniques and an effective low cost traffic improvement strategy in urban road networks. However, the literature has not paid much attention to the turning restriction design problem (TRDP), which aims to determine a set of intersections where turning restrictions should be implemented. In this paper, a bi-level programming model is proposed to formulate the TRDP. The upper level problem is to minimize the total travel cost from the viewpoint of traffic managers, and the lower level problem is to depict travelers’ route choice behavior based on stochastic user equilibrium (SUE) theory. We propose a branch and bound method (BBM), based on the sensitivity analysis algorithm (SAA), to find the optimal turning restriction strategy. A branch strategy and a bound strategy are applied to accelerate the solution process of the TRDP. The computational experiments give promising results, showing that the optimal turning restriction strategy can obviously reduce system congestion and are robust to the variations of both the dispersion parameter of the SUE problem and the level of demand.     

Potential distribution on random electrical networks

Let N = (G, c) be a random electrical network obtained by assigning a certain resistance for each edge in a random graph G ∈ G(n, p) and the potentials on the boundary vertices. In this paper, we prove that with high probability the potential distribution of all vertices of G is very close to a constant.