15771 research outputs found
Sort by
New Insight into 2-Community Structures in Graphs with Applications in Social Networks
No full textin Springer series Lecture Notes in Computer Science, Vol 9486We investigate the structural and algorithmic properties of 2-community structure in graphs introduced by Olsen [13]. A 2-community structure is a partition of vertex set into two parts such that for each vertex of the graph number of neighbours in/outside own part is in correlation with sizes of parts. We show that every 3-regular graph has a 2-community structure which can be found in polynomial time, even if the subgraphs induced by each partition must be connected. We introduce a concept of a 2-weak community and prove that it is NP-complete to find a balanced 2-weak community structure in general graphs even with additional request of connectivity for both parts. On the other hand, the problem can be solved in polynomial time in graphs of degree at most 3.nonouirechercheInternationa
Possible and Necessary Winners of Partial Tournaments
No full textWe study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them, possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.nonouirechercheInternationa
Forward Curve Risk Factors Analysis in the UK Real Estate Market
No full textThis paper empirically investigates the risk factors of the property swap prices using 4 years of price data relative to the UK Investment Property Databank (IPD) Total Return All Property Swap. The implied forward rates are analyzed with a first difference model to determine its main components. Regarding the risk free rate, the traditional sport-forward relation does not hold for property derivatives. The impact of the risk free rate on forward rates appears as being complex and made of different effects; it varies according to time and maturities. Derivatives prices take into account the smoothing effect of the underlying index and REITs stocks are also relevant to explain these prices. The informational content of the swap is important. The impact of the REITs and of the smoothing decreases with maturities. The risk factor structure obtained is more complex than found in many other studies relative to commodities, securities or bonds. Possible reasons for this phenomenon are discussed.nonouirechercheInternationa
Nested Monte Carlo Search for Two-Player Games
No full textThe use of the Monte Carlo playouts as an evaluation function has proved to be a viable, general technique for searching intractable game spaces. This facilitate the use of statistical techniques like Monte Carlo Tree Search (MCTS), but is also known to require significant processing overhead. Weseek to improve the quality of information extracted from the Monte Carlo playout in three ways. Firstly, by nesting the evaluation function inside another evaluation function; secondly, by measuring and utilising the depth of the playout; and thirdly, by incorporating pruning strategies that eliminateunnecessary searches and avoid traps. Our experimental data, obtained on a variety of two-player games from past General Game Playing (GGP) competitions and others, demonstrate the usefulness of these techniques in a Nested Player when pitted against a standard, optimised UCT player.nonouirechercheInternationa
Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
No full textIt is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN-CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances of kSAT-formulas, and linear equations mod 2, Ek-LIN2, do have PTASs for any k. The MIN-Ek-LIN2 problems are equivalent to the k-ary versions of the Nearest Codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique for k-uniform hypergraphs which could be of independent interest.nonouirechercheInternationa
Rural Road Maintenance in Madagascar: the GENIS project
No full textThe paper reports a real world decision aiding process concerning rural road maintenance in Madagascar. The issue arises within AGETIPA, the National Agency in charge of conducting Public Works in Madagascar, and can be summarised as a problem of resource allocation to a number of competitive projects. The problem has been modeled using multiple criteria and a classification procedure under two objectives: make the most rational use of the limited available resources and promote participation and commitment of the local actors in the maintenance process. The project is part of an on-going partnership between the LAMSADE and AGETIPA aiming to enhance Decision Support Capacity within AGETIPA.nonouirechercheInternationa
Geometry-aware stationary subspace analysis
No full textIn many real-world applications data exhibits non-stationarity, i.e., its distribution changes over time. One approach to handling non-stationarity is to remove or minimize it before attempting to analyze the data. In the context of brain computer interface (BCI) data analysis this is sometimes achieved using stationary subspace analysis (SSA). The classic SSA method finds a matrix that projects the data onto a stationary subspace by optimizing a cost function based on a matrix divergence. In this work we present an alternative method for SSA based on a symmetrized version of this matrix divergence. We show that this frames the problem in terms of distances between symmetric positive definite (SPD) matrices, suggesting a geometric interpretation of the problem. Stemming from this geometric viewpoint, we introduce and analyze a method which utilizes the geometry of the SPD matrix manifold and the invariance properties of its metrics. Most notably we show that these invariances alleviate the need to whiten the input matrices, a common step in many SSA methods which often introduces error. We demonstrate the usefulness of our technique in experiments on both synthetic and real-world data.nonouirechercheInternationa
Comportements du consommateur
No full textIllustré d'études de cas, ce document expose les principaux concepts permettant de décrire et de comprendre le comportement des consommateurs, afin de prendre les meilleures décisions marketing : besoins, implications, apprentissage et mémorisation, persuasion, émotions, expériences et comportements d'achat et de consommation, caractéristiques socio-économiques du consommateur, etcnonouinon-rechercheNationa
Transmettre des savoirs pour innover
No full textRéseau maghrébin des Technolectes REMATE, Université de Carthage, Université Tunis El Manar, Université de la Manouba, Agence Universitaire de la Francophonie AUFnonnonrechercheInternationa
