tailieunhanh - Reducing offline to online: an example and its applications

We study online versions of maximum weighted hereditary subgraph problems for which the instance is revealed in two clusters. This result can be seen as an inverse version of our previous work. It brings to the fore a hardness gap between online and offline versions of those problems. This result does not apply in the case of maximizing a k-colorable induced subgraph of a given graph. | Yugoslav Journal of Operations Research 13 (2003), Number 1, 3-24 REDUCING OFF-LINE TO ON-LINE: AN EXAMPLE AND ITS APPLICATIONS Marc DEMANGE ESSEC Business School* Cergy-Pontoise Cedex, France demange@ Abstract: We study on-line versions of maximum weighted hereditary subgraph problems for which the instance is revealed in two clusters. We focus on the comparison of these on-line problems with their respective off-line versions. In [3], we have reduced on-line versions to the off-line ones in order to devise competitive analysis for such problems. In this paper, we first devise hardness results pointing out that this previous analysis was tight. Then, we propose a process that allows, for a large class of hereditary problems, to transform an on-line algorithm into an off-line one with improvement of the guarantees. This result can be seen as an inverse version of our previous work. It brings to the fore a hardness gap between on-line and off-line versions of those problems. This result does not apply in the case of maximizing a k colorable induced subgraph of a given graph. For this problem we point out that, contrary to the first case, the on-line version is almost as well approximated as the offline one. Keywords: Combinatorial problems, on-line computation, reductions, hereditary subgraph problem. 1. CONTEXT AND AIMS OF THE PAPER A set-property π , assigning to every finite set V a Boolean value (either true if V satisfies π , or false in the opposite case), is hereditary if, whenever V satisfies π , so does every subset of V . π is called trivial if it is satisfied for only a finite number of sets, or unsatisfied for only a finite number of sets. Heredity is very natural in operations research; a generic example is the case where constraints represent the saturation of a shared resource: it is quite natural that a part of a feasible program * also at CERMSEM, Universit› Paris I, Paris, France. 4 M. Demange / Reducing Off-Line to On-Line: An .

• Quản trị mạng
• Combinatorial problems
• Online computation
• Hereditary subgraph problem
• Inverse version
• Feasible program
• Slow positron beam system
• Simulation program
• Conceptual design
• Simion simulation program
• Building feasible design models
• BMC Geriatrics
• Qualitative research
• Feasible rehabilitation
• Increased understanding
• Rehabilitation participation
• Future situation