On-line computation and maximum-weighted hereditary subgraph problems (Q2853213)

Online 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. Therefore, decisions must be made before all the data are known. The performance of an online algorithm is measured by the so-called competitive ratio. The maximum weighted hereditary subgraph problem consists in finding a maximum-weighted subgraph of a given weighted graph \(G\), satisfying a non-trivial hereditary property, such as clique, or maximum independent set. A central question in this work is how it is possible to exploit (polynomial-time) algorithms in order to devise (polynomial-time) online algorithms and, moreover, is it possible to transfer performance guarantees from the offline to the online framework? The main idea of the proposed algorithm can be described as follows: at each step, a solution of the problem restricted to the new cluster is computed by using the offline approximation algorithm (the subroutine) and then either the whole solution is included (if its value is sufficiently good) or rejected (in the opposite case). Such an algorithm is called a threshold algorithm. Lower bounds on the competitive ratio for a class of algorithms (including threshold ones) are identified and hardness results (that account for the difficulty of the problems and for the quality of algorithms developed to solve them) are derived.