n-Tokyoites' loop-line commuter problem

DOI10.1016/S0012-365X(02)00747-1MaRDI QIDQ1402069zbMATH OpenOpenAlexFDO

Authors Liang Chen, Naoyuki Tokuda

Publication date 19 August 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(02)00747-1

zbMATH Keywords

Algorithm designingData assignment problemGilmore-GomoryHungarian algorithmmatching problemWeighted bipartite matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Review text

The paper deals with the \(n\)-Tokyoites' loop-line computer problem which comprises a special class of the more general Gilmore-Gomory weighted bipartite matching problem where weights assigned to arcs are given in terms of integrals of some functions. The algorithm proposed by the authors runs in \(O(n^2)\) time and is faster than the more popularly used Hungarian-type \(O(n^3)\) algorithms applicable to the more general weighted bipartite matching problem. Moreover, the algorithm developed by the authors allows to impose some novel angular constraints which find an immediate application not only on the \(n\)-Tokyoites' loop-line commuter problem itself, but also to the data association problem involved in the multisensor-multitarget tracking process and to the specifically defined Gilmore-Gomory's original TSP problem.

Recommendations

• scientific article; zbMATH DE number 91028
• An efficient algorithm for the bipartite matching problem
• On some matching problems arising in vehicle scheduling models
• Faster scaling algorithms for general graph matching problems
• scientific article; zbMATH DE number 1003236

Cited in

(2)

• A study on two measurements-to-tracks data assignment algorithms
• Data association approaches in bearings-only multi-target tracking

This page was built for publication: \(n\)-Tokyoites' loop-line commuter problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1402069)