Time offset optimization in digital broadcasting

We investigate a planning problem arising in the forthcoming digital video broadcasting (DVB-T) system. Unlike current analog systems, the DVB-T standard allows a mitigation of the interference by means of a suitable synchronization of the received signals. The problem we describe in this paper is that of finding a time offset to impose to the signal emitted by each transmitter of the network, so as to maximize the network (territory) coverage (TOP, time offset problem). We show that, unlike related problems in which other transmitter parameters are taken as decision variables (e.g., emission powers or frequencies), TOP has a nice and algorithmically exploitable combinatorial structure. Namely, we introduce an exponentially sized set covering formulation of TOP, in which constraints are dynamically generated by a polynomial time oracle. We show the effectiveness of the approach through extensive experiments on the reference test bed of the Italian DVB-T Frequency Plan.     

Cavity Volume and Free Energy in Many-Body Systems

Most models for the spread of an invasive species into a new environment are based on Fisher’s reaction–diffusion equation. They assume that habitat quality is independent of the presence or absence of the invading population. Ecosystem engineers are species that modify their environment to make it (more) suitable for them. A potentially more appropriate modeling approach for such an invasive species is to adapt the well-known Stefan problem of melting ice. Ahead of the front, the habitat is unsuitable for the species (the ice); behind the front, the habitat is suitable (the open water). The engineering action of the population moves the boundary ahead (the melting). This approach leads to a free boundary problem. In this paper, we study the well-posedness of a novel free boundary model for the spread of ecosystem engineers that was recently derived from an individual random walk model. The Stefan condition for the moving boundary is replaced by a biologically derived two-sided condition that models the movement behavior of individuals at the boundary as well as the process by which the population moves the boundary to expand their territory. Our proofs consist of several new and novel ideas that can be used in broader contexts. We assign a convex functional to this problem so that the evolution system governed by this convex potential is exactly the system of evolution equations describing the above model. We then apply variational and fixed-point methods to deal with this free boundary problem.

     

The maximum reliability location problem and α-reliablep-center problem: Derivatives of the probabilistic location set covering problem

In the last several years, the modeling of emergency vehicle location has focussed on the temporal availability of the vehicles. Vehicles are not available for service when they are engaged in earlier calls. To incorporate this dynamic aspect into facility location decisions, models have been developed which provide additional levels of coverage. In this paper, two new models are derived from the probabilistic location set covering problem. These models allow the examination of the relationships between the number of facilities being located, the reliability that a vehicle will be available, and a coverage standard. In addition, these models incorporate sectoral specific estimates of the availability of the vehicles. Solution of these models reveals that the use of sectoral estimates leads to facility locations which are distributed to a greater spatial extent over the region to be serviced.     

The maximum covering/shortest path problem: A multiobjective network design and routing formulation

In this paper the authors introduce the maximum covering/shortest path problem and the maximum population/shortest path problem, a special case of the former model. Both models are formulated as two objective integer programs. A summary of the results of a sample problem for the latter formulation is given. Possible modifications to, and extensions and applications of both models are also presented. With these formulations the authors extend the concept of ‘coverage’ from facility location analysis to network design and routing analysis.     

Fuzzy goal programming models for analyzing demand coverage

The main objective of demand coverage models is to locate servers so that a given demand space is appropriately covered. Most existing models assume that demand is located at specific points within an area and that coverage is evaluated by certain quantifiable criteria. However, in realistic applications, the concept of coverage may also include qualitative aspects. Moreover, the location of the servers may be determined on the basis of more than one objective. In this paper, we present a number of fuzzy goal programming models for demand coverage. We consider three objectives: (a) maximization of total coverage, (b) maximization of minimum coverage, and (c) minimization of distance to servers of uncovered demand points. Through a series of realistic problem instances, we demonstrate that the proposed models provide satisfactory solutions with respect to all three objectives.     

Efficient Data Augmentation for Fitting Stochastic Epidemic Models to Prevalence Data

Stochastic epidemic models describe the dynamics of an epidemic as a disease spreads through a population. Typically, only a fraction of cases are observed at a set of discrete times. The absence of complete information about the time evolution of an epidemic gives rise to a complicated latent variable problem in which the state space size of the epidemic grows large as the population size increases. This makes analytically integrating over the missing data infeasible for populations of even moderate size. We present a data augmentation Markov chain Monte Carlo (MCMC) framework for Bayesian estimation of stochastic epidemic model parameters, in which measurements are augmented with subject-level disease histories. In our MCMC algorithm, we propose each new subject-level path, conditional on the data, using a time-inhomogenous continuous-time Markov process with rates determined by the infection histories of other individuals. The method is general, and may be applied to a broad class of epidemic models with only minimal modifications to the model dynamics and/or emission distribution. We present our algorithm in the context of multiple stochastic epidemic models in which the data are binomially sampled prevalence counts, and apply our method to data from an outbreak of influenza in a British boarding school. Supplementary material for this article is available online.     

Optimal Direct and Indirect Covering Trees

The maximal covering subtree problem has applications in transportation network design and extensive facility location. A subtree of a network is a tree that is not a full spanning tree. Finding an optimal subtree may involve the two objectives, minimizing the total arc cost or distance of the subtree, and maximizing the subtree's coverage of population or demand at nodes. Coverage may be defined as direct or indirect: indirect coverage requires that a node be within a distance threshold s>0 of the subtree, and direct coverage requires that a node be connected to the subtree (s=0). Previous approaches to this problem have sought to identify optimal subtrees of a parent network that is itself a tree (e.g., a minimum spanning tree). In this paper four new bi-objective zero–one programming models are presented. The first two are models for the problem of finding optimal subtrees on a single spanning tree parent under conditions of (1) direct and (2) indirect coverage. These problems have been addressed previously in the literature. In the third and fourth models, the subtree can be selected from among multiple candidate parent spanning trees simultaneously. The latter models address a new generalization of the first problem and offer both increased flexibility and the potential for a more diverse array of solutions. The models have integer-friendly solution properties and are relatively small in terms of the number of decision variables and constraints. Computational experience is reported for a demonstration problem and results are compared to the results of previous models.     

A unified solving approach for two and three dimensional coverage problems in sensor networks

The problem of designing a wired or a wireless sensor network to cover, monitor and/or control a region of interest has been widely treated in literature. This problem is referred to in literature as the sensor placement problem (SPP) and in the most general case it consists in determining the number and the location of one or more kind of sensors with the aim of covering all the region of interest or a significant part of it. In this paper we propose a unified and stepwise solving approach for two and three dimensional coverage problems to be used in omni-directional and directional sensor networks. The proposed approach is based on schematizing the region of interest and the sensor potential locations by a grid of points and representing the sensor coverage area by a circle or by a circular sector. On this basis, the SPP is reduced to an optimal coverage problem and can be formulated by integer linear programming (ILP) models. We will resume the main ILP models used in our approach, highlighting, for each of them, the specific target to be achieved and the design constraints taken into account. The paper concludes with an application of the proposed approach to a real test case and a discussion of the obtained results.     

Optimization scheme for sensor coverage scheduling with bandwidth constraints

Wireless Sensor Network has attracted a lot of attentions due to its broad applications in recent years and also introduces many challenges. Network lifetime is a critical issue in Wireless Sensor Networks. It is possible to extend network lifetime by organizing the sensors into a number of sensor covers. However, with the limited bandwidth, coverage breach (i.e, targets that are not covered) can occur if the number of available time-slots/channels is less than the number of sensors in a sensor cover. In this paper, we study a joint optimization problem in which the objective is to minimize the coverage breach as well as to maximize the network lifetime. We show a “trade-off” scheme by presenting two strongly related models, which aim to tradeoffs between the two conflicting objectives. The main approach of our models is organizing sensors into non-disjoint sets, which is different from the current most popular approach and can gain longer network lifetime as well as less coverage breach. We proposed two algorithms for the first model based on linear programming and greedy techniques, respectively. Then we transform these algorithms to solve the second model by revealing the strong connection between the models. Through numerical simulation, we showed the good performance of our algorithms and the pictures of the tradeoff scheme in variant scenarios, which coincide with theoretical analysis very well. It is also showed that our algorithms could obtain less breach rate than the one proposed in (Cheng et al. in INFOCOM’ 05, 2005).     

Joint ground and air emergency medical services coverage models: A greedy heuristic solution approach

Aeromedical and ground ambulance services often team up in responding to trauma crashes, especially when the emergency helicopter is unable to land at the crash scene. We propose location-coverage models and a greedy heuristic for their solution to simultaneously locate ground and air ambulances, and landing zones (transfer points). We provide a coverage definition based on both response time and total service time, and consider three coverage options; only ground emergency medical services (EMS) coverage, only air EMS coverage, or joint coverage of ground and air EMS in which the patient is transferred from an ambulance into an emergency helicopter at a transfer point. To analyze this complex coverage situation we develop two sets of models, which are variations of the Location Set Covering Problem (LSCP) and the Maximal Covering Location Problem (MCLP). These models address uncertainty in spatial distribution of motor vehicle crash locations by providing coverage to a given set of both crash nodes and paths. The models also consider unavailability of ground ambulances by drawing upon concepts from backup coverage models. We illustrate our results on a case study that uses crash data from the state of New Mexico. The case study shows that crash node and path coverage percentage values decrease when ground ambulances are utilized only within their own jurisdiction.     

Multiagent Temporal Logics with Multivaluations

We study multiagent logics and use temporal relational models with multivaluations. The key distinction from the standard relational models is the introduction of a particular valuation for each agent and the computation of the global valuation using all agents’ valuations. We discuss this approach, illustrate it with examples, and demonstrate that this is not a mechanical combination of standard models, but a much more subtle and sophisticated modeling of the computation of truth values in multiagent environments. To express the properties of these models we define a logical language with temporal formulas and introduce the logics based at classes of such models. The main mathematical problem under study is the satisfiability problem. We solve it and find deciding algorithms. Also we discuss some interesting open problems and trends of possible further investigations.     

Solving a minimum-power covering problem with overlap constraint for cellular network design

We consider a type of covering problem in cellular networks. Given the locations of base stations, the problem amounts to determining cell coverage at minimum cost in terms of the power usage. Overlap between adjacent cells is required in order to support handover. The problem we consider is NP-hard. We present integer linear models and study the strengths of their continuous relaxations. Preprocessing is used to reduce problem size and tighten the models. Moreover, we design a tabu search algorithm for finding near-optimal solutions effectively and time-efficiently. We report computational results for both synthesized instances and networks originating from real planning scenarios. The results show that one of the integer models leads to tight bounds, and the tabu search algorithm generates high-quality solutions for large instances in short computing time.     

Allocation of Marketing Effort Among <Emphasis Type="Italic">P</Emphasis> Substitutional Products in <Emphasis Type="Italic">N</Emphasis> Territories<Superscript>†</Superscript>

Frequently, companies face the problem of allocating a given marketing budget in order to maximize their total returns. In this paper we examine the problem of allocating marketing effort, such as advertising, among P substitutional products, distributed in N different sales territories. Two models are discussed. In the first model it is assumed that at most one product is promoted in each sales territory. It is shown that a simple algorithm leads to at least a local optimum in a finite number of steps. In the second model, the restriction of one product per territory is eliminated. Applying a concept of effective effort, the model is transformed to an equivalent separable programming problem, solvable by a “single-pass” algorithm for various forms of response functions. Furthermore, a concept of successive modifications of the objective function is discussed.     

Modeling influenza progression within a continuous-attribute heterogeneous population

We consider three attributes of an individual that are critical in determining the temporal dynamics of pandemic influenza: social activity, proneness to infection, and proneness to shed virus and spread infection. These attributes differ by individual, resulting in a heterogeneous population. We develop discrete-time models that depict the evolution of the disease in the presence of such population heterogeneity. For every individual, the value for each of the three describing attributes is viewed as an experimental value of a continuous random variable. The methodology is simple yet general, extending more traditional discrete compartmental models that depict population heterogeneity. Illustrative numerical examples show how individuals who have much larger-than-average values for one or more of the attributes drive the influenza wave, especially in the early generations of the pandemic. This heterogeneity-driven pandemic physics carries important policy implications. We conclude by using contact data in four European countries to demonstrate empirical uses of our model.     

Bayesian multivariate Poisson models for insurance ratemaking

When actuaries face the problem of pricing an insurance contract that contains different types of coverage, such as a motor insurance or a homeowner’s insurance policy, they usually assume that types of claim are independent. However, this assumption may not be realistic: several studies have shown that there is a positive correlation between types of claim. Here we introduce different multivariate Poisson regression models in order to relax the independence assumption, including zero-inflated models to account for excess of zeros and overdispersion. These models have been largely ignored to date, mainly because of their computational difficulties. Bayesian inference based on MCMC helps to resolve this problem (and also allows us to derive, for several quantities of interest, posterior summaries to account for uncertainty). Finally, these models are applied to an automobile insurance claims database with three different types of claim. We analyse the consequences for pure and loaded premiums when the independence assumption is relaxed by using different multivariate Poisson regression models together with their zero-inflated versions.     

Some combinatorial aspects of discrete non-linear population dynamics

Motivated by issues arising in population dynamics, we consider the problem of iterating a given analytic function a number of times. We use the celebrated technique known as Carleman linearization that turns (for a certain class of functions) this problem into simply taking the power of a real number. We expand this method, showing in particular that it can be used for population models with immigration, and we also apply it to the famous logistic map. We also are able to give a number of results for the invariant density of this map, some being related to the Carleman linearization.     

The minmax regret gradual covering location problem on a network with incomplete information of demand weights

The gradual covering location problem seeks to establish facilities on a network so as to maximize the total demand covered, allowing partial coverage. We focus on the gradual covering location problem when the demand weights associated with nodes of the network are random variables whose probability distributions are unknown. Using only information on the range of these random variables, this study is aimed at finding the “minmax regret” location that minimizes the worst-case coverage loss. We show that under some conditions, the problem is equivalent to known location problems (e.g. the minmax regret median problem). Polynomial time algorithms are developed for the problem on a general network with linear coverage decay functions.     

A new model for maximal coverage exploiting GIS capabilities

The representation of demand is a key issue which can significantly affect results in several demand covering models. In this paper we concentrate on the well known Maximal Coverage Location Problem and demonstrate that alternative representations of the demand space may lead to largely fluctuating as well as misleading results which seriously overestimate the real coverage achieved by a specified number of servers. We introduce a new model based on the notion of complementary partial coverage and exploit the capabilities of Geographic Information Systems in order to better represent demand. Results of an empirical study indicate that the proposed model is less susceptible to fluctuations for alternative representations of the demand space and that it provides coverage of a larger proportion of demand than traditional models.     

Competitive carbon emission yields the possibility of global self-control

Despite many international climate meetings such as Copenhagen 2009, it is still unclear how annual global emissions can be reduced without requiring governments to micro-manage the emitting companies within their individual jurisdictions. Here we examine a simple, yet highly non-trivial, computer model of carbon emission which is consistent with recent activity in the European carbon markets. Our simulation results show that the ongoing daily competition to emit CO₂ within a population of emitters, can lead to a form of collective self-control over the aggregated emissions. We identify regimes in which such a population spontaneously hits its emissions target with minimal fluctuations. We then focus on the emission dynamics induced by a governing body which chooses to actively manage the capping level. Finally we lay some formal stepping stones toward a complete analytic theory for carbon emissions fluctuations within this model framework – in so doing, we also connect this problem to more familiar theoretical terrain within computer science.     

Stability and Hopf bifurcation in a class of nonlocal delay differential equation with the zero‐flux boundary condition

The aim of this paper is to study the stability and Hopf bifurcation in a general class of differential equation with nonlocal delayed feedback that models the population dynamics of a two age structured spices. The existence of Hopf bifurcation is firstly established after delicately analyzing the eigenvalue problem of the linearized nonlocal equation. The direction of the Hopf bifurcation and stability of the bifurcated periodic solutions are then investigated by means of center manifold reduction. Subsequently, we apply our main results to explore the spatial‐temporal patterns of the nonlocal Mackey‐Glass equation. We obtain both spatially homogeneous and inhomogeneous periodic solutions and numerically show that the former is stable while the latter is unstable. We also show that the inhomogeneous periodic solutions will eventually tend to homogeneous periodic solutions after transient oscillations and increasing of the immature mobility constant will shorten the transient oscillation time.