Approximation Algorithms for the Directed k-Tour and k-Stroll Problems

Source

• Evernote/Papers/Approximation Algorithms for the Directed k-Tour and k-Stroll Problems.md

Summary

이 논문은 비대칭 외판원 문제(ATSP)의 일반화인 지향 그래프 k-Stroll 및 k-Tour 문제에 대한 근사 알고리즘을 제시합니다. 주요 결과로 k-Stroll 문제에 대해 다중대수(polylogarithmic) 근사 알고리즘을 제안하여, 기존에 알려진 bicriteria 근사 알고리즘의 한계를 극복했습니다. 또한 k-Tour 문제에 대해 O(log^2 n / log log n) 근사 알고리즘을 제시하며, 기존 다항 시간 알고리즘의 근사 비율을 개선했습니다.

Key Points

• k-Stroll 문제: s-t 경로상에서 최소 k개의 서로 다른 정점을 방문하는 최소 길이 경로 찾기
• k-Tour 문제: k-Stroll의 특수한 경우(s=t)로, 특정 정점을 포함하는 최소 길이 순회 경로 찾기
• 기존 k-Stroll 알고리즘은 bicriteria (O(log^2 k), 3)-근사였으나, 본 논문은 polylogarithmic 근사 알고리즘을 제안
• k-Tour 문제에 대해 O(log^2 n / log log n) 근사 알고리즘 제안 (기존 다항 시간 알고리즘보다 개선)
• k=n 일 때 k-Stroll은 ATSP Path, k-Tour는 ATSP 와 동치

Related

• k-원자성 검증 문제 (k-atomicity-verification problem) 연구

• Coherent image selection using a fast approximation to the generalized traveling salesman problem

• Backward Path Growth for Efficient Mobile Sequential Recommendation

• Knapsack Problem 정리 (CANUYES)

• K-RBMs를 이용한 다중 비선형 부분공간 학습

• k-parity 테스트의 비적응적 쿼리 복잡도

• 여행하는 세일즈맨 문제 (TSP)

• 정적 네트워크에서의 최단 경로 쿼리 (Shortest-path queries in static networks)

• Adaptive Speculative Processing of Out-of-Order Event Streams

• KAIST 전산학과 영화 ‘Travelling Salesman’ 상영 공지

• 가시성 그래프의 미해결 문제들 (Unsolved problems in visibility graphs)

• The Number of Huffman Codes, Compact Trees, and Sums of Unit Fractions

• 최소 일관 부분집합 커버 문제 (MCSC): 데이터 마이닝의 최소화 관점

• Entropic Inequalities and Marginal Problems

• Sequential Pattern Mining: Approaches and Algorithms

• Convergence and approximation in potential games

• 문제 - 일렬 연결망