15771 research outputs found
Sort by
Approximation algorithms for some vehicle routing problems
No full textWe study vehicle routing problems with constraints on the distance traveled by each vehicle or on the number of vehicles. The objective is either to minimize the total distance traveled by vehicles or to minimize the number of vehicles used. We design constant differential approximation algorithms for kVRP. Note that, using the differential bound for METRIC 3VRP, we obtain the randomized standard ratio This is an improvement of the best-known bound of 2 given by Haimovich et al. (Vehicle Routing Methods and Studies, Golden, Assad, editors, Elsevier, Amsterdam, 1988). For natural generalizations of this problem, called EDGE COST VRP, VERTEX COST VRP, MIN VEHICLE and kTSP we obtain constant differential approximation algorithms and we show that these problems have no differential approximation scheme, unless P=NP.ouinonouirechercheInternationa
Issues in Multiagent Resource Allocation
No full textThe allocation of resources within a system of autonomous agents, that not only havepreferences over alternative allocations of resources but also actively participate in com-puting an allocation, is an exciting area of research at the interface of Computer Scienceand Economics. This paper is a survey of some of the most salient issues in MultiagentResource Allocation. In particular, we review various languages to represent the pref-erences of agents over alternative allocations of resources as well as different measuresof social welfare to assess the overall quality of an allocation. We also discuss pertinentissues regarding allocation procedures and present important complexity results. Ourpresentation of theoretical issues is complemented by a discussion of software packagesfor the simulation of agent-based market places. We also introduce four major applica-tion areas for Multiagent Resource Allocation, namely industrial procurement, sharingof satellite resources, manufacturing control, and grid computingouinonouirechercheInternationa
La détention d'assurance vie selon l'âge : une étude économétrique
No full textNotre communication se propose d’expliciter les comportements de détention de produits d’assurance vie selon l’âge, à partir d’une exploitation économétrique de l’enquête Patrimoine 1998 de l’Insee. Plus précisément, nous cherchons à identifier les déterminants socio-économiques et financiers significatifs de cette détention (en particulier l’âge, le revenu, le patrimoine, la situation matrimoniale, le statut professionnel et le niveau d’études). En suivant la logique développée dans un article précédent, nous estimons un modèle Probit pour expliquer la probabilité de détention de produits d’assurance, et des moindres carrés ordinaires pour expliquer les montants de richesse détenue en produits d’assurance, en fonction des déterminants identifiés précédemment.ouinonouirechercheNationa
An alternative approach of corporate social disclosure analysis
No full textThis paper proposes an alternative approach to corporate social disclosure analysis in order to link social information disclosed and corporate social performance. A survey of the literature dealing with description and explanation of corporate social disclosure practices underlines the inconsistency of the findings. As most of these researches use quantitative content analysis, we discuss the relevance of this instrument. In order to improve the description of corporate social practices as well as the explanation of the link between these disclosures and corporate social performance, we propose a qualitative approach, based on Carroll's social responsibility typology. A study on fifteen French companies, using both approaches, outlines the interest of this alternative method.ouinonouirechercheInternationa
Reasoning under inconsistency: A forgetting-based approach
No full textIn this paper, a fairly general framework for reasoning from inconsistent propositional bases is defined. Variable forgetting is used as a basic operation for weakening pieces of information so as to restore consistency. The key notion is that of recoveries, which are sets of variables whose forgetting enables restoring consistency. Several criteria for defining preferred recoveries are proposed, depending on whether the focus is laid on the relative relevance of the atoms or the relative entrenchment of the pieces of information (or both). Our framework encompasses several previous approaches as specific cases, including reasoning from preferred consistent subsets, and some forms of information merging. Interestingly, the gain in flexibility and generality offered by our framework does not imply a complexity shift compared to these specific cases.ouinonouirechercheInternationa
Winner Determination in Sequential Majority Voting
No full textHyderabad, IndePreferences can be aggregated using voting rules.We consider here the family of rules which performa sequence of pairwise majority comparisons between two candidates. The winner thus depends onthe chosen sequence of comparisons, which can berepresented by a binary tree. We address the difficulty of computing candidates that win for sometrees, and then introduce and study the notion offair winner, i.e. candidates who win in a balancedtree. We then consider the situation where we lackcomplete informations about preferences, and determine the computational complexity of computing winners in this case.ouinonouirechercheInternationa
When Market Illiquidity Generates Volume
No full textWe develop a model of the daily return-volume relationship which incorporates information and liquidity shocks. First, we distinguish between two trading strategies, information-based and liquidity-based trading and suggest that their respective impacts on returns and volume should be modeled differently. Second, we integrate the microstructure setting of Grossman-Miller (1988) with the information flow perspective of Tauchen-Pitts (1983) and derive a modified MDH model with two latent factors related to information and liquidity. Our model explains how the liquidity frictions can increase the daily traded volume, in the presence of liquidity arbitragers. Finally, we propose a stock-specific liquidity measure using daily return and volume observations of FTSE100 stocks.ouinonouirechercheInternationa
How hard is it to Control Sequential Elections via the Agenda?
No full textVoting on multiple related issues is an importantand difficult problem. The key difficulty is that thenumber of alternatives is exponential in the numberof issues, and hence it is infeasible for the agentsto rank all the alternatives. A simple approach is tovote on the issues one at a time, in sequence; however, a drawback is that the outcome may dependon the order in which the issues are voted upon anddecided, which gives the chairperson some controlover the outcome of the election because she canstrategically determine the order. While this is undeniably a negative feature of sequential voting, inthis paper we temper this judgment by showing thatthe chairperson’s control problem is, in most cases,computationally hard.ouinonouirechercheInternationa
An efficient implementation for the 0-1 multi-objective knapsack problem
No full textIn this paper, we present an approach, based on dynamic programming, for solving 0-1 multi-objective knapsack problems. The main idea of the approach relies on the use of several complementary dominance relations to discard partial solutions that cannot lead to new non-dominated criterion vectors. This way, we obtain an efficient method that outperforms the existing methods both in terms of CPU time and size of solved instances. Extensive numerical experiments on various types of instances are reported. A comparison with other exact methods is also performed. In addition, for the first time to our knowledge, we present experiments in the three-objective case.ouinonouirechercheInternationa
Negotiating over small bundles of resources
No full textWhen rational but myopic agents negotiate over the exchange of indivisible resources, any restriction to the negotiation protocol may prevent the system from convergingto a socially optimal allocation in the general case. This paper addresses this issue by analysing how the confinement tocertain classes of utility functions can enable agents to moveto an optimal allocation by negotiating over small bundlesof items at a time. In particular, we consider so-called k-separable domains, where the full set of resources can bedivided into several preferentially independent bundles oflimited cardinality.ouinonouirechercheInternationa