On-line computation and maximum-weighted hereditary subgraph problems
DOI:
https://doi.org/10.2298/YJOR1101011DKeywords:
On-line algorithms, hereditary property, independent set, competitive ratioAbstract
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.References
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M. (1999) Complexity and approximation: Combinatorial optimization problems and their approximability properties. Berlin: Springer-Verlag
Crescenzi, P., Silvestri, R., Trevisan, L. (1996) To weight or not to weight: where is the question?. u: Israel symposium on theory on computing and systems (IV), proc, IEEE Computer Society, str. 68-77
Demange, M., Paschos, V.Th. (2005) Improved approximations for weighted and unweighted graph problems. Theory of Computing Systems, 38(6): 763
Demange, M., Paschos, Th.V. (2001) Two-steps combinatorial optimization. u: OLCP01, proc, str. 37-44
Demange, M., Paradon, X., Paschos, V.Th. (2005) On-line maximum order induced hereditary sub graph problems. International Transactions in Operational Research, 12 (2), 185-201
Demange, M. (2003) Reducing off-line to on-line: An example and its applications. Yugoslav Journal of Operations Research, vol. 13, br. 1, str. 3-24
Garey, M.R., Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NPCompletness. San Francisco: CA. Freeman
Halldorsson, M.M. (2000) Approximations of weighted independent set and hereditary subset problems. J Graph Algorithms Appl., 4, 1-
Halldórsson, M.M., Radhakrishnan, J. (1994) Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Nordic J. Comput., 1(4): 475
Halldórsson, M.M., Radhakrishnan, J. (1997) Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica, 18(1): 145-163
Halldórsson, M.M. (1995) Approximations via partitioning. Japan Advanced, Institute of Science and Technology (JAIST)
Hastad, J. (1999) Clique is hard to approximate within $nsp {1-epsilon}$. Acta Math, 182, 1, 105-142
Paradon, X. (2000) Algorithmique on-line. Paris: Université Paris Dauphine, Ph. D.Thesis
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
