1,720,987 research outputs found
Complexity and approximability of the maximum flow problem with minimum quantities
No full textWe consider the maximum flow problem with minimum quantities (MFPMQ), which is a variant of the maximum flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound (a minimum quantity), which may depend on the arc. This problem has recently been shown to be weakly NP -complete even on series-parallel graphs. In this article, we provide further complexity and approximability results for MFPMQ and several special cases. We first show that it is strongly NP -hard to approximate MFPMQ on general graphs (and even bipartite graphs) within any positive factor. On series-parallel graphs, however, we present a pseudo-polynomial time dynamic programming algorithm for the problem. We then study the case that the minimum quantity is the same for each arc in the network and show that, under this restriction, the problem is still weakly NP -complete on general graphs, but can be solved in strongly polynomial time on series-parallel graphs. On general graphs, we present a (2 - 1/lambda)-approximation algorithm for this case, where lambda denotes the common minimum quantity of all arcs. (c) 2013 Wiley Periodicals, Inc
A combined local search and integer programming approach to the traveling tournament problem
No full textThe traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances
Approximation algorithms for TTP(2)
No full textWe consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. It consists of designing a schedule for a sports league of n teams such that the total traveling costs of the teams are minimized. The most important variant of the traveling tournament problem imposes restrictions on the number of consecutive home games or away games a team may have. We consider the case where at most two consecutive home games or away games are allowed. We show that the well-known independent lower bound for this case cannot be reached and present two approximation algorithms for the problem. The first algorithm has an approximation ratio of in the case that n/2 is odd, and of in the case that n/2 is even. Furthermore, we show that this algorithm is applicable to real world problems as it yields close to optimal tournaments for many standard benchmark instances. The second algorithm we propose is only suitable for the case that n/2 is even and n a parts per thousand yen 12, and achieves an approximation ratio of 1 + 16/n in this case, which makes it the first -approximation for the problem
An optimal randomized online algorithm for the -Canadian Traveller Problem on node-disjoint paths
No full textWe consider the -Canadian Traveller Problem, which asks for a shortest path between two nodes and in an undirected graph, where up to edges may be blocked. An online algorithm learns about a blocked edge when reaching one of its endpoints. Recently, it has been shown that no randomized online algorithm can be better than -competitive, even if all --paths are node-disjoint. We show that the bound is tight by constructing a randomized online algorithm for this case that achieves the ratio against an oblivious adversary and is therefore best possible.DFG RTG [1703
A 5.875-approximation for the Traveling Tournament Problem
No full textIn this paper we propose an approximation for the Traveling Tournament Problem which is the problem of designing a schedule for a sports league consisting of a set of teams T such that the total traveling costs of the teams are minimized. It is not allowed for any team to have more than k home-games or k away-games in a row. We propose an algorithm which approximates the optimal solution by a factor of 2+2k/n+k/(n-1)+3/n+3/(2a = 4 and n >= 6. This is the first constant factor approximation for k > 3. We furthermore show that this algorithm is also applicable to real-world problems as it produces solutions of high quality in a very short amount of time. It was able to find solutions for a number of well known benchmark instances which are even better than the previously known ones
A Note on the k-Canadian Traveller Problem
No full textWe consider the online problem k-CTP, which is the problem to guide a vehicle from some site s to some site t on a road map given by a graph G = (V,E) in which up to k (unknown) edges are blocked by avalanches. An online algorithm learns from a blocked edge when reaching one of its endpoints. Thus, it might have to change its route to the target t up to k times. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 2k + 1 and give an easy algorithm which matches this lower bound. Furthermore, we show that randomization can not improve the competitive ratio substantially, by establishing a lower bound of k + 1 for the competitivity of randomized online algorithms against an oblivious adversary. Key words: routing, on-line algorithms, competitiveness
Complexity of the traveling tournament problem
No full textAbstractWe consider the complexity of the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. The problem was supposed to be computationally hard ever since its proposal in 2001. Recently, the first NP-completeness proof has been given for the variant of the problem were no constraints on the number of consecutive home games or away games of a team are considered. The complexity of the original traveling tournament problem including these constraints, however, is still open. In this paper, we show that this variant of the problem is strongly NP-complete when the upper bound on the maximal number of consecutive away games is set to 3
The online knapsack problem with incremental capacity
No full textWe consider an online knapsack problem with incremental capacity. In each time period, a set of items, each with a specific weight and value, is revealed and, without knowledge of future items, it has to be decided which of these items to accept. Additionally, the knapsack capacity is not fully available from the start but increases by a constant amount in each time period. The goal is to maximize the overall value of the accepted items. This setting extends the basic online knapsack problem by introducing a dynamic instead of a static knapsack capacity and is applicable to classic problems such as resource allocation or one-way trading. In contrast to the basic online knapsack problem, for which no competitive algorithms exist, the setting of incremental capacity facilitates the development of competitive algorithms for a bounded time horizon. We provide a competitive analysis of deterministic and randomized online algorithms for the online knapsack problem with incremental capacity and present lower bounds on the competitive ratio achievable by online algorithms for the problem. Most of these lower bounds match the competitive ratios achieved by our online algorithms exactly or differ only by a constant factor.German Research Foundation (DFG) [GRK 1703/1
- …
