An axiomatization of entropy of capacities on set systems

We present an axiomatization of the entropy of capacities defined on set systems which are not necessarily the whole power set, but satisfy a condition of regularity. This entropy encompasses the definition of Marichal and Roubens for the entropy of capacities. Its axiomatization is in the spirit of the one of Faddeev for the classical Shannon entropy. In addition, we present also an axiomatization of the entropy for capacities proposed by Dukhovny.     

k-intolerant capacities and Choquet integrals

We define an aggregation function to be (at most) k-intolerant if it is bounded from above by its kth lowest input value. Applying this definition to the discrete Choquet integral and its underlying capacity, we introduce the concept of k-intolerant capacities which, when varying k from 1 to n, cover all the possible capacities on n objects. Just as the concepts of k-additive capacities and p-symmetric capacities have been previously introduced essentially to overcome the problem of computational complexity of capacities, k-intolerant capacities are proposed here for the same purpose but also for dealing with intolerant or tolerant behaviors of aggregation. We also introduce axiomatically indices to appraise the extent to which a given capacity is k-intolerant and we apply them on a particular recruiting problem.     

Metric inequalities for routings on direct connections with application to line planning

We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the well-known feasibility condition for arc capacities in ordinary multi-commodity flows. The condition can be expressed in terms of a class of metric inequalities for routings on direct connections. We illustrate the concept on the example of the line planning problem in public transport and present an application to large-scale real-world problems.     

Asymptotically optimal production policies in dynamic stochastic jobshops with limited buffers

We consider a production planning problem for a jobshop with unreliable machines producing a number of products. There are upper and lower bounds on intermediate parts and an upper bound on finished parts. The machine capacities are modelled as finite state Markov chains. The objective is to choose the rate of production so as to minimize the total discounted cost of inventory and production. Finding an optimal control policy for this problem is difficult. Instead, we derive an asymptotic approximation by letting the rates of change of the machine states approach infinity. The asymptotic analysis leads to a limiting problem in which the stochastic machine capacities are replaced by their equilibrium mean capacities. The value function for the original problem is shown to converge to the value function of the limiting problem. The convergence rate of the value function together with the error estimate for the constructed asymptotic optimal production policies are established.     

Relative Compactness for Capacities, Measures, Upper Semicontinuous Functions and Closed Sets

We prove an Ascoli theorem for capacities. This theorem which characterizes relatively compact sets of capacities is widely applicable and many Ascoli theorems for particular classes of capacities can immediately be deduced as corollaries. Indeed it is usually necessary only to demonstrate that these classes are closed and then to simplify the characterization when possible. In particular, we show that the proof of the classical Prohorov theorem can be naturally factored into the shorter proof of the Ascoli theorem for capacities and into the somewhat longer proof that the class of probability measures is closed in the class of capacities. We also deduce new and known Ascoli theorems for sup measures, upper semi-continuous functions, the Vietoris hyperspace topology, and various classes of measures.     

Laws of large numbers of negatively correlated random variables for capacities

Our aim is to present some limit theorems for capacities.We consider a sequence of pairwise negatively correlated random variables.We obtain laws of large numbers for upper probabilities and 2-alternating capacities,using some results in the classical probability theory and a non-additive version of Chebyshev’s inequality and Boral-Contelli lemma for capacities.     

Variations of Robin capacity and applications

We obtain some estimates for the distortions of the moduli of quadrilaterals, the reduced moduli, and Robin capacities depending on the variation of the boundary of a domain. We show that for sufficiently smooth variations of the boundary the corresponding variations of the moduli and capacities are proportional to the area of the variable part of the domain in some extremal metric. We apply these results to studying the generalized Lavrent’ev problem of finding the shape of an infinitely thin airfoil of given length with the maximal aerodynamical lift under some restriction on the curvature of the airfoil.     

Revisiting parametric multi-terminal problems: Maximum flows, minimum cuts and cut-tree computations

Given an undirected network, the multi-terminal network flows analysis consists in determining the all pairs maximum flow values. In this paper, we consider an undirected network in which some edge capacities are allowed to vary and we analyze the impact of such variations on the all pairs maximum flow values. We first provide an efficient algorithm for the single parametric capacity case, and then propose a generalization to the case of multiple parametric capacities. Moreover, we provide a study on Gomory–Hu cut-tree relationships.     

The Schwarzian Derivative of a p-Valent Function

Mathematical Notes - We show that a comparison of the capacities of suitable condensers gives an inequality for the Schwarzian derivatives of a holomorphic p-valent function defined on the unit...     

Entropy of bi-capacities

In the context of multicriteria decision making whose aggregation process is based on the Choquet integral, bi-capacities can be regarded as a natural extension of capacities when the underlying evaluation scale is bipolar. The notion of entropy, recently generalized to capacities to measure their uniformity, is now extended to bi-capacities. We show that the resulting entropy measure has a very natural interpretation in terms of the Choquet integral and satisfies many natural properties that one would expect from an entropy measure.     

Estimates for certain Orlicz-Sobolev capacities of an Euclidean ball

We calculate certain Orlicz-Sobolev capacities of an Euclidian n-dimensional ball.     

As simple as possible but not simpler in Multiple Criteria Decision Aiding: the robust-stochastic level dependent Choquet integral approach

The level dependent Choquet integral has been proposed to handle decision making problems in which the importance and the interaction of criteria may depend on the level of the alternatives’ evaluations. This integral is based on a level dependent capacity, which is a family of single capacities associated to each level of evaluation for the considered criteria. We present two possible formulations of the level dependent capacity where importance and interaction of criteria are constant inside each one of the subintervals in which the interval of evaluations for considered criteria is split or vary with continuity inside the whole interval of evaluations. Since, in general, there is not only one but many level dependent capacities compatible with the preference information provided by the Decision Maker, we propose to take into account all of them by using the Robust Ordinal Regression (ROR) and the Stochastic Multicriteria Acceptability Analysis (SMAA). On one hand, ROR defines a necessary preference relation (if an alternative a is at least as good as an alternative b for all compatible level dependent capacities), and a possible preference relation (if a is at least as good as b for at least one compatible level dependent capacity). On the other hand, considering a random sampling of compatible level dependent capacities, SMAA gives the probability that each alternative reaches a certain ranking position as well as the probability that an alternative is preferred to another. A real-world decision problem on rankings of universities is provided to illustrate the proposed methodology.     

On optimal partitions,individual values and cooperative games: Does a wiser agent always produce a higher value?

We consider an optimal partition of resources (e.g. consumers) between several agents, given utility functions (“wisdoms”) for the agents and their capacities. This problem is a variant of optimal transport (Monge–Kantorovich) between two measure spaces where one of the measures is discrete (capacities) and the costs of transport are the wisdoms of the agents. We concentrate on the individual value for each agent under optimal partition and show that, counter-intuitively, this value may decrease if the agent’s wisdom is increased. Sufficient and necessary conditions for the monotonicity with respect to the wisdom functions of the individual values will be given, independently of the other agents. The sharpness of these conditions is also discussed. Motivated by the above we define a cooperative game based on optimal partition and investigate conditions for stability of the grand coalition.     

An efficient algorithm for the minimum capacity cut problem

Given a finite undirected graph with nonnegative edge capacities the minimum capacity cut problem consists of partitioning the graph into two nonempty sets such that the sum of the capacities of edges connecting the two parts is minimum among all possible partitionings. The standard algorithm to calculate a minimum capacity cut, due to Gomory and Hu (1961), runs in O(n ⁴) time and is difficult to implement. We present an alternative algorithm with the same worst-case bound which is easier to implement and which was found empirically to be far superior to the standard algorithm. We report computational results for graphs with up to 2000 nodes.Partial financial support by NSF grant DMS8508955 and ONR grant R&T4116663.Work done while visiting New York University. Partial financial support by a New York University Research Challenge Fund grant and ONR grant R&T4116663.     

Markov properties of multiparameter processes and capacities

Summary We study a class of multiparameter symmetric Markov processes. We prove that this class is stable by subordination in Bochner's sense. We show then that for these processes, a probabilistic and an analytic potential theory correspond to each other. In particular, additive functionals are associated with finite energy measures, hitting probabilities are estimated by capacities, quasicontinuity corresponds to path-continuity. In the last section, examples show that many earlier results, as well as new ones, in this domain can be obtained by our method.     

A Benders decomposition approach for a distribution network design problem with consolidation and capacity considerations

We develop a model for a strategic freight-forwarding network design problem in which the design decisions involve the locations and capacities of consolidation and deconsolidation centers, and capacities on linehaul linkages as well as the shipment routes from origins to destinations through centers. We devise a solution approach based on Benders decomposition and conduct a computational study that illustrates the efficiency and the effectiveness of the approach.     

The mixing set with divisible capacities: A simple approach

We give a simple algorithm for linear optimization over the mixing set with divisible capacities, and derive a compact extended formulation from such an algorithm. The main idea is to apply a suitable unimodular transformation to obtain an equivalent problem that is easier to analyze.     

On the optimal design of tandem queueing systems with finite buffers

We consider tandem queueing systems that can be formulated as a continuous-time Markov chain, and investigate how to maximize the throughput when the queue capacities are limited. We consider various constrained optimization problems where the decision variables are of one or more of the following types: (1) expected service times, (2) queue capacities, and (3) the number of servers at the respective stations. After surveying our previous studies of this kind, we open up consideration of three new problems by presenting some numerical results that should give some insight into the general form of the optimal design.     

Strong laws of large numbers for sub-linear expectations

We investigate three kinds of strong laws of large numbers for capacities with a new notion of independently and identically distributed(IID) random variables for sub-linear expectations initiated by Peng.It turns out that these theorems are natural and fairly neat extensions of the classical Kolmogorov’s strong law of large numbers to the case where probability measures are no longer additive. An important feature of these strong laws of large numbers is to provide a frequentist perspective on capacities.     

Thermal capacity estimates on the Allen-Cahn equation

We consider the Allen-Cahn equation in a well-known scaling regime which gives motion by mean curvature. A well-known transformation of this PDE, using its standing wave, yields a PDE the solution of which is approximately the distance function to an interface moving by mean curvature. We give bounds on this last fact in terms of thermal capacity. Our techniques hinge upon the analysis of a certain semimartingale associated with a certain PDE (the PDE for the approximate distance function) and an analogue of some results by Bañuelos and Øksendal relating lifetimes of diffusions to exterior capacities.