TAILIEUCHUNG - Online computation and maximum - weighted hereditary subgraph problems
In this paper we study the online version of maximum-weighted hereditary subgraph problems. In our online model, the final instance (a graph with n vertices) is revealed in t clusters, 2 ≤ t ≤ n . We first focus on an online version of the maximum - weighted hereditary subgraph problem. Then, we deal with the particular case of the independent set problem. We are interested in two types of results: The competitive ratio guaranteed by the online algorithm and hardness results that account for the difficulty of the problems and for the quality of algorithms developed to solve them. | Yugoslav Journal of Operations Research 21 (2010), Number 1, 11-28 DOI: ON-LINE COMPUTATION AND MAXIMUM-WEIGHTED HEREDITARY SUBGRAPH PROBLEMS Marc DEMANGE ESSEC Business School, Bucharest, Romania, demange@ Bernard KOUAKOU Université de Montréal, Montréal, Canada, Eric SOUTIF CEDRIC, CNAM, Paris, France, Received: June 2009 / Accepted: March 2011 Abstract: In this paper1 we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance (a graph with n vertices) is revealed in t clusters, 2 ≤ t ≤ n . We first focus on an on-line version of the maximumweighted hereditary subgraph problem. Then, we deal with the particular case of the independent set problem. We are interested in two types of results: the competitive ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problems and for the quality of algorithms developed to solve them. Keywords: On-line algorithms, hereditary property, independent set, competitive ratio. MSC: 68Q25, 68W40, 90C27, 90C35 1. INTRODUCTION On-line computation aims to solve combinatorial optimization problems with the constraint that the instance is not a priori completely known before one begins to solve it. In other words, the data set is revealed step-by-step and one has, at each step, to 1 A preliminary extended abstract appeared in the Proceedings of 16th International Symposium on Algorithms and Computation, ISAAC 2005. 12 M. Demange, B. Kouakou, E. Soutif / On-Line Computation irrevocably decide on the final solution dealing with this step. On-line algorithms concern a large class of problems subjected to time constraints (decisions are made before one knows all the data). In [13], a general framework for on-line problems is drawn. An on-line problem is defined by: - a combinatorial optimization problem P, - a set of rules R detailing how the final
đang nạp các trang xem trước
