| 1. |
- Baltz, Andreas, et al.
(författare)
-
Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection
- 2015
-
Ingår i: Journal of the Operational Research Society. - : Informa UK Limited. - 0160-5682 .- 1476-9360. ; 66:4, s. 615-626
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce and study the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection (TSP-MTWHS), which generalises the well-known Travelling Salesman Problem with Time Windows and the recently introduced Travelling Salesman Problem with Hotel Selection. The TSP-MTWHS consists in determining a route for a salesman (eg, an employee of a services company) who visits various customers at different locations and different time windows. The salesman may require a several-day tour during which he may need to stay in hotels. The goal is to minimise the tour costs consisting of wage, hotel costs, travelling expenses and penalty fees for possibly omitted customers. We present a mixed integer linear programming (MILP) model for this practical problem and a heuristic combining cheapest insert, 2-OPT and randomised restarting. We show on random instances and on real world instances from industry that the MILP model can be solved to optimality in reasonable time with a standard MILP solver for several small instances. We also show that the heuristic gives the same solutions for most of the small instances, and is also fast, efficient and practical for large instances.
|
|
| 2. |
- Baltz, Andreas, et al.
(författare)
-
Construction of Sparse Asymmetric Connectors
- 2003
-
Ingår i: Proceedings of European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2003). - Berlin-Heidelberg : Springer Berlin/Heidelberg.
-
Konferensbidrag (refereegranskat)
|
|
| 3. |
- Baltz, Andreas, et al.
(författare)
-
Constructions of Sparse Asymmetric Connectors with Number Theoretic Methods
- 2005
-
Ingår i: Networks. - : John Wiley & Sons. - 0028-3045 .- 1097-0037. ; 45:3, s. 119-124
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of connecting a set I of n inputs to a set O of N outputs (n ≤ N) by as few edges as possible such that for every injective mapping f : I → O there are n vertex disjoint paths from i to f(i) of length k for a given k . For k = Ω(log N + logn) Oruς (1994) gave the presently best (n,N)-connector with O(N+n·log n) edges. For k=2 and N the square of a prime, Richards and Hwang (1985) described a construction using edges. We show by a probabilistic argument that an optimal (n,N)-connector has Θ (N) edges, if for some ε>0. Moreover, we give explicit constructions based on a new number theoretic approach that need at most edges for arbitrary choices of n and N. The improvement we achieve is based on applying a generalization of the Erdös-Heilbronn conjecture on the size of restricted sums.
|
|
| 4. |
- Glazik, Christian, et al.
(författare)
-
Bounds for Static Black-Peg AB Mastermind
- 2017
-
Ingår i: COCOA 2017. - Cham : Springer Berlin/Heidelberg. - 9783319711461 - 9783319711478 ; , s. 409-424
-
Konferensbidrag (refereegranskat)abstract
- Mastermind is a famous two-player game introduced by M. Meirowitz (1970). Its combinatorics has gained increased interest over the last years for different variants.In this paper we consider a version known as the Black-Peg AB Game, where one player creates a secret code consisting of c colors on p <= c pegs, where each color is used at most once. The second player tries to guess the secret code with as few questions as possible. For each question he receives the number of correctly placed colors. In the static variant the second player doesn't receive the answers one at a time, but all at once after asking the last question. There are several results both for the AB and the static version, but the combination of both versions has not been considered so far. The most prominent case is n:=p=c, where the secret code and all questions are permutations. The main result of this paper is an upper bound of O(n^{1.525}) questions for this setting. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of \Omega(n\log n). Furthermore, we complement the upper bound for p=c by an optimal (\lceil 4c/3 \rceil -1)-strategy for the special case p=2 and arbitrary c >= 2 and list optimal strategies for six additional pairs (p,c) .
|
|
| 5. |
- Glazik, Christian, et al.
(författare)
-
Bounds for the Static Permutation Mastermind game
- 2021
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 344:3
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper' we introduce a variant of Mastermind, which we call Static Permutation Mastermind and which is defined as follows. One player creates a secret code, called secret, consisting of n colors on n pegs, where each color is used exactly once. The second player tries to determine the secret with as few questions as possible, where each question is a possible secret and all questions are asked at once. After having asked all questions, he receives for each question the number of correctly placed colors and has one more try to determine the secret. The main result of this paper is an upper bound of O(n1.525) questions. It is proved by a distinction of pairs of possible secrets with low and high Hamming distance. For pairs with a low Hamming distance we construct questions using certain arithmetic progressions. For pairs with a high Hamming distance we estimate the size of a vertex cover in a suitable hypergraph. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of Ω(nlogn).
|
|
| 6. |
- Jäger, Gerold, et al.
(författare)
-
Improved Approximation Algorithms for Maximum Graph Partitioning Problems
- 2005
-
Ingår i: Journal of combinatorial optimization. - : Kluwer Academic Publishers. - 1382-6905 .- 1573-2886. ; 10:2, s. 133-167
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the design of approximation algorithms for a number of maximum graph partitioning problems, among others MAX-k-CUT, MAX-k-DENSE-SUBGRAPH, and MAX-k-DIRECTED-UNCUT. We present a new version of the semidefinite relaxation scheme along with a better analysis, extending work of Halperin and Zwick (2002). This leads to an improvement over known approximation factors for such problems. The key to the improvement is the following new technique: It was already observed by Han, Ye, Zhang (2002) that a parameter-driven choice of the random hyperplane can lead to better approximation factors than obtained by Goemans and Williamson (1995). But it remained difficult to find a ”good” set of parameters. In this paper, we analyze random hyperplanes depending on several new parameters. We prove that a suboptimal choice of these parameters can be obtained by the solution of a linear program which leads to the desired improvement of the approximation factors. In this fashion a more systematic analysis of the semidefinite relaxation scheme is obtained.
|
|
| 7. |
- Jäger, Gerold, et al.
(författare)
-
Improved Approximation Algorithms for Maximum Graph Partitioning Problems
- 2004
-
Ingår i: Proceedings of 24th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2004). - Berlin-Heidelberg : Springer Berlin/Heidelberg. ; , s. 348-359
-
Konferensbidrag (refereegranskat)abstract
- In this paper we improve the analysis of approximation algorithms based on semidefinite programming for the maximum graph partitioning problems MAX-k-CUT, MAX-k-UNCUT, MAX-k-DIRECTEDCUT, MAX-k-DIRECTED-UNCUT, MAX-k-DENSE-SUBGRAPH, and MAX-k-VERTEX-COVER. It was observed by Han, Ye, Zhang (2002) and Halperin, Zwick (2002) that a parameter-driven random hyperplane can lead to better approximation factors than obtained by Goemans and Williamson (1994). Halperin and Zwick could describe the approximation factors by a mathematical optimization problem for the above problems for and found a choice of parameters in a heuristic way. The innovation of this paper is twofold. First, we generalize the algorithm of Halperin and Zwick to cover all cases of k, adding some algorithmic features. The hard work is to show that this leads to a mathematical optimization problem for an optimal choice of parameters. Secondly, as a key-step of this paper we prove that a sub-optimal set of parameters is determined by a linear program. Its optimal solution computed by CPLEX leads to the desired improvements. In this fashion a more systematic analysis of the semidefinite relaxation scheme is obtained which leaves room for further improvements.
|
|
| 8. |
- Jäger, Gerold, et al.
(författare)
-
Solving Generalized Maximum Dispersion with Linear Programming
- 2007
-
Ingår i: Proceedings of 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM 2007). - Berlin-Heidelberg : Springer Berlin-Heidelberg. ; , s. 1-10
-
Konferensbidrag (refereegranskat)abstract
- The Generalized Maximum Dispersion problem asks for a partition of a given graph into p vertex-disjoint sets, each of them having at most k vertices. The goal is to maximize the total edge-weight of the induced subgraphs. We present the first LP-based approximation algorithm.
|
|
