An axiomatization of the Choquet integral in the context of multiple criteria decision making without any commensurability assumption

An axiomatization of the Choquet integral is proposed in the context of multiple criteria decision making without any commensurability assumption. The most essential axiom—named Commensurability Through Interaction—states that the importance of an attribute i takes only one or two values when a second attribute k varies. When the importance takes two values, the point of discontinuity is exactly the value on the attribute k that is commensurate to the fixed value on attribute i. If the weight of criterion i does not depend on criterion k, for any value of the other criteria than i and k, then criteria i and k are independent. Applying this construction to any pair i, k of criteria, one obtains a partition of the set of criteria. In each block, the criteria interact one with another, and it is thus possible to construct vectors of values on the attributes that are commensurate. There is complete independence between the criteria of any two blocks in this partition. Hence one cannot ensure commensurability between two blocks in the partition. But this is not a problem since the Choquet integral is additive between subsets of criteria that are independent.     

Interactive outranking approaches for multicriteria decision-making problems with imprecise information

PROMETHEE is a powerful method, which can solve many multiple criteria decision making (MCDM) problems. It involves sophisticated preference modelling techniques but requires too much a priori precise information about parameter values (such as criterion weights and thresholds). In this paper, we consider a MCDM problem where alternatives are evaluated on several conflicting criteria, and the criterion weights and/or thresholds are imprecise or unknown to the decision maker (DM). We build robust outranking relations among the alternatives in order to help the DM to rank the alternatives and select the best alternative. We propose interactive approaches based on PROMETHEE method. We develop a decision aid tool called INTOUR, which implements the developed approaches.     

Implicit completeness in the <Emphasis Type="Italic">k</Emphasis>-valued logic

A criterion of implicit completeness in a k-valued logic P _k for arbitrary k ≥ 2 is established.     

On balanced colorings of the <Emphasis Type="Italic">n</Emphasis>-cube

A 2-coloring of the n-cube in the n-dimensional Euclidean space can be considered as an assignment of weights of 1 or 0 to the vertices. Such a colored n-cube is said to be balanced if its center of mass coincides with its geometric center. Let B _n,2k be the number of balanced 2-colorings of the n-cube with 2k vertices having weight 1. Palmer, Read, and Robinson conjectured that for n≥1, the sequence \(\{B_{n,2k}\}_{k=0,1,\ldots,2^{n-1}}\) is symmetric and unimodal. We give a proof of this conjecture. We also propose a conjecture on the log-concavity of B _n,2k for fixed k, and by probabilistic method we show that it holds when n is sufficiently large.     

Specialization results and ramification conditions

Given a hilbertian field k of characteristic zero and a finite Galois extension E/k(T) with group G such that E/k is regular, we produce some specializations of E/k(T) at points t0 ∈ P¹(k) which have the same Galois group but also specified inertia groups at finitely many given primes. This result has two main applications. Firstly we conjoin it with previous works to obtain Galois extensions of Q of various finite groups with specified local behavior — ramified or unramified — at finitely many given primes. Secondly, in the case k is a number field, we provide criteria for the extension E/k(T) to satisfy this property: at least one Galois extension F/k of group G is not a specialization of E/k(T).     

On criteria of estimation of the errors of cubature formulas

The paper considers cubature formulas for calculating integrals of functions f(X), X = (x ₁, …, x _n ) which are defined on the n-dimensional unit hypercube K ⁿ = [0, 1] ⁿ and have integrable mixed derivatives of the kind \(\partial _{\begin{array}{*{20}c} {\alpha _1 \alpha _n } \\ {x_1 , \ldots , x_n } \\ \end{array} } f(X)\), 0 ≤ α _j ≤ 2. We estimate the errors R[f] = \(\smallint _{K^n } \) f(X)dX ? Σ _{k = 1} ^N c _k f(X(k)) of cubature formulas (c _k > 0) as functions of the weights c _k of nodes X(k) and properties of integrable functions. The error is estimated in terms of the integrals of the derivatives of f over r-dimensional faces (r≤n) of the hypercube K ⁿ : |R(f)| ≤ \(\sum _{\alpha _j } \) G(α _j )\(\int_{K^r } {\left| {\partial _{\begin{array}{*{20}c} {\alpha _1 \alpha _n } \\ {x_1 , \ldots , x_n } \\ \end{array} } f(X)} \right|} \) dX _r , where coefficients G(α _j ) are criteria which depend only on parameters c _k and X(k). We present an algorithm to calculate these criteria in the two- and n-dimensional cases. Examples are given. A particular case of the criteria is the discrepancy, and the algorithm proposed is a generalization of those used to compute the discrepancy. The results obtained can be used for optimization of cubature formulas as functions of c _k and X(k).     

Condition monitoring: a new perspective

We present a novel approach to support preventive replacement decisions based on condition monitoring. It is assumed that the condition of a technical unit is measured continuously, with the measurement indicating in which of k≥2 states the unit is. A new unit is in state S₁, and failure occurs the moment a unit leaves state S _k . A unit will only go from state S _j to state S_j+1, and these immediately observed transitions occur at random times. At such transition moments a decision is required on preventive replacement of the unit, which would require preparation time. Such a decision needs to be based on inferences about the total residual time till failure. We present a method for such inferences that relies on minimal model assumptions added to data on state transitions. We illustrate the approach via simulated examples, and discuss possible use of the method and related aspects.     

The Number of Labeled Outerplanar <Emphasis Type="Italic">k</Emphasis>-Cyclic Graphs

A k-cyclic graph is a graph with cyclomatic number k. An explicit formula for the number of labeled connected outerplanar k-cyclic graphs with a given number of vertices is obtained. In addition, such graphs with fixed cyclomatic number k and a large number of vertices are asymptotically enumerated. As a consequence, it is found that, for fixed k, almost all labeled connected outerplanar k-cyclic graphs with a large number of vertices are cacti.     

Partition of a unity on infinite-dimensional manifold of the Lipschiz class Lip<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>

In the present paper we prove a criterion of Lip ^k -paracompactness for infinitedimensional manifold M modeled in nonnormable topological vector Fréchet space F. We establish that a manifold is Lip ^k -paracompact if and only if the model space F is paracompact and Lip ^k -normal. We prove a sufficient condition for existence of Lip ^k -partition of a unity on a manifold of class Lip ^k .     

Conductors in <Emphasis Type="Italic">p</Emphasis>-adic families

Let the function \(s_g\) map a positive integer to the sum of its digits in the base g. A number k is called n-flimsy in the base g if \(s_g(nk)<s_g(k)\). Clearly, given a base g, \(g\geqslant 2\), if n is a power of g, then there does not exist an n-flimsy number in the base g. We give a constructive proof of the existence of an n-flimsy number in the base g for all the other values of n (such an existence follows from the results of Schmidt and Steiner, but the explicit construction is a novelty). Our algorithm for construction of such a number, say k, is very flexible in the sense that, by easy modifications, we can impose further requirements on k—k ends with a given sequence of digits, k begins with a given sequence of digits, k is divisible by a given number (or belongs to a certain congruence class modulo a given number), etc.     

Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.     

An Accelerated Inexact Proximal Point Algorithm for Convex Minimization

The proximal point algorithm is classical and popular in the community of optimization. In practice, inexact proximal point algorithms which solve the involved proximal subproblems approximately subject to certain inexact criteria are truly implementable. In this paper, we first propose an inexact proximal point algorithm with a new inexact criterion for solving convex minimization, and show its O(1/k) iteration-complexity. Then we show that this inexact proximal point algorithm is eligible for being accelerated by some influential acceleration schemes proposed by Nesterov. Accordingly, an accelerated inexact proximal point algorithm with an iteration-complexity of O(1/k ²) is proposed.     

The Number of <Emphasis Type="Italic">k</Emphasis>-Sumsets in an Abelian Group

Let G be an abelian group of order n. The sum of subsets A₁,...,A_k of G is defined as the collection of all sums of k elements from A₁,...,A_k; i.e., A₁ + A₂ + · · · + A_k = {a₁ + · · · + a_k | a₁ ∈ A₁,..., a_k ∈ A_k}. A subset representable as the sum of k subsets of G is a k-sumset. We consider the problem of the number of k-sumsets in an abelian group G. It is obvious that each subset A in G is a k-sumset since A is representable as A = A₁ + · · · + A_k, where A₁ = A and A₂ = · · · = A_k = {0}. Thus, the number of k-sumsets is equal to the number of all subsets of G. But, if we introduce a constraint on the size of the summands A₁,...,A_k then the number of k-sumsets becomes substantially smaller. A lower and upper asymptotic bounds of the number of k-sumsets in abelian groups are obtained provided that there exists a summand A_i such that |A_i| = n log^qn and |A₁ +· · ·+ A_i-1 + A_i+1 + · · ·+A_k| = n log^qn, where q = -1/8 and i ∈ {1,..., k}.     

Markov decision processes with noise-corrupted and delayed state observations

We consider the partially observed Markov decision process with observations delayed by k time periods. We show that at stage t, a sufficient statistic is the probability distribution of the underlying system state at stage t - k and all actions taken from stage t - k through stage t - 1. We show that improved observation quality and/or reduced data delay will not decrease the optimal expected total discounted reward, and we explore the optimality conditions for three important special cases. We present a measure of the marginal value of receiving state observations delayed by (k - 1) stages rather than delayed by k stages. We show that in the limit as k →∞ the problem is equivalent to the completely unobserved case. We present numerical examples which illustrate the value of receiving state information delayed by k stages.     

Analysis of Local Search Landscapes for <Emphasis Type="Italic">k</Emphasis>-SAT Instances

Stochastic local search is a successful technique in diverse areas of combinatorial optimisation and is predominantly applied to hard problems. When dealing with individual instances of hard problems, gathering information about specific properties of instances in a pre-processing phase is helpful for an appropriate parameter adjustment of local search-based procedures. In the present paper, we address parameter estimations in the context of landscapes induced by k-SAT instances: at first, we utilise a sampling method devised by Garnier and Kallel in 2002 for approximations of the number of local maxima in landscapes generated by individual k-SAT instances and a simple neighbourhood relation. The objective function is given by the number of satisfied clauses. The procedure provides good approximations of the actual number of local maxima, with a deviation typically around 10%. Secondly, we provide a method for obtaining upper bounds for the average number of local maxima in k-SAT instances. The method allows us to obtain the upper bound \(2^{n-O(\sqrt{n/k})}\) for the average number of local maxima, if m is in the region of 2 ^k · n/k.     

Semigroup and Metric Characteristics of Locally Primitive Matrices and Digraphs

The notion of local primitivity for a quadratic 0, 1-matrix of size n × n is extended to any part of the matrix which need not be a rectangular submatrix. A similar generalization is carried out for any set B of pairs of initial and final vertices of the paths in an n-vertex digraph, B ? {(i, j) : 1 ≤ i, j ≤ n}. We establish the relationship between the local B-exponent of a matrix (digraph) and its characteristics such as the cyclic depth and period, the number of nonprimitive matrices, and the number of nonidempotentmatrices in the multiplicative semigroup of all quadratic 0, 1-matrices of order n, etc. We obtain a criterion of B-primitivity and an upper bound for the B-exponent. We also introduce some new metric characteristics for a locally primitive digraph Γ: the k, r-exporadius, the k, r-expocenter, where 1 ≤ k, r ≤ n, and the matex which is defined as the matrix of order n of all local exponents in the digraph Γ. An example of computation of the matex is given for the n-vertex Wielandt digraph. Using the introduced characteristics, we propose an idea for algorithmically constructing realizable s-boxes (elements of round functions of block ciphers) with a relatively wide range of sizes.     

A Formula for the Partition Function That “Counts”

We derive a combinatorial multisum expression for the number D(n, k) of partitions of n with Durfee square of order k. An immediate corollary is therefore a combinatorial formula for p(n), the number of partitions of n. We then study D(n, k) as a quasipolynomial. We consider the natural polynomial approximation \({\tilde{D}(n, k)}\) to the quasipolynomial representation of D(n, k). Numerically, the sum \({\sum_{1\leq k \leq \sqrt{n}} \tilde{D}(n, k)}\) appears to be extremely close to the initial term of the Hardy-Ramanujan-Rademacher convergent series for p(n).     

The communication complexity of addition

Suppose each of k≤n ^o(1) players holds an n-bit number x _i in its hand. The players wish to determine if ∑ _i≤k x _i =s. We give a public-coin protocol with error 1% and communication O(k logk). The communication bound is independent of n, and for k≥3 improves on the O(k logn) bound by Nisan (Bolyai Soc. Math. Studies; 1993).