2025년 대한수학회 정기총회 및 가을 연구발표회의 일환으로, 워털루대학교(University of Waterloo) 윌리엄 쿡(William Cook) 교수님의 대중강연 "The Traveling Salesman Problem: Package Deliveries, Pub Walks, and Astro Tours"가 개최됩니다. 참가를 원하시는 분께서는 아래 양식을 작성해 주시기 바랍니다.
As part of the 2025 KMS Annual Meeting and Fall Conference, Professor William Cook (University of Waterloo) will deliver a public lecture entitled “The Traveling Salesman Problem: Package Deliveries, Pub Walks, and Astro Tours,” and if you wish to attend, please complete the registration form below.
- 일시 Date & Time: 2025년 10월 22일(수) 오후 7시
- 장소 Venue: 한국과학기술회관 B1 과학기술컨벤션센터 대회의실2 (서울)
Grand Conference Room 2, B1, ST Convention Center, Seoul - 문의처 Contact: 대한수학회 Korean Mathematical Society (kms@kms.or.kr)
- 본 강연은 무료 강연이며, 영어로 진행됩니다. The lecture is free of charge and will be delivered in English.
Abstract: Is it possible to compute the shortest route through a large number of stops? The task, known as the traveling salesman problem, or TSP, arises in many practical contexts, such as guiding a delivery van to your doorstep.
It sounds simple enough, but even a whisper of the TSP strikes fear in the heart of the computing world. A Washington Post article reported it would take "1,000 years to compute the most efficient route between 22 cities.” Claims such as this, however, ignore 70 years of intense study. A 22-city TSP can be handled in a snap with modern methods, even on an iPhone. Indeed, we discuss techniques used to find to precise optimality the shortest walking tour to 81,998 pubs in Korea and to find approximate solutions to visit over 100,000,000 stars.
The general setting is the following. Complexity theory suggests there are limits to the power of general-purpose computational techniques, in engineering, science and elsewhere. But what are these limits and how widely do they constrain our quest for knowledge? The TSP can play a crucial role in this discussion, demonstrating whether or not focused efforts on a single, possibly unsolvable, model will produce results beyond our expectations.
