پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شمارهها | 1,877 |
| تعداد مقالات | 15,278 |
| تعداد مشاهده مقاله | 43,732,100 |
| تعداد دریافت فایل اصل مقاله | 17,564,536 |
Complexity indices for the travelling salesman problem and data mining | ||
| Transactions on Combinatorics | ||
| مقاله 6، دوره 1، شماره 1، خرداد 2012، صفحه 35-43 اصل مقاله (436.8 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2012.723 | ||
| نویسنده | ||
| Dragos Cvetković* | ||
| چکیده | ||
| we extend our previous work on complexity indices for the travelling salesman problem (TSP), summarized in cite{CvCK3}, using graph spectral techniques of data mining. A complexity index is an invariant of an instance $I$ by which we can predict the execution time of an exact algorithm for TSP for $I$. We consider the symmetric travelling salesman problem with instances $I$ represented by complete graphs $G$ with distances between vertices (cities) as edge weights (lengths). Intuitively, the hardness of an instance $G$ depends on the distribution of short edges within $G$. Therefore we consider some short edge subgraphs of $G$ (minimal spanning tree, critical connected subgraph, and several others) as non-weighted graphs and several their invariants as potential complexity indices. Here spectral invariants (e.g. spectral radius of the adjacency matrix) play an important role since, in general, there are intimate relations between eigenvalues and the structure of a graph. Since hidden details of short edge subgraphs really determine the hardness of the instance, we use techniques of data mining to find them. In particular, spectral clustering algorithms are used including information obtained from the spectral gap in Laplacian spectra of short edge subgraphs. | ||
| کلیدواژهها | ||
| Travelling Salesman Problem؛ Spectral clustering algorithms؛ Hamiltonian cycle | ||
| مراجع | ||
|
B. Ashok and T.K. Patra (2010) Locating phase transitions in computationally hard problems J. Physics, to appear
D. Cvetkovi\' c, M. \v Cangalovi\' c and V. Kova\v cevi\' c-Vuj\v
ci\' c (1999) Semidefinite programming methods for the symmetric
travelling salesman problem Integer Programming and
Combinatorial Optimization, Proc. 7th Internat. IPCO Conf.Graz,
Austria, June 1999, Lecture Notes Comp. Sci. 1610, Springer,
Berlin , 126-136
D. Cvetkovi\' c, M. \v Cangalovi\' c and V. Kova\v cevi\' c-Vuj\v
ci\' c (1999) Complexity indices for the travelling salesman problem
based on a semidefinite relaxation SYM-OP-IS '99, Proc. XXVI
Yugoslav Symp. Operations Research, Beograd , 177-180
D. Cvetkovi\' c, M. \v Cangalovi\' c and V. Kova\v cevi\' c-Vuj\v
ci\' c (2004) Optimization and highly informative graph invariants Two Topics in Mathematics, ed. B.Stankovi\' c, Zbornik radova
10(18), Matemati\v cki institut SANU, Beograd , 5-39
D. Cvetkovi\'c, P. Rowlinson and S. K. Simi\'c (2009) An Introduction to the Theory of Graph Spectra Cambridge
University Press, Cambridge
D. Cvetkovi\' c and S.K. Simi\' c (2011) Graph spectra in computer
science Linear Algebra Appl. 434, 1545-1562
M. Fiedler (1973) Algebraic connectivity of graphs Czech. J. Math. 23 (98), 298-305
G. Gutin and A. Punnen (2002) The Travelling Salesman
Problem and Its Variations Kluwer Academic Publishers,
Dordrecht
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnoy Kan and D.B. Shmoys (1985) The Traveling Salesman Problem John Wiley and Sons,
Chichester - New York - Brisbane - Toronto - Singapore
K. Ko, P. Orponen, U. Sch\" oning and O. Watanabe (1986) What is a
hard instance of a computational problem ? Structure in
Complexity Theory. Conf. 1986, Lecture Notes in Computer Science,
Springer , 197-217
U. von Luxburg (2007) A tutorial on spectral clustering Stat.
Comput. 17, 395-416
C.R. Reeves and A.V. Eremeev (2004) Statistical analysis of local
search landscapes J. Oper. Res. Soc. 55, 687-693
B.D. Reyck and W. Herroelen (1996) On the use of the complexity index as
a measure of complexity in activity networks Europ. J. Oper.
Res. 91, 347-366
R. Sawilla (2008) A survey of data mining of graphs using spectral
graph theory Defence R\&D Canada, Ottawa, Technical Memorandum
TM 2008-317, Ottawa
| ||
|
آمار تعداد مشاهده مقاله: 5,287 تعداد دریافت فایل اصل مقاله: 3,448 |
||