Parameterized algorithms and complexity for the traveling purchaser problem and its variants

Mingyu Xiao (), Jianan Zhang () and Weibo Lin ()
Additional contact information
Mingyu Xiao: University of Electronic Science and Technology of China
Jianan Zhang: University of Electronic Science and Technology of China
Weibo Lin: Huawei Technologies Co., Ltd.

Journal of Combinatorial Optimization, No 0, 17 pages

Abstract: Abstract The traveling purchaser problem (TPP), a generalization of the traveling salesman problem, is to determine a tour of suppliers and purchase needed products from suppliers while minimizing the traveling and purchasing cost. This problem finds applications in the routing and scheduling contexts and its variants with different constraints have been widely studied. Motivated by the phenomenon that most real-world instances of TPP have a small parameter (such as the number of suppliers, the number of products to purchase, and others), we study TPP and its variants from the view of parameterized complexity. We show that TPP and some variants are fixed-parameter tractable by taking the number k of products or the number m of suppliers as the parameter, and W[2]-hard by taking the number q of visited suppliers as the parameter. Furthermore, we implement some of our fixed-parameter tractable algorithms to show that they are practically effective when the parameters are not very large.

Keywords: Traveling purchaser problem; Fixed-parameter tractable; Dynamic programming; Parameterized complexity (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00608-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00608-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00608-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().