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., and Protasi, M., Complexity and Approximation (Combinatorial Optimization Problems and Their Approximability Properties), Springer-Verlag, 1999.
Crescenzi, P., Silvestri, R., and Trevisan, L., “To weight or not to weight: where is the question?”, in: Proc. of 4th Israel Symposium on Theory on Computing and Systems, IEEE Computer Society, 1996, 68-77.
Demange, M., “Reducing off-line to on-line: an example and its applications,” Yugoslav Journal of Operations Research, 13(1) (2003) 3-24.
Demange, M., and Paschos, V. Th., “Improved approximations for weighted and unweighted graph problems,” Theory of Computing Systems, 38(6) (2005) 763-787.
Demange, M., and Paschos, Th.V., “Two-steps combinatorial optimization,” in: Proc. of OLCP'01, 2001, 37-44.
Demange, M., Paradon, X., and Paschos, Th.V., “On-line maximum-order induced hereditary subgraph problems,” International Transactions in Operational Research, 12 (2) (2005) 185-201.
Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979.
Halldórsson, M.M., “Approximations of weighted independent set and hereditary subset problems,” Journal of Graph Algorithms and Applications, 4 (1) (2000) 1-16.
Halldórsson, M.M., and Radhakrishnan, J., “Improved approximations of independent set in bounded-degree graphs via subgraph removal,” Nordic Journal of Computing, 1 (4) (1994) 475-492.
Halldórsson, M.M., and Radhakrishnan, J., “Greed is good: approximation of independent set in sparse and bounded-degree graphs,” Algorithmica, 18 (1) (1997) 145-163.
Halldórsson, M.M., “Approximations via partitioning,” JAIST, Japan Advanced Institute of Science and Technology, Japan, 1995.
Håstad, J., “Clique is hard to approximate within n¹⁻ε,” Acta Mathematica, 182 (1999) 105-142.
Paradon, X., “Algorithmique on-line,” Ph.D. Thesis, Université Paris Dauphine, 2000.
Downloads
Published
Issue
Section
License
Copyright (c) 2011 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
