Search

Transportation networks frequently employ hub-and-spoke network architectures to route flows between many origin and destination pairs. Hub facilities work as switching points for flows in large networks. In this study, we focus on a problem, called the single allocation hub-and-spoke network design problem. In the problem, the goal is to allocate each non-hub node to exactly one of the given hub nodes so as to minimize the total transportation cost. The problem is essentially equivalent to another combinatorial optimization problem, called the metric labeling problem. The metric labeling problem was first introduced by Kleinberg and Tardos in 2002, motivated by application to segmentation problems in computer vision and related areas. In this study, we deal with a case where the set of hubs forms a star, which is encountered especially in telecommunication networks. We propose a polynomial-time randomized approximation algorithm for the problem, whose approximation ratio is less than 5.281. Our algorithms solve a linear relaxation problem and apply dependent rounding procedures. [ABSTRACT FROM AUTHOR]

The modularity is the best known and widely used quality function for community detection in graphs. We investigate the approximability of the modularity maximization problem and some related problems. We first design a polynomial-time 0.4209-additive approximation algorithm for the modularity maximization problem, which improves the current best additive approximation error of 0.4672. Our theoretical analysis also demonstrates that the proposed algorithm obtains a nearly-optimal solution for any instance with a high modularity value. We next design a polynomial-time 0.1660-additive approximation algorithm for the maximum modularity cut problem. Finally, we extend our algorithm to some related problems. [ABSTRACT FROM AUTHOR]

A 2.75-approximation algorithm is proposed for the unconstrained traveling tournament problem, which is a variant of the traveling tournament problem. For the unconstrained traveling tournament problem, this is the first proposal of an approximation algorithm with a constant approximation ratio. In addition, the proposed algorithm yields a solution that meets both the no-repeater and mirrored constraints. Computational experiments show that the algorithm generates solutions of good quality. [ABSTRACT FROM AUTHOR]

This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose a new lower bound for the traveling tournament problem, and construct a randomized approximation algorithm yielding a feasible solution whose approximation ratio is less than 2+(9/4)/( n−1), where n is the number of teams. Additionally, we propose a deterministic approximation algorithm with the same approximation ratio using a derandomization technique. For the traveling tournament problem, the proposed algorithms are the first approximation algorithms with a constant approximation ratio, which is less than 2+3/4. [ABSTRACT FROM AUTHOR]

This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose an approximation algorithm for the traveling tournament problem with the constraints such that both the number of consecutive away games and that of consecutive home games are at most k. When k≤5, the approximation ratio of the proposed algorithm is bounded by (2 k−1)/ k+O( k/ n) where n denotes the number of teams; when k>5, the ratio is bounded by (5 k−7)/(2 k)+O( k/ n). For k=3, the most investigated case of the traveling tournament problem to date, the approximation ratio of the proposed algorithm is 5/3+O(1/ n); this is better than the previous approximation algorithm proposed for k=3, whose approximation ratio is 2+O(1/ n). [ABSTRACT FROM AUTHOR]