15771 research outputs found
Sort by
Moderate exponential time approximation and branching algorithms
No full textWe study links between approximation, exponential time computation and fixed parameter tractability. In particular, rather than focusing on one particular optimization problem, we tackle the question of finding sufficient conditions for a problem to admit "good" approximation algorithms in exponential time. In particular, we focus on the existence of "approximation schemata" (ratios 1 ± ε for arbitrarily small ε) and we exhibit conditions under which a technique of devising approximate branching algorithms reaches interesting results.nonnonouirechercheInternationa
Payer nuit gravement à la santé : une étude de l’impact du renoncement financier aux soins sur l’état de santé
No full textCet article propose d’analyser des déterminants du renoncement aux soins pour raisons financières puis d’étudier ses conséquences sur l’évolution de l’état de santé quatre ans plus tard à partir des données de l’Enquête Santé ProtectionSociale. L’analyse des déterminants du renoncement montre le rôle important joué par l’accès à une couverture complémentaire, au côté de celui de la situation sociale présente, passée et anticipée. L’analyse montre ensuite que le renoncement aux soins a un effet causal sur la dégradation de l’état de santé ultérieur. Elle suggère ainsi que les difficultés d’accès aux soins contribuent aux inégalités de santé.This article focusses on self-assessed unmet needs for financial reasons. We study its social and economic determinants and its consequences on future health status, from a longitu-dinal dataset: the French Heath, Health care and Insurance Survey (Enquête Santé Protection Sociale). We first show that living standards, access to complementary health insurance and life course factors (past, current and anticipated socioeconomic status) have an impact on self-assessed unmet needs. We then show that self-assessed unmet needs have a detrimental causal effect on future health status,suggesting that financial barriers in access to health care contribute to social health inequalities.nonouirechercheNationa
Liquidity Contagion. The Emerging Sovereign Debt Markets example
No full textFinancial markets are today so interconnected that they are fragile to contagion. Massive investment funds with very short horizons in -and out- flows can generate contagion effects between markets. Since 2010, investors are willing to get a liquid exposure to the EMsovereign debt. As a consequence, some asset management firms started to propose products to track the performance of this asset class. However in that case, the fund manager faces a mismatch of liquidity between assets and liabilities and needs some tools to manage the liquidity of his investments. The main contribution of this paper is the analysis of contagion looking at common market liquidity problems to detect funding liquidity problems. Using the CDS Bond Spread basis as a liquidity indicator and a state space model with time-varying volatility specification, we show that during the 2007-2008 financial crisis, there exist pure contagion effects both in terms of price and liquidity on the emergings overeign debt market.This result has strong implication since the main risk for an asset manager is to get stuck with an unwanted position due to a dry-up of market liquidity.nonouirechercheInternationa
The firefighter problem with more than one firefighter on trees
No full textIn this paper we study the complexity of generalized versions of the firefighter problem on trees, and answer several open questions of Finbow and MacGillivray (2009) [8]. More specifically, we consider the version denoted by Max(S,b)(S,b)-Fire where b≥2b≥2 firefighters are allowed at each time step and the objective is to maximize the number of saved vertices that belong to SS. We also study the related decision problem (S,b)(S,b)-Fire that asks whether all the vertices in SS can be saved using b≥2b≥2 firefighters at each time step.We show that (S,b)(S,b)-Fire is NP-complete for trees of maximum degree b+2b+2 even when SS is the set of leaves. Using this last result, we prove the NP-hardness of Max(S,b)(S,b)-Fire for trees of maximum degree b+3b+3 even when SS is the set of all vertices. On the positive side, we give a polynomial-time algorithm for solving (S,b)(S,b)-Fire and Max(S,b)(S,b)-Fire on trees of maximum degree b+2b+2 when the fire breaks out at a vertex of degree at most b+1b+1. Moreover, we present a polynomial-time algorithm for the Max(S,b)(S,b)-Fire problem (and the corresponding weighted version) for a subclass of trees, namely kk-caterpillars. Finally, we observe that the minimization version of Max(S,b)(S,b)-Fire is not n1−εn1−ε-approximable on trees for any ϵ∈(0,1)ϵ∈(0,1) and b≥1b≥1 if P≠NPP≠NP.nonouirechercheInternationa
The Robust Set Problem: Parameterized Complexity and Approximation
No full textLNCS n°7464In this paper, we introduce the Robust Set problem: given a graph G = (V,E), a threshold function t:V → N and an integer k, find a subset of vertices V′ ⊆ V of size at least k such that every vertex v in G has less than t(v) neighbors in V′. This problem occurs in the context of the spread of undesirable agents through a network (virus, ideas, fire, …). Informally speaking, the problem asks to find the largest subset of vertices with the property that if anything bad happens in it then this will have no consequences on the remaining graph. The threshold t(v) of a vertex v represents its reliability regarding its neighborhood; that is, how many neighbors can be infected before v gets himself infected.We study in this paper the parameterized complexity of Robust Set and the approximation of the associated maximization problem. When the parameter is k, we show that this problem is W[2]-complete in general and W[1]-complete if all thresholds are constant bounded. Moreover, we prove that, if P ≠ NP, the maximization version is not n 1 − ε - approximable for any ε > 0 even when all thresholds are at most two. When each threshold is equal to the degree of the vertex, we show that k -Robust Set is fixed-parameter tractable for parameter k and the maximization version is APX-complete. We give a polynomial-time algorithm for graphs of bounded treewidth and a PTAS for planar graphs. Finally, we show that the parametric dual problem (n − k)-Robust Set is fixed-parameter tractable for a large family of threshold functions.nonouirechercheInternationa
Algorithms for dominating clique problems
No full textWe handle in this paper three dominating clique problems, namely, the decision problem to detect whether a graph has a dominating clique and two optimization versions asking to compute a maximum- and a minimum-size dominating clique of a graph G, if G has a dominating clique. For the three problems we propose exact moderately exponential algorithms with worst-case running time upper bounds improving those by Kratsch and Liedloff [D. Kratsch, M. Liedloff, An exact algorithm for the minimum dominating clique problem, Theoret. Comput. Sci. 385 (1–3) (2007) 226–240]. We then study the three problems in sparse and dense graphs also providing improved running time upper bounds. Finally, we propose some exponential time approximation algorithms for the optimization versions.nonouirechercheInternationa
Définition d’un cadre de conception et d’exécution pour la simulation multi-agent
No full textLa simulation multi-agent est utilisée pour comprendre des systèmes complexes par la reproduction de divers scénarios. Dans les plates-formes de simulation actuelles, la politique d’ordonnancement consiste à contrôler l’activation séquentielle des agents qui exécutent systématiquement la boucle perception - décision - action. Cette approche centrée agent est peu efficace en termes de temps d’exécution et de conception. Nous proposons un nouveau cadre conceptuel et opérationnel EASS dans lequel les agents mutualisent, au sein de l’environnement, les informations et les traitements nécessaires à la mise en œuvre de la politique d’ordonnancement. Cette externalisation dans l’environnement d’une partie de l’activité des agents liée à leurs activations permet l’activation contextuelle. Les principaux avantages de l’activation contextuelle sont un gain d’efficacité en termes de temps d’exécution, et une meilleure flexibilité de la gestion des comportements des agents en termes de conception.Agent-based simulation is used to understand complex systems and to experiment several scenarios. In classical simulation frameworks, a pitfall is the fact that the action phase, based on local agent context analysis, is repeated in each agent at each time cycle during the simulation execution. This analysis inside the agents reduces agent flexibility and limits agent behavior reuse in various simulations. If the designer wants to modify the way the agent reacts to the context, he could not do it without altering the way the agent is implemented because the link between agent context and agent actions is an internal part of the agent. Our proposition, called EASS, is a new agent-based simulation framework, where the context is analyzed by the environment and where agent activation is based on context evaluation. This activation process is called contextual activation. The main advantage of contextual activation is the improvement of complex agent simulation design in terms of flexibility and run-time.ouinonouirechercheNationa
The spinning top metaphor : understanding value misfits and clashes
No full textouinonouirechercheInternationa