Abstract
A parameterized problem Π can be considered as a set of pairs (I,k) where I is the main part and k (usually an integer) is the parameter. Π is called fixed-parameter tractable (FPT) if membership of (I,k) in Π can be decided in time O(f(k)|I|c), where |I| denotes the size of I, f(k) is a computable function, and c is a constant independent of k and I. An algorithm of complexity O(f(k)|I|c) is called a fixed-parameter algorithm.
It often happens that although a problem is FPT, the practitioners prefer to use imprecise heuristic methods to solve the problem in the real-world situation simply because of the fact that the heuristic methods are faster. In this paper we argue that in this situation a fixed-parameter algorithm for the given problem may be still of a considerable practical use. In particular, the fixed-parameter algorithm can be used to evaluate the approximation quality of heuristic approaches.
To demonstrate this way of application of fixed-parameter algorithms, we consider the problem of extracting a maximum-size reflected network in a linear program. We evaluate a state-of-the-art heuristic SGA and two variations of it with a new heuristic and with an exact algorithm. The new heuristic and algorithm use fixed-parameter tractable procedures. The new heuristic turned out to be of little practical interest, but the exact algorithm is of interest when the network size is close to that of the linear program especially if the exact algorithm is used in conjunction with SGA. Another conclusion which has a large practical interest is that some variant of SGA can be the best choice because in most cases it returns optimal solutions; previously it was disregarded because comparing to the other heuristics it improved the solution insignificantly at the cost of much larger running times.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abu-Khzam, F.N., Fellows, M.R., Langston, M., Suters, W.H.: Crown Structures for Vertex Cover Kernelization. Theory of Computing Systems 41, 411–430 (2007)
Abu-Khzam, F.N., Langston, M., Shanbhag, P., Symons, C.T.: Scalable Parallel Algorithms for FPT Problems. Algorithmica 45, 269–284 (2006)
Baker, B.M., Maye, P.J.: A Heuristic for Finding Embedded Network Structure in Mathematical Programmes. Europ. Jour. Oper. Res. 67, 52–63 (1993)
Bartholdi, J.J.: A Good Submatrix is Hard to Find. Oper. Res. Letters 1, 190–193 (1982)
Betzler, N., Hüffner, F., Niedermeier, R.: Optimal edge deletions for signed graph balancing. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 297–310. Springer, Heidelberg (2007)
Bixby, R.E., Fourer, R.: Finding Embedded Network Rows in Linear Programs I. Extraction Heuristics. Manag. Science 34, 342–376 (1988)
Bixby, R.E., Cunningham, W.H.: Converting Linear Programs to Network Problems. Math. Oper. Res. 5, 321–356 (1980)
Brown, G.G., Wright, W.G.: Automatic Identification of Embedded Network Rows in Large-Scale Optimization Models. Math. Prog. 29, 41–56 (1984)
Chen, J., Kanj, I.A., Xia, G.: Simplicity is beauty: Improved upper bounds for vertex cover. Tech. Report TR05-008, DePaul University, Chicago IL (2005)
DasGupta, B., Enciso, G.A., Sontag, E.D., Zhang, Y.: Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. In: Àlvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol. 4007, pp. 253–264. Springer, Heidelberg (2006)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)
Gülpınar, N., Gutin, G., Mitra, G., Maros, I.: Detecting Embedded Pure Network Structures by Using GUB and Independent Set Algorithms. Comput. Optim. Applic. 15, 235–247 (2000)
Gülpınar, N., Gutin, G., Mitra, G., Zverovitch, A.: Extracting Pure Network Submatrices in Linear Programs Using Signed Graphs. Discrete Applied Mathematics 137, 359–372 (2004)
Gutin, G., Zverovitch, A.: Extracting pure network submatrices in linear programs using signed graphs, Part 2. Communications of DQM 6, 58–65 (2003)
Hansen, P.: Labelling Algorithms for Balance in Signed Graphs. In: Problémes Combinatoires et Theorie des Graphes, Colloq. Internat., Orsay, pp. 215–217 (1976); Colloques Internat. du CNRS 260 Paris (1978)
Harary, F., Kabell, J.A.: A Simple Algorithm to Detect Balance in Signed Graphs. Math. Social Science 1, 131–136 (1980-1981)
Heller, I., Tompkins, C.B.: An Extension of a Theorem of Dantzig’s. In: Kuhn, H.W., Tucker, A.W. (eds.) Linear Inequalities and Related Systems. Annals Math. Studies, vol. 38, pp. 247–252. Princeton Univ. Press, Princeton (1956)
Hsu, A.C., Fourer, R.: Identification of Embedded Network Structure in Linear Programming Models. GSIA Working Paper, 1997-58
Hüffner, F.: Algorithm Engineering for Optimal Graph Bipartization. Journal of Graph Algorithms and Applications 13, 77–98 (2009)
Kottler, S., Kaufmann, M., Sinz, C.: Computation of Renameable Horn Backdoors. In: Kleine Büning, H., Zhao, X. (eds.) SAT 2008. LNCS, vol. 4996, pp. 154–160. Springer, Heidelberg (2008)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)
Paschos, V.T.: A Δ/2-Approximation for the Maximum Independent Set Problem. Inform. Proc. Let. 44, 11–13 (1992)
Razgon, I., O’Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. Journal of Computer and System Sciences (in press)
Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research Letters 32, 299–301 (2004)
Zaslavsky, T.: Signed Graphs. Discete Applied Math. 4, 47–74 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gutin, G., Karapetyan, D., Razgon, I. (2009). Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs. In: Chen, J., Fomin, F.V. (eds) Parameterized and Exact Computation. IWPEC 2009. Lecture Notes in Computer Science, vol 5917. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11269-0_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-11269-0_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11268-3
Online ISBN: 978-3-642-11269-0
eBook Packages: Computer ScienceComputer Science (R0)