Iterative behaviour of generalized majority functions

Let us consider a society of n persons {P₁,…,P_n} with interaction coefficient a_ij between P_i and P_j. Let {θ₁,…,θ_p} be the set of opinions which may be assumed by any person. We study the dynamical behaviour of such a society under local majority rules.The results presented in this paper generalize many partial results previously obtained by several authors (Tchuente, 1977; Goles and Olivos, 1980; Poljak and Sura, 1982). Furthermore, by introducing algebraic invariants, analogous to those exhibited in Goles (1980) for the study of Boolean threshold functions, we provide a tool for a general approach of such dynamical models.     

Arbres avec un nombre maximum de sommets pendants

This article is an attempt to study the following problem: Given a connected graph G, what is the maximum number of vertices of degree 1 of a spanning tree of G? For cubic graphs with n vertices, we prove that this number is bounded by $\text{1}\text{4}\text{n}$ and $\text{1}\text{2}\text{(n ? 2)}$.     

Parallel calculation of a linear mapping on a computer network

We are interested in the parallel computation of a linear mapping of n real variables by a network of computers with restricted means of communication between them and without any common memory. Let $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ denote the algebra of n×n real matrices, and let G be the graph associated with a binary, reflexive and symmetric relation R over {1,2, …,n}. We define

$\text{A}{}_{\mathrm{R}}\text{= {A?M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{):a}{}_{\mathrm{ij}}\text{≠ 0}\text{implies}\text{iRj}}$

A matrix $\text{M∈M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ is said to be realizable on G if it can be expressed as a product of elements of A_R. Therefore, every matrix of $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ is realizable on G if and only if A_R generates $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$. We show that A_R generates $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ if and only if G is connected.     

On the Minimum Average Distance Spanning Tree of the Hypercube

Given an undirected and connected graph G, with a non-negative weight on each edge, the Minimum Average Distance (MAD) spanning tree problem is to find a spanning tree of G which minimizes the average distance between pairs of vertices. This network design problem is known to be NP-hard even when the edge-weights are equal. In this paper we make a step towards the proof of a conjecture stated by A.A. Dobrynin, R. Entringer and I. Gutman in 2001, and which says that the binomial tree B _n is a MAD spanning tree of the hypercube H _n . More precisely, we show that the binomial tree B _n is a local optimum with respect to the 1-move heuristic which, starting from a spanning tree T of the hypercube H _n , attempts to improve the average distance between pairs of vertices, by adding an edge e of H _n -T and removing an edge e′ from the unique cycle created by e. We also present a greedy algorithm which produces good solutions for the MAD spanning tree problem on regular graphs such as the hypercube and the torus.     

Complexity of the pipeline computation of a family of inner products

We are interested in the minimum time T(S) necessary for computing a family S = { < S_i, S_j >: ? S_i, S_j?R^p, (i, j) ?E } of inner products of order p, on a systolic array of order p × 2. We first prove that the determination of T(S) is equivalent to the partition problem and is thus NP-complete. Then we show that the designing of an algorithm which runs in time T(S) + 1 is equivalent to the problem of finding an undirected bipartite eulerian multigraph with the smallest number of edges, which contains a given undirected bipartite graph, and can therefore be solved in polynomial time.     

Real estate price estimation in French cities using geocoding and machine learning

This paper reviews real estate price estimation in France, a market that has received little attention. We compare seven popular machine learning techniques by proposing a different approach that quantifies the relevance of location features in real estate price estimation with high and fine levels of granularity. We take advantage of a newly available open dataset provided by the French government that contains 5 years of historical data of real estate transactions. At a high level of granularity, we obtain important differences regarding the models’ prediction powers between cities with medium and high standards of living (precision differences beyond 70% in some cases). At a low level of granularity, we use geocoding to add precise geographical location features to the machine learning algorithm inputs. We obtain important improvements regarding the models’ forecasting powers relative to models trained without these features (improvements beyond 50% for some forecasting error measures). Our results also reveal that neural networks and random forest techniques particularly outperform other methods when geocoding features are not accounted for, while random forest, adaboost and gradient boosting perform well when geocoding features are considered. For identifying opportunities in the real estate market through real estate price prediction, our results can be of particular interest. They can also serve as a basis for price assessment in revenue management for durable and non-replenishable products such as real estate.

     

Parallel realization of permutations over trees

Let G = (X,E) be a finite connected (undirected) graph; a permutation σ over X is said to be compatible with G when every vertex x different from σ(x) is adjacent to σ(x); l(G) denotes the minimum k such that every permutation over X can be decomposed into a product of k permutations compatible with G. It is shown that, among all trees with X as set of vertices, the chain has the smallest l(G).     

Iterative behaviour of one-dimensional threshold automata

This paper presents two results on the dynamical behaviour of some finite binary one-dimensional threshold automata, where the interaction coefficient between two cells i, j is a decreasing function of |i?j|.     

Connection-graph and iteration-graph of monotone boolean functions

In this paper, we establish some relationships between the circuits of the connection-graph G_C(F), and the circuits of theiteration-graph G₁(F), of a monotone boolean function F. We first show that if G₁(F) contains an element circuit of length multiple of p? {2,3}, then G_C(F) contains an elementary circuit of length multiple of p; then we prove that if G_C(F) is a subgraph of a caterpillar, then G₁(F) is a subgraph of a tree; at last we exhibit an infinite family of monotone boolean functions {F_n; n = 2 × 5^q, q ≥ 1} such that any G_C(F_n) is a subgraph of a tree, and G₁(F_n) contains a circuit of length 2^q+1, i.e., of the order $\text{n}{}^{\mathrm{<mtext>log</mtext><mtext>2</mtext><mtext>log5</mtext>}}$.