15771 research outputs found
Sort by
Une Approche Multi-Agent basée sur la Confiance pour une Découverte Distribuée de Services dans les Réseaux Sociaux
No full textL’importante augmentation du nombre de servicesdisponibles dans les applications sociales(par exemple les réseaux sociaux) a engendréun nouveau défi à la communauté "servicesweb" : la sélection de services à partirdes réseaux sociaux plutôt qu’à partir de registres(par exemple, UDDI, ebXML). Les approchesexistantes à base de registres échouentsouvent à satisfaire les besoins des demandeursde services. Cela est dû au fait que les registressont centralisés et surtout ne prennentpas en considération le contexte social. Danscet article, nous proposons une approche multiagentbasée sur la confiance pour une découvertedistribuée de services dans les réseaux sociaux.Pour ce faire, nous définissons une mesurede confiance comme un concept bidimensionnelqui comprend (i) une confiance en la sociabilitéindiquant si le fournisseur de servicesest socialement digne de confiance et (ii) uneconfiance en l’expertise évaluant la qualité desservices offerts.nonouirechercheNationa
Government as Borrower of First Resort
No full textWe examine optimal supply of safe government bonds accounting for their effect on corporate debt markets. Government bonds are shown to influence leverage under asymmetric information regarding corporate cash flows and safe asset scarcity. Corporations have incentives to issue junk debt in response to safe asset scarcity since uninformed investors then migrate to junk debt markets. Uninformed demand stimulates informed speculation which drives junk debt prices closer to fundamentals, encouraging pooling at high leverage. Acting as borrower of first resort, the government can issue safe bonds which siphon off uninformed demand for risky corporate debt and reduce socially wasteful informed speculation. Thus, government bonds either eliminate pooling at high leverage or improve risk sharing in such equilibria. An optimal supply of government bonds is increasing in both marginal Q and the intrinsic demand for safe assets.nonnonouirechercheInternationa
On the differential approximation of MIN SET COVER
No full textWe present in this paper differential approximation results for MIN SET COVER and MIN WEIGHTED SET COVER. We first show that the differential approximation ratio of the natural greedy algorithm for MIN SET COVER is bounded below by 1.365/Δ and above by 4/(Δ+1), where Δ is the maximum set-cardinality in the MIN SET COVER-instance. Next, we study another approximation algorithm for MIN SET COVER that computes 2-optimal solutions, i.e., solutions that cannot be improved by removing two sets belonging to them and adding another set not belonging to them. We prove that the differential approximation ratio of this second algorithm is bounded below by 2/(Δ+1) and that this bound is tight. Finally, we study an approximation algorithm for MIN WEIGHTED SET COVER and provide a tight lower bound of 1/Δ. Our results identically hold for MAX HYPERGRAPH INDEPENDENT SET in both the standard and the differential approximation paradigms.ouinonouirechercheInternationa
Complexity of the satisfactory partition problem
No full textThe Satisfactory Partition problem consists in deciding if a given graph has apartition of its vertex set into two nonempty parts such that each vertex has at least asmany neighbors in its part as in the other part. This problem was introduced by Gerberand Kobler [GK98, GK00] and further studied by other authors but its complexity remained open until now. We prove in this paper that Satisfactory Partition, as wellas a variant where the parts are required to be of the same cardinality, are NP-complete.However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into knonempty parts (k ≥ 3) is requested.ouinonouirechercheInternationa
On the existence and determination of satisfactory partitions in a graph
No full textThe Satisfactory Partition problem consists in deciding if a given graph has a partition of its vertex set into two nonempty sets V 1,V 2 such that for each vertex v, if v ∈ V i then dVi(v) ³ s(v)dVi(v)s(v), where s(v)≤ d(v) is a given integer-valued function. This problem was introduced by Gerber and Kobler [EJOR 125 (2000), 283–291] for s = é\fracd2 ùs=2d. In this paper we study the complexity of this problem for different values of s.ouinonouirechercheInternationa
On Labeled Traveling Salesman Problems
No full textWe consider labeled Traveling Salesman Problems, defined upon a complete graph of n vertices with colored edges. The objective is to find a tour of maximum (or minimum) number of colors. We derive results regarding hardness of approximation, and analyze approximation algorithms for both versions of the problem. For the maximization version we give a -approximation algorithm and show that it is APX-hard. For the minimization version, we show that it is not approximable within n 1 − ε for every ε> 0. When every color appears in the graph at most r times and r is an increasing function of n the problem is not O(r 1 − ε )-approximable. For fixed constant r we analyze a polynomial-time (r + H r )/2-approximation algorithm (H r is the r-th harmonic number), and prove APX-hardness. Analysis of the studied algorithms is shown to be tight.ouinonouirechercheInternationa
Compact preference representation and Boolean games
No full textGame theory is a widely used formal model for studying strategical interactions between agents. Boolean games (Harrenstein, Logic in conflict, PhD thesis, 2004; Harrenstein et al., Theoretical Aspects of Rationality and Knowledge, pp. 287–298, San Francisco Morgan Kaufmann, 2001) yield a compact representation of 2-player zero-sum static games with binary preferences: an agent’s strategy consists of a truth assignment of the propositional variables she controls, and a player’s preferences are expressed by a plain propositional formula. These restrictions (2-player, zero-sum, binary preferences) strongly limit the expressivity of the framework. We first generalize the framework to n-player games which are not necessarily zero-sum. We give simple characterizations of Nash equilibria and dominated strategies, and investigate the computational complexity of the associated problems. Then, we relax the last restriction by coupling Boolean games with a representation, namely, CP-nets.ouinonouirechercheInternationa
On the probabilistic min spanning tree Problem
No full textWe study a probabilistic optimization model for min spanning tree, where any vertex v i of the input-graph G(V, E) has some presence probability p i in the final instance G′ ⊂ G that will effectively be optimized. Suppose that when this “real” instance G′ becomes known, a spanning tree T, called anticipatory or a priori spanning tree, has already been computed in G and one can run a quick algorithm (quicker than one that recomputes from scratch), called modification strategy, that modifies the anticipatory tree T in order to fit G′. The goal is to compute an anticipatory spanning tree of G such that, its modification for any GG is optimal for G′. This is what we call probabilistic min spanning tree problem. In this paper we study complexity and approximation of probabilistic min spanning tree in complete graphs under two distinct modification strategies leading to different complexity results for the problem. For the first of the strategies developed, we also study two natural subproblems of probabilistic min spanning tree, namely, the probabilistic metric min spanning tree and the probabilistic min spanning tree 1,2 that deal with metric complete graphs and complete graphs with edge-weights either 1, or 2, respectively.ouinonouirechercheInternationa
Évaluation de la qualité d’un processus métier à l’aide d’informations issues de réseaux informels
No full textNous nous intéressons dans cet article à la phase de réversibilité d’un processus métier de gestion de projet externalisé. Nous évaluons une partie de sa qualité : sa robustesse par rapport au risque de perte de connaissance des personnes impliquées dans le processus. Pour cela, nous nous appuyons sur le paradigme Goal-Question-Metric proposant une démarche de gestion de la qualité pour définir des métriques d’évaluation permettant de répondre en partie au besoin opérationnel. Les métriques que nous proposons utilisent des informations issues de l’analyse des réseaux informels sous-jacents aux tâches du processus métier ; ceci permet de tenir compte de la connaissance tacite des personnes. Nous discutons ensuite de quelques perspectives métier en nous appuyant sur les résultats de cette évaluation.We consider the business process of the reversibility stage in an outsourced IT project management. We evaluate a facet of its quality: its robustness w.r.t. the risk of loosing (tacit) knowledge of the persons implied in the process. Based on the Goal-Question-Metric paradigm, we propose an approach for the definition of quality metrics covering the given operational requirements. The metrics we define take tacit knowledge into account, using information from the structural analysis of an informal network (which is a kind of social network).ouinonouirechercheNationa
Lyapunov control of Schrödinger equations: beyond the dipole approximation
No full textWe analyse in this paper the Lyapunov trajectory tracking of the Schrödinger equation for a second order coupling operator. We present a theoretical convergence result; for situations not covered by the theoretical result we propose a numerical approach that is tested and works well in practice.ouinonouirechercheInternationa