|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Approximation Algorithms for the Black and White Traveling Salesman Problemтезисы доклада
- Авторы: Bhattacharia B., Hu Y., Kononov A.
- Сборник: Computing and Combinatorics. COCOON 2007
- Серия: Lecture Notes in Computer Science
- Том: 4598
- Тезисы
- Год издания: 2007
- Издательство: Springer Berlin
- Местоположение издательства: Heidelberg, Germany
- Первая страница: 559
- Последняя страница: 567
- DOI: 10.1007/978-3-540-73545-8_54
- Аннотация: The black and white traveling salesman problem (BWTSP) is to find the minimum cost hamiltonian tour of an undirected complete graph G, containing black and white vertices, subject to two restrictions: the number of white vertices, and the cost of the subtour between two consecutive black vertices are bounded. This paper focuses on designing approximation algorithms for the BWTSP in a graph satisfying the triangle inequality. We show that approximating the tour which satisfies the length constraint is NP-hard. We then show that the BWTSP can be approximated with tour cost (4-3/2Q) times the optimal cost, when at most Q white vertices appear between two consecutive black vertices. When exactly Q white vertices appear between two consecutive black vertices, the approximation bound can be slightly improved to (4-15/8Q). This approximation bound is further improved to 2.5 when Q = 2.
- Добавил в систему: Кононов Александр Вениаминович