15771 research outputs found
Sort by
Reoptimization of maximum weight induced hereditary subgraph problems
No full textThe reoptimization issue studied in this paper can be described as follows: given aninstance I of some problem Π, an optimal solution O P T for Π in I and an instance I ′ resultingfrom a local perturbation of I that consists of insertions or removals of a small number ofdata, we wish to use O P T in order to solve Π in I ′, either optimally or by guaranteeingan approximation ratio better than that guaranteed by an ex nihilo computation and withrunning time better that that needed for such a computation. We use this setting in order tostudy weighted versions of several representatives of a broad class of problems known in theliterature as maximum induced hereditary subgraph problems. The main problems studiedare max independent set, max k -colorable subgraph, max Pk-free subgraph, maxsplit subgraph and max planar subgraph. We also show, how the techniques presentedallow us to handle also bin packing.ouinonouirechercheInternationa
Single Approximation for Biobjective Max TSP
No full textWe propose an algorithm which returns a single Hamiltonian cycle with performance guarantee on both objectives. The algorithm is analysed in three cases. When both (resp. at least one) objective function(s) fulfill(s) the triangle inequality, the approximation ratio is 512−041 (resp. 83−). When the triangle inequality is not assumed on any objective function, the algorithm is 141+22−027 -approximate.ouinonouirechercheInternationa
Drivers of socially responsible investment in the French financial market
No full textouinonouirechercheInternationa
A multiple criteria sorting method where each category is characterized by several reference actions: The Electre Tri-nC method
No full textThis paper presents Electre Tri-nC, a new sorting method which takes into account several reference actions for characterizing each category. This new method gives a particular freedom to the decision maker in the co-construction decision aiding process with the analyst to characterize the set of categories, while there is no constraint for introducing only one reference action as typical of each category like in Electre Tri-C (Almeida-Dias et al., 2010). As in such a sorting method, this new sorting method is composed of two joint rules. Electre Tri-nC also fulfills a certain number of natural requirements. Additional results on the behavior of the new method are also provided in this paper, namely the ones with respect to the addition or removal of the reference actions used for characterizing a certain category. A numerical example illustrates the manner in which Electre Tri-nC can be used by a decision maker. A comparison with some related sorting procedures is presented and it allows to conclude that the new method is appropriate to deal with sorting problems.ouinonouirechercheInternationa
A note on utility based pricing and asymptotic risk diversification
No full textIn principle, liabilities combining both insurancial risks (e.g. mortality/longevity, crop yield,...) and pure financial risks cannot be priced neither by applying the usual actuar- ial principles of diversification, nor by arbitrage-free replication arguments. Still, it has been often proposed in the literature to combine these two approaches by suggesting to hedge a pure financial payoff computed by taking the mean under the historical/objective probability measure on the part of the risk that can be diversified. Not surprisingly, simple examples show that this approach is typically inconsistent for risk adverse agents. We show that it can nevertheless be recovered asymptotically when the number of sold claims goes to infinity and the absolute risk aversion of the agent goes to zero simultaneously. This follows from a general convergence result on utility indifference prices which is valid for both complete and incomplete financial markets. In particular, if the underlying financial market is complete, the limit price corresponds to the hedging cost of the mean payoff. If the financial market is incomplete but the agent behaves asymptotically as an exponential utility maximizer with vanishing risk aversion, we show that the utility indifference price converges to the expectation of the discounted payoff under the minimal entropy martingale measure.ouinonouirechercheInternationa
Strategizing through Sensemaking Practices: Mapping Out a Real Estate Project
No full textSensemaking practices are a core activity for strategizing in organizations.Managers can use various types of objects to shape sense in a project. Wepropose an integrative framework to analyse the sensemaking practicesat work in a real estate project. Our results provide a better understandingof the micro foundations of strategy and sensemaking.nonouirechercheInternationa
Trust-Based Service Discovery in Multi-relation Social Networks
No full textWith the increasing number of services, the need to locate relevant services remains essential. To satisfy the query of a service requester, available service providers has first to be discovered. This task has been heavily investigated from both industrial and academic perspectives based essentially on registers. However, they completely ignore the contribution of the social dimension. When integrating social trust dimension to service discovery, this task will gain wider credibility and acceptance. If a service requester knows that discovered services are offered by trustworthy providers, he will be more confident. In this paper, we present a new discovery technique based on a social trust measure that ranks service providers belonging to the service requester’s multi-relation social network. The proposed measure is an aggregation of three measures: the social position, the social proximity and the social similarity. To compute these measures, we take into account both semantic and structural knowledge extracted from the multi-relation social network. Semantic information includes service requestor and provider profiles and their interactions. Structural information includes among other the position of service providers in the multi-relation social network graph.nonouirechercheInternationa
Skin in the Game and Moral Hazard
No full textWhat determines equilibrium securitization levels, and should they be regulated? To address these questions we develop a model where originators can exert unobservable effort to increase asset quality, subsequently having private information regarding quality when selling ABS to rational investors. In equilibrium, all originators have low/zero retentions if they are financially constrained and/or prices are su¢ ciently informative. Asymmetric information lowers effort incentives in all equilibria. Effort is promoted by junior retentions, investor sophistication, andinformative prices. Optimal regulation promotes effort while accounting for investor-level externalities. It entails either a menu of junior retentions or a single junior retention with sizedecreasing in price informativeness. Mandated market opacity is only optimal amongst regulations failing to induce originator effort.nonnonouirechercheInternationa
Group Activity Selection Problem
No full textWe consider a setting where one has to organize one or several group activities for a set of agents. Each agent will participate in at most one activity, and her preferences over activities depend on the number of participants in the activity. The goal is to assign agents to activities based on their preferences. We put forward a general model for this setting, which is a natural generalization of anonymous hedonic games. We then focus on a special case of our model, where agents’ preferences are binary, i.e., each agent classifies all pairs of the form ”(activity, group size)” into ones that are acceptable and ones that are not. We formulate several solution concepts for this scenario, and study them from the computational point of view, providing hardness results for the general case as well as efficient algorithms for settings where agents’ preferences satisfy certain natural constraints.nonouirechercheInternationa
Solving breakthrough with Race Patterns and Job-Level Proof Number Search
No full textbreakthrough is a recent race-based board game usually played on a 8×8 board. We describe a method to solve 6×5 boards based on (1) race patterns and (2) an extension of (JLPNS).Using race patterns is a new domain-specific technique that allows early endgame detection. The patterns we use enable us to prune positions safely and statically as far as 7 moves from the end.For the purpose of solving Breakthrough we also present an extension of the parallel algorithm (JLPNS), viz. when a PN search is used as the underlying job. In this extension, partial results are regularly sent by the clients to the server.nonouirechercheInternationa