Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations

DOI10.1134/S1990478914020070zbMath1324.90106OpenAlexW2020455290MaRDI QIDQ5264723

O. Yu. Tsidulko, E. Kh. Gimadi, Yu. V. Glazkov

Publication date: 27 July 2015

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1990478914020070

zbMATH Keywords

asymptotic optimality\(m\)-planar 3-dimensional assignment problem\(m\)-PSP with different weight functionsone-cycle permutationpolynomial approximation algorithm

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (3)

Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph ⋮ An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution ⋮ Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above

This page was built for publication: Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations