We consider two natural generalizations of the Asymmetric Traveling Salesman problem: the k‐Stroll and the k‐Tour problems. The input to the k‐Stroll problem is a directed n‐vertex graph with nonnegative edge lengths, an integer k, as well as two special vertices s and t. The goal is to find a minimum‐length s‐t walk, containing at least k distinct vertices (including the endpoints s,t). The k‐Tour problem can be viewed as a special case of k‐Stroll, where s=t. That is, the walk is required to be a tour, containing some pre‐specified vertex s. When k=n, the k‐Stroll problem becomes equivalent to Asymmetric Traveling Salesman Path, and k‐Tour to Asymmetric Traveling Salesman. Our main result is a polylogarithmic approximation algorithm for the k‐Stroll problem. Prior to our work, only bicriteria (O(log2
k),3)‐approximation algorithms have been known, producing walks whose length is bounded by 3OPT, while the number of vertices visited is Ω(k/log2
k). We also show a simple O(log2
n/loglogn)‐approximation algorithm for the k‐Tour problem. The best previously known approximation algorithms achieved min(O(log3
k),O(log2
n⋅logk/loglogn)) approximation in polynomial time, and O(log2
k) approximation in quasipolynomial time.