Text

Fast Implementation of the Traveling-Salesman-Problem Method for Reordering Columns within Supernodes

In 2017 Pichon et al. introduced an effective method for reordering columns within supernodes based on reformulating the underlying optimization problem as a set of traveling salesman problems (TSPs), one for each supernode. The primary problem with their approach is its cost in time, and the primary bottleneck is computing the TSP distances. We introduce techniques that dramatically reduce the time required by their method. First, we introduce a straightforward technique for reducing the size of a TSP, thereby reducing the number of TSP distances that must be computed and also reducing the cost of computing the TSP tour afterward. Second, we introduce a more complex and efficient algorithm for computing the TSP distances that exploits the fact that the relevant sets induce subtrees in the supernodal elimination tree. (A corrected version is attached.)

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS; Vol.42 No.3 July-September 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1337-1364

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

TRAVELING SALESMAN PROBLEM
SPARSE CHOLESKY FACTORIZATION
SYMBOLIC FACTORIZATION
SUPERNODES
REORDERING WITHIN SUPERNODES

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Mathias Jacquelin, Esmond G. Ng, Barry W. Peyton

Versi lain/terkait

Lampiran Berkas

Komentar