×

zbMATH — the first resource for mathematics

Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph. (English) Zbl 1338.05263
Summary: Some hard-to solve combinatorial problems of finding several disjoint discrete structures in complete weighted graph are considered. Efficient algorithms with performance guarantees are constructed for the Euclidean \(m\)-Peripatetic Salesman Problem, \( m\)-Weighted Clique Problem and \( m\)-Layer Planar three-index Assignment Problem.
MSC:
05C85 Graph algorithms (graph-theoretic aspects)
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baburin, A. E.; Gimadi, E. Kh., On the asymptotic optimality of an algorithm for solving the maximum m-PSP in a multidimensional Euclidean space, Proc. Steklov Inst. Math., 272, Suppl. 1, 1-13, (2011) · Zbl 1230.65065
[2] Burkard, R.; Dell’Amico, M.; Martello, S., Assignments, (2009), SIAM Philadelphia, 382 p
[3] De Brey, M. J.D.; Volgenant, A., Well-solved cases of the 2-PSP, Optimization, 39, 3, 275-293, (1997) · Zbl 0886.90120
[4] De Kort, J. B.J. M., Lower bounds for symmetric K-PSP, Optimization, 22, 1, 113-122, (1991) · Zbl 0717.90048
[5] De Kort, J. B.J. M., Upper bounds for the symmetric 2-PSP, Optimization, 23, 4, 357-367, (1992) · Zbl 0814.05066
[6] De Kort, J. B.J. M., A branch and bound algorithm for symmetric 2-PSP, EJOR, 70, 229-243, (1993) · Zbl 0799.90114
[7] Dinits, E. A.; Kronrod, M. A., One algorithm for solving assignment problem, Dokl. AN SSSR, 189, 1, 23-25, (1969)
[8] Duchenne, E.; Laporte, G.; Semet, F., Branch-and-cut algorithms for the undirected m-PSP, EJOR, 162, 700-712, (2005) · Zbl 1067.90136
[9] Eremin, Ivan; Gimadi, Edward; Kelmanov, Alexander; Pyatkin, Artem; Khachay, Mikhail, 2-approximation algorithm for finding a clique with minimum weight of vertices and edges, Proc. Steklov Inst., 284, Supp. l, (2014)
[10] Fon-Der-Flaass, D. G., Array of distinct representatives - a very simple NP-complete problem, Discrete Math., 171, 1-3, 295-298, (1997) · Zbl 0879.68040
[11] Frieze, A. M., Complexity of a 3-dimensional assignment problem, Eur. J. Oper. Res., 13, 2, 161-164, (1983) · Zbl 0507.90057
[12] Gimadi, E. Kh., Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space, Proc. Steklov Inst. Math., 263, Suppl. 2, 56-67, (2008) · Zbl 1178.90335
[13] Gimadi, E. Kh.; Kelmanov, A. V.; Pyatrin, A. V.; Khachay, M. Y., Efficient algorithms with performance estimates for some problems of finding several disjoint cliques in complete undirected weighted graph, Trudy IMM UrO RAN, 20, 2, 99-112, (2014), (in Russian)
[14] E.Kh. Gimadi, Approximation efficient algorithms with performance guarantees for some hard routing problems, in; Proc. of the II International Conference ‘Optimzation and Applications’ OPTIMA-2011, Petrovac/Montenegro, 2011, pp. 98-101.
[15] Gimadi, Edward Kh., On some probability inequalities for some discrete optimization problems, (Operations Research Proceedings, Selected Papers. International Conference OR 2005, (2006), Springer Bremen, Berlin), 283-289 · Zbl 1114.90454
[16] E.Kh. Gimadi, N.M. Korkishko, On some modifications of three index planar assignment problem, in: Proc. Discrete optimization methods in production and logistics (DOM’2004), The second international workshop, Omsk, 2004, pp. 161-165.
[17] Gimadi, E. Kh.; Glazkov, Yu. V., An asymptotically optimal algorithm for one modification of planar three-index assignment problem, J. Appl. Ind. Math., 1, 4, 442-452, (2007), (Pleiades Publ. Ltd)
[18] Gimadi, E. Kh.; Glazkov, Y. V.; Tsidulko, O. Y., Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations, J. Appl. Ind. Math., 8, 2, 208-217, (2014) · Zbl 1324.90106
[19] Hopcroft, J. E.; Karp, R. M., An \(n^{5 / 2}\) algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 4, 225-231, (1973) · Zbl 0266.05114
[20] Kleinschmidt, P.; Schannath, H., A strongly polynomial algorithm for the transportation problem, Math. Prog., 68, 1-13, (1995) · Zbl 0833.90084
[21] Krarup, J., The peripatetic salesman and some related unsolved problems, (Combinatorial Programming: Methods and Applications (Proc. NATO Advanced Study Inst., Versailles, 1974), (1975), Reidel Dordrecht), 173-178
[22] Ore, O., Theory of graphs, (1962), AMS Providence, 279 p
[23] (Petrov, V. V., Limit Theorems of Probability Theory, Sequences of Independent Random Variables, (1995), Clarendon Press Oxford), 304
[24] Roskind, J.; Tarjan, R. E., A note on finding minimum-cost edge-disjoint spanning trees, Math. Oper. Res., 10, 4, 701-708, (1985) · Zbl 0581.90093
[25] A.I. Serdukov, An asymptotically optimal algorithm for solving Max Euclidean TSP. Metodi Celochislennoi Optimizacii (Upravliaemie Sistemi), Novosibirsk. n. 27, 1987, p. 79-87 (in Russian).
[26] Spieksma, F. C.R., Multi-index assignment problems: complexity, approximation, applications, Nonlinear Assignment Problems, Algorithms and Applications, (2000), Kluwer Acad. Publ. Dordrecht, pp. 1-12 · Zbl 1029.90036
[27] (Gutin, G.; Punnen, A. P., The Traveling Salesman Problem and its Variations, (2002), Kluwer Academic Publishers Dordrecht, Boston, London), 830 · Zbl 0996.00026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.