umu.sePublications
Change search
Refine search result
1 - 50 of 50
Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Rows per page
• 5
• 10
• 20
• 50
• 100
• 250
Sort
• Standard (Relevance)
• Author A-Ö
• Author Ö-A
• Title A-Ö
• Title Ö-A
• Publication type A-Ö
• Publication type Ö-A
• Issued (Oldest first)
• Created (Oldest first)
• Last updated (Oldest first)
• Disputation date (earliest first)
• Disputation date (latest first)
• Standard (Relevance)
• Author A-Ö
• Author Ö-A
• Title A-Ö
• Title Ö-A
• Publication type A-Ö
• Publication type Ö-A
• Issued (Oldest first)
• Created (Oldest first)
• Last updated (Oldest first)
• Disputation date (earliest first)
• Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
• 1.
Christian-Albrechts Universität Kiel.
Christian-Albrechts Universität Kiel. Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics. Christian-Albrechts Universität Kiel. Christian-Albrechts Universität Kiel.
Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection2015In: Journal of the Operational Research Society, ISSN 0160-5682, E-ISSN 1476-9360, Vol. 66, no 4, p. 615-626Article in journal (Refereed)

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.
Christian-Albrechts Universität Kiel, Germany.
Christian-Albrechts Universität Kiel, Germany. Christian-Albrechts Universität Kiel, Germany.
Construction of Sparse Asymmetric Connectors2003In: Proceedings of European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2003), 2003Conference paper (Refereed)
• 3.
Christian-Albrechts-Universität Kiel, Germany.
Christian-Albrechts-Universität Kiel, Germany. Christian-Albrechts-Universität Kiel, Germany.
Constructions of Sparse Asymmetric Connectors2003In: Proceedings of 23rd Conference of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2003) / [ed] P.K. Lodaya and J. Radhakrishnan, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2003, p. 13-22Conference paper (Refereed)
• 4.
Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany. Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
Constructions of Sparse Asymmetric Connectors with Number Theoretic Methods2005In: Networks, ISSN 0028-3045, E-ISSN 1097-0037, Vol. 45, no 3, p. 119-124Article in journal (Refereed)

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 $\in \mathbb{N}$. For k = Ω(log N + log$^{2}$n) 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 $N\left[\sqrt{n+5/4-1/2}\right] + n\left[\sqrt{n+5/4-1/2} \right]\sqrt{N}$edges. We show by a probabilistic argument that an optimal (n,N)-connector has Θ (N) edges, if $n\leq N^{1/2-\varepsilon}$for some ε>0. Moreover, we give explicit constructions based on a new number theoretic approach that need at most $N\left[\sqrt{3n/4} \right]+2n\left[\sqrt{3n/4} \right]\left[\sqrt{N} \right]$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.

• 5.
School of Medicine, Washington University, United States.
Computer Science Institute, University of Halle-Wittenberg, Germany. Department of Biology, Washington University, United States. Department of Computer Science/Department of Genetics, Washington University, United States.
How frugal is mother nature with haplotypes?2009In: Bioinformatics, ISSN 1367-4803, E-ISSN 1367-4811, Vol. 25, no 1, p. 68-74Article in journal (Refereed)

Motivation: Inference of haplotypes from genotype data is crucial and challenging for many vitally important studies. The first, and most critical step, is the ascertainment of a biologically sound model to be optimized. Many models that have been proposed rely partially or entirely on reducing the number of unique haplotypes in the solution.

Results: This article examines the parsimony of haplotypes using known haplotypes as well as genotypes from the HapMap project. Our study reveals that there are relatively few unique haplotypes, but not always the least possible, for the datasets with known solutions. Furthermore, we show that there are frequently very large numbers of parsimonious solutions, and the number increases exponentially with increasing cardinality. Moreover, these solutions are quite varied, most of which are not consistent with the true solutions. These results quantify the limitations of the Pure Parsimony model and demonstrate the imperative need to consider additional properties for haplotype inference models. At a higher level, and with broad applicability, this article illustrates the power of combinatorial methods to tease out imperfections in a given biological model.

• 6.
Computer Science Institute, University of Halle Wittenberg, Germany .
Computer Science Institute, University of Halle Wittenberg, Germany . Computer Science Institute, University of Halle Wittenberg, Germany . Computer Science Institute, University of Halle Wittenberg, Germany . Computer Science Institute, University of Halle Wittenberg, Germany .
Effective Heuristics for Large Euclidean TSP Instances Based on Pseudo Backbones2009In: Proceedings of 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009) / [ed] Sonia Cafieri, Antonio Mucherino, Giacomo Nannicini, Fabien Tarissan and Leo Liberti, 2009, p. 3-6Conference paper (Refereed)

We present two approaches for the Euclidean TSP which compute high quality tours for large instances. Both approaches are based on pseudo backbones consisting of all common edges of good tours. The first approach starts with some pre-computed good tours. Using this approach we found record tours for seven VLSI instances. The second approach is window based and constructs from scratch very good tours of huge TSPinstances, e. g., the World TSP.

• 7.
Computer Science Institute, University of Halle-Wittenberg, Germany.
Computer Science Institute, University of Halle-Wittenberg, Germany. Computer Science Institute, University of Halle-Wittenberg, Germany. Computer Science Institute, University of Halle-Wittenberg, Germany.
Effective Tour Searching for TSP by Contraction of Pseudo Backbone Edges2009In: Proceedings of 5th International Conference on Algorithmic Aspects in Information and Management (AAIM 2009) / [ed] A. Goldberg and Y. Zhou, Berlin-Heidelberg: Springer , 2009, p. 175-187Conference paper (Refereed)

We introduce a reduction technique for the well-known TSP. The basic idea of the approach consists of transforming a TSP instance to another one with smaller size by contracting pseudo backbone edges computed in a preprocessing step, where pseudo backbone edges are edges which are likely to be in an optimal tour. A tour of the small instance can be re-transformed to a tour of the original instance. We experimentally investigated TSP benchmark instances by our reduction technique combined with the currently leading TSP heuristic of Helsgaun. The results strongly demonstrate the effectivity of this reduction technique: for the six VLSI instances xvb13584, pjh17845, fnc19402, ido21215, boa28924, and fht47608 we could set world records, i.e., find better tours than the effective reduction of the problem size so that we can search the more important tour subspace more intensively.

• 8.
Computer Science Institute, Christian-Albrechts-University of Kiel, Germany.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
The b-Matching Problem in Hypergraphs: Hardness and Approximability2012In: Proceedings of 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012) / [ed] Guohui Lin, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2012, p. 200-211Conference paper (Refereed)

In this paper we analyze the maximum cardinality $b$-matching problem in $l$-uniform hypergraphs with respect to the complexity class MAX-SNP, where $b$-matching is defined as follows: for given $b\in\mathbb{N}$ and a hypergraph $\mathcal{H}=(V,\varepsilon)$ a subset $M_{b}\subseteq\varepsilon$ with maximum cardinality is sought so that no vertex is contained in more than $b$ hyperedges of $M_{b}$. We show that if the maximum degree of the vertices is bounded by a constant $B\in\mathbb{N}$, this problem has no approximation scheme, unless $\mathcal{P}=\mathcal{N}\mathcal{P}$. This result generalizes a result of Kann from $b=1$ to the case that $b\in\mathbb{N}$ with $0. Furthermore, we extend a result of Srivastav and Stangier, who gave an approximation algorithm for the unweighted b-matching problem.

• 9.
Martin-Luther-University Halle-Wittenberg, Germany and GISA GmbH, D-06112 Halle (Saale), Germany.
Martin-Luther-University Halle-Wittenberg, Germany. Martin-Luther-University Halle-Wittenberg, Germany and Christian-Albrechts-University Kiel, Germany. Martin-Luther-University Halle-Wittenberg, Germany. Martin-Luther-University Halle-Wittenberg, Germany.
Finding Good Tours for Huge Euclidean TSP Instances by Iterative Backbone Contraction2010In: Proceedings of 6th International Conference on Algorithmic Aspects in Information and Management (AAIM 2010) / [ed] B. Chen, Berlin-Heidelberg: Springer , 2010, Vol. 6124, p. 119-130Conference paper (Refereed)

This paper presents an iterative, highly parallelizable approach to find good tours for very large instances of the Euclidian version of the well-known Traveling Salesman Problem (TSP). The basic idea of the approach consists of iteratively transforming the TSP instance to another one with smaller size by contracting pseudo backbone edges. The iteration is stopped, if the new TSP instance is small enough for directly applying an exact algorithm or an efficient TSP heuristic. The pseudo backbone edges of each iteration are computed by a window based technique in which the TSP instance is tiled in non-disjoint sub-instances. For each of these sub-instances a good tour is computed, independently of the other sub-instances. An edge which is contained in the computed tour of every sub-instance (of the current iteration) containing this edge is denoted to be a pseudo backbone edge. Paths of pseudo-backbone edges are contracted to single edges which are fixed during the subsequent process.

• 10. Fischer, Anja
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Computational Recognition of RNA Splice Sites by Exact Algorithms for the Quadratic Traveling Salesman Problem2015In: Computation, E-ISSN 2079-3197, Vol. 3, no 2, p. 285-298Article in journal (Refereed)

One fundamental problem of bioinformatics is the computational recognition of DNA and RNA binding sites. Given a set of short DNA or RNA sequences of equal length such as transcription factor binding sites or RNA splice sites, the task is to learn a pattern from this set that allows the recognition of similar sites in another set of DNA or RNA sequences. Permuted Markov (PM) models and permuted variable length Markov (PVLM) models are two powerful models for this task, but the problem of finding an optimal PM model or PVLM model is NP-hard. While the problem of finding an optimal PM model or PVLM model of order one is equivalent to the traveling salesman problem (TSP), the problem of finding an optimal PM model or PVLM model of order two is equivalent to the quadratic TSP (QTSP). Several exact algorithms exist for solving the QTSP, but it is unclear if these algorithms are capable of solving QTSP instances resulting from RNA splice sites of at least 150 base pairs in a reasonable time frame. Here, we investigate the performance of three exact algorithms for solving the QTSP for ten datasets of splice acceptor sites and splice donor sites of five different species and find that one of these algorithms is capable of solving QTSP instances of up to 200 base pairs with a running time of less than two days.

• 11. Fischer, Anja
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Exact algorithms and heuristics for the Quadratic Traveling Salesman Problem with an application in bioinformatics2014In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 166, p. 97-114Article in journal (Refereed)

In this paper we introduce an extension of the Traveling Salesman Problem (TSP), which is motivated by an important application in bioinformatics. In contrast to the TSP the costs do not only depend on each pair of two nodes traversed in succession in a cycle but on each triple of nodes traversed in succession. This problem can be formulated as optimizing a quadratic objective function over the traveling salesman polytope, so we call the combinatorial optimization problem quadratic TSP (QTSP). Besides its application in bioinformatics, the QTSP is a generalization of the Angular-Metric TSP and the TSP with reload costs. Apart from the TSP with quadratic cost structure we also consider the related Cycle Cover Problem with quadratic objective function (QCCP). In this work we present three exact solution approaches and several heuristics for the QTSP. The first exact approach is based on a polynomial transformation to a TSP, which is then solved by standard software. The second one is a branch-and-bound algorithm that relies on combinatorial bounds. The best exact algorithm is a branch-and-cut approach based on an integer programming formulation with problem-specific cutting planes. All heuristical approaches are extensions of classic heuristics for the TSP. Finally, we compare all algorithms on real-world instances from bioinformatics and on randomly generated instances. In these tests, the branch-and-cut approach turned out to be superior for solving the real-world instances from bioinformatics. Instances with up to 100 nodes could be solved to optimality in about ten minutes.

• 12.
Faculty to Economics Sciences, University of Groningen, the Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine. Department of Computer Science, Royal Holloway University of London, UK and Department of Computer Science, University of Haifa, Israel. Computer Science Institute, University of Halle-Wittenberg, Germany.
Improving the Performance of Greedy Heuristics for TSPs Using Tolerances2007In: Communications in Dependability and Quality Management, Vol. 10, no 1, p. 52-70Article in journal (Refereed)

In this paper we introduce three greedy algorithms for the traveling salesman problem. These algorithms are unique in that they use arc tolerances, rather than arc weights, to decide whether or not to include an arx in a solution. We report extensive computational experiments on benchmark instances that clearly demonstrate that our tolerance-based algorithms outperform their weight-based counterpart. Along with other papers dealing with the Assignment Problem, this paper indicates that the potential for using tolerance-based algorithms for various optimization problems is high and motivates further investigation of the approach. We recommend one of our algorithms as a significantly better alternative to the weight-based greedy, which is often used to produce initial TSP tours.

• 13.
Faculty of Economic Sciences, University of Groningen, The Netherlands. Department of Computer Science, Royal Holloway University of London, UK and Department of Computer Science, University of Haifa, Israel. Computer Science Institute, University of Halle-Wittenberg, Germany.
Tolerance-based algorithms for the traveling salesman problem2008In: Mathematical Programming and Game Theory for Decision Making / [ed] S.K. Neogy, R.B. Bapat, A.K. Das, and T. Parthasarathy, New Jersey: World Scientific, 2008, p. 47-59Chapter in book (Refereed)

Most research on algorithms for combinatorial optimization use the costs of the elements in the ground set for making decisions about the solutions that the algorithms would output. For traveling salesman problems, this implies that algorithms generally use arc lengths to decide on whether an arc is included in a partial solution or not. In this paper we study the eect of using element tolerances for making these decisions. We choose the traveling salesman problem as a model combinatorial optimization problem and propose several greedy algorithms for it based on tolerances. We report extensive computational experiments on benchmark instances that clearly demonstrate that our tolerance-based algorithms outperform their weight-based counterpart. This indicates that the potential for using tolerance-based algorithms for various optimization problems is high and motivates further investigation of the approach.

• 14.
Christian-Albrechts Universität Kiel.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics. Christian-Albrechts Universität Kiel. Christian-Albrechts Universität Kiel.
Bounds for Static Black-Peg AB Mastermind2017In: Proceedings of 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017), Springer Berlin/Heidelberg, 2017Conference paper (Refereed)

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) .

• 15.
Department of Econometrics and Operations Research, University of Groningen, The Netherlands.
Computer Science Institute, Martin-Luther-University, Halle-Wittenberg, Germany.
How To Make a Greedy Heuristic for the Asymmetric Traveling Salesman Problem Competitive2005Report (Refereed)

It is widely confirmed by many computational experiments that a greedy type heuristics for the Traveling Salesman Problem (TSP) produces rather poor solutions except for the Euclidean TSP. The selection of arcs to be included by a greedy heuristic is usually done on the base of cost values. We propose to use upper tolerances of an optimal solution to one of the relaxed Asymmetric TSP (ATSP) to guide the selection of an arc to be included in the final greedy solution. Even though it needs time to calculate tolerances, our computational experiments for the wide range of ATSP instances show that tolerance based greedy heuristics is much more accurate and faster than previously reported greedy type algorithms.

• 16.
Faculty of Economics and Business, University of Groningen, The Netherlands.
Computer Science Institute, University of Halle-Wittenberg, D-06099 Halle (Saale), Germany.
The Computational Efficiency of Ji-Lee-Li Algorithm for the Assignment Problem2008In: Algorithmic Operations Research, ISSN 1718-3235, Vol. 3, no 1, p. 79-81Article in journal (Refereed)

Ji et al. have conjectured that using the matrix form (to represent a basic solution) instead of the Simplex tableau in the dual Simplex method will lead to an algorithm with the time complexity comparable to the Hungarian algorithm for solving the Assignment Problem. In this note we show that both the time complexity and the CPU times of the Ji et al. algorithm are far away from being competitive to the Hungarian algorithm.

• 17.
Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
University of Halle-Wittenberg, Computer Science Institute, Germany. University of Halle-Wittenberg, Computer Science Institute, Germany.
Some Basics on Tolerances2006In: Proceedings of 2nd International Conference on Alghorithmic Aspects in Information and Management (AAIM 2006) / [ed] S.-W. Cheng and C.K. Poon, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2006, p. 194-206Conference paper (Refereed)

In this paper we deal with sensitivity analysis of combinatorial optimization problems and its fundamental term, the tolerance. For three classes of objective functions (Σ,∏,MAX) we give some basic properties on upper and lower tolerances. We show that the upper tolerance of an element is well defined, how to compute the upper tolerance of an element, and give equivalent formulations when the upper tolerance is +∞ or > 0. Analogous results are given for the lower tolerance and some results on the relationship between lower and upper tolerances are given.

• 18.
Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
Computer Science Institute, University of Halle-Wittenberg, Germany. Computer Science Institute, University of Halle-Wittenberg, Germany.
Tolerance Based Contract-or-Patch Heuristic for the Asymmetric TSP2006In: Proceedings of 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN 2006) / [ed] T. Erlebach, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2006, p. 86-97Conference paper (Refereed)

In this paper we improve the quality of a recently suggested class of construction heuristics for the Asymmetric Traveling Salesman Problem (ATSP), namely the Contract-or-Patch heuristic. Our improvement is based on replacing the selection of each path to be contracted after deleting a heaviest arc from each short cycle in an Optimal Assignment Problem Solution (OAPS) by contracting a single arc from a short cycle in an OAPS with the largest upper tolerance with respect to one of the relaxed ATSP. The improved algorithm produces higher-quality tours than all previous COP versions and is clearly outperforming all other construction heuristics on robustness.

• 19.
Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
Computer Science Institute, University of Halle-Wittenberg, Germany. Computer Science Institute, University of Halle-Wittenberg, Germany.
Tolerances Applied in Combinatorial Optimization2006In: Journal of Computer Science, ISSN 1549-3636, E-ISSN 1552-6607, Vol. 2, no 9, p. 716-734Article in journal (Refereed)

In this paper we deal with sensitivity analysis of combinatorial optimization problems and its fundamental term, the tolerance. For three classes of objective functions (Σ,II,MAX) we give some basic properties on upper and lower tolerances. We show that the upper tolerance of an element is well defined, how to compute the upper tolerance of an element, and give equivalent formulations when the upper tolerance is +∞ or > 0. Analogous results are given for the lower tolerance and some results on the relationship between lower and upper tolerances are given.

• 20.
Mathematisches Seminar Christian-Albrechts-Universität zu Kiel, Germany.
A New Algorithm for Computing the Smith Normal Form and its Implementation on Parallel Machines2004In: Proceedings of 6th Workshop on Advances in Parallel and Distributed Computation Models, International Parallel and Distributed Processing Symposium (IPDPS 2004), IEEE Press, 2004Conference paper (Refereed)

Smith normal form computation is important in many topics, e.g. group theory and number theory. For matrices over the rings Z and F2 [x], we introduce a new Smith normal form algorithm, called Triangular Band Matrix Algorithm, which first computes the Hermite Normalform and then step by step the diagonal form and the Smith normal form. In comparison to the Kannan Bachem Algorithm, which computes the Smith normal form by alternately computing the Hermite normal form and the left Hermite normal form, the theoretical advantage is, that we only once apply the expensive Hermite normal form step. We parallelize the Triangular Band Matrix Algorithm and get a better complexity analysis than for previous parallel algorithms, like the Kannan Bachem Algorithm and the Hartley Hawkes Algorithm. In the part, which is different to the Kannan Bachem Algorithm, the Triangular Band Matrix Algorithm leads to a better efficiency and smaller execution times, even for large example matrices.

• 21.
University of Essen.
Algorithmen zur Berechnung der Smith-Normalform und deren Implementation auf Parallelrechnern2001Doctoral thesis, monograph (Other academic)
• 22.
Computer Science Institute, University of Kiel, Germany.
An Effective SAT encoding for Magic Labeling2010In: Proceedings of 9th Cologne/Twente workshop on graphs and combinatorial optimization (CTW 2010) / [ed] U. Faigle, R. Schrader, and D. Herrmann, 2010, p. 97-100Conference paper (Refereed)
• 23.
Department of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, Missouri 63130-4899, USA.
An Efficient Algorithm for Graph Bisection of Triangularizations2007In: Applied Mathematical Sciences, ISSN 1312-885X, E-ISSN 1314-7552, Vol. 1, no 25, p. 1203-1215Article in journal (Refereed)

Graph bisection is an elementary problem in graph theory. We consider the best known experimental algorithms and introduce a new algorithm called Longest-Path-Algorithm. Applying this algorithm to the cluster tree generation of hierarchical matrices, arising for example in discretizations of partial equations, we show that this algorithm outperforms previous algorithms.

• 24.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
An Optimal Strategy for Static Mastermind with Two Pegs2016In: Proceedings of 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016), Springer Berlin/Heidelberg, 2016, p. 670-682Conference paper (Refereed)

Mastermind is a famous two-player game which has attracted much attention in literature within the last years. In this work we investigate the static (also called non-adaptive) variant of Mastermind. The principal rule is that the codemaker has to choose a secret consisting of p pegs and c colors for each peg and the codebreaker may give a number of guesses at once, where for each guess he receives information from the codemaker. Using this information he has a final guess for the correct secret. The aim of the game is to minimize the number of guesses. Whereas Goddard has investigated the static version of original Mastermind in 2003, we do such an investigation of its black-peg variant, where the received information consists only of a number of black pegs which corresponds to the number of pegs matching in the corresponding question and the secret. As main result we present a strategy for this game for p=2 pegs and arbitrarily many colors c≥3 colors and prove its feasibility and optimality. Furthermore, by computer search we found optimal strategies for 9 other pairs (pc).

• 25.
Mathematisches Seminar der Christian-Albrechts-Universität zu Kiel, Germany.
Parallel Algorithms for Computing the Smith Normal Form of Large Matrices2003In: Proceedings of 10th European PVM/MPI 2003 / [ed] J. Dongarra, D. Laforenza, S. Orlando, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2003, p. 170-179Conference paper (Refereed)

Smith normal form computation has many applications in group theory, module theory and number theory. As the entries of the matrix and of its corresponding transformation matrices can explode during the computation, it is a very difficult problem to compute the Smith normal form of large dense matrices. The computation has two main problems: the high execution time and the memory requirements, which might exceed the memory of one processor. To avoid these problems, we develop two parallel Smith normal form algorithms using MPI. These are the first algorithms computing the Smith normal form with corresponding transformation matrices, both over the rings Z and F[x]. We show that our parallel algorithms both have a good efficiency, i.e. by doubling the processes, the execution time is nearly halved, and succeed in computing the Smith normal form of dense example matrices over the rings Z and F2[x] with more than thousand rows and columns.

• 26.
Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Germany.
Reduction of Smith Normal Form Transformation Matrices2005In: Computing, ISSN 0010-485X, E-ISSN 1436-5057, Vol. 74, no 4, p. 377-388Article in journal (Refereed)

Smith normal form computations are important in group theory, module theory and number theory. We consider the transformation matrices for the Smith normal form over the integers and give a presentation of arbitrary transformation matrices for this normal form. Our main contribution is an algorithm that replaces already computed transformation matrices by others with small entries. We combine methods from lattice basis reduction with a procedure to reduce the sum of the squared entries of both transformation matrices. This algorithm performs well even for matrices of large dimensions.

• 27. Jäger, Gerold
SAT and IP Based Algorithms for Magic Labeling with Applications2013In: Proceedings of 24th International Workshop om Combinatorial Algorithms (IWOCA 2013), Berlin-Heidelberg, 2013, p. 258-268Conference paper (Refereed)
• 28.
Christian-Albrechts-Universität Kiel.
The Theory of Tolerances with Applications to the Traveling Salesman Problem2011Other (Refereed)
• 29.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
SAT and IP Based Algorithms for Magic Labeling Including a Complete Search for Total Magic Labelings2015In: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675, Vol. 31, p. 87-103Article in journal (Refereed)

In this paper a labeling of a graph with n vertices and m   edges is a one-to-one mapping from the union of the set of vertices and edges onto the set {1,2,…,m+n}. Such a labeling is defined as magic, if one or both of the following two conditions is fulfilled: the sum of an edge label and the labels of its endpoint vertices is constant for all edges; the sum of a vertex label and the labels of its incident edges is constant for all vertices. If a graph has a labeling fulfilling both conditions, it is called a totally magic graph. We present effective IP and Sat based algorithms for the problem of finding a magic labeling for a given graph, and we extend these algorithms also to find all magic labelings for a given graph. We experimentally compare the resulted algorithms by applying it to random graphs. Finally, we demonstrate its performance by solving small cases of seven open problems within the theory of magic graphs. As main practical result we perform an exhaustive search showing that no totally magic graph with 11 vertices exists.

• 30.
Computer Science Institute, University of Halle-Wittenberg, Germany.
School of Medicine, Washington University, United states. Department of Computer Science/Department of Genetics, Washington University, United States.
Complete Parsimony Haplotype Inference Problem and Algorithms2009In: Proceedings of 17th Annual European Symposium on Algorithms (ESA 2009) / [ed] A. Fiat and P. Sanders, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2009, p. 337-348Conference paper (Refereed)

Haplotype inference by pure parsimony (HIPP) is a wellknown paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of HIPP to the problem of finding all optimal solutions, which we call complete HIPP. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypes as well as equal columns and decomposability. We explicitly exploit these features in three computational approaches which are based on integer linear programming, depth-first branch-and-bound, and a hybrid algorithm that draws on the diverse strengths of the first two approaches. Our experimental analysis shows that our optimized algorithms are significantly superior to the baseline algorithms, often with orders of magnitude faster running time. Finally, our experiments provide some useful insights to the intrinsic features of this interesting problem.

• 31.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability2016In: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675, Vol. 37, p. 68-83Article in journal (Refereed)

Haplotype inference by pure parsimony (HIPP) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of HIPP to the problem of finding all optimal solutions, which we call CHIPP. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypesas well as equal columns and decomposability. We explicitly exploit these features in three computational approaches that are based on integer linear programming, depth-first branch-and-bound, and Boolean satisfiability. Further we introduce two hybrid algorithms that draw upon the diverse strengths of the approaches. Our experimental analysis shows that our optimized algorithms are significantly superior to the baseline algorithms, often with orders of magnitude faster running time. Finally, our experiments provide some useful insights into the intrinsic features of this important problem.

• 32.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
A backbone based TSP heuristic for large instances2014In: Journal of Heuristics, ISSN 1381-1231, E-ISSN 1572-9397, Vol. 20, no 1, p. 107-124Article in journal (Refereed)

We introduce a reduction technique for large instances of the traveling salesman problem (TSP). This approach is based on the observation that tours with good quality are likely to share many edges. We exploit this observation by neglecting the less important tour space defined by the shared edges, and searching the important tour subspace in more depth. More precisely, by using a basic TSP heuristic, we obtain a set of starting tours. We call the set of edges which are contained in each of these starting tours as pseudo-backbone edges. Then we compute the maximal paths consisting only of pseudo-backbone edges, and transform the TSP instance to another one with smaller size by contracting each such path to a single edge. This reduced TSP instance can be investigated more intensively, and each tour of the reduced instance can be expanded to a tour of the original instance. Combining our reduction technique with the currently leading TSP heuristic of Helsgaun, we experimentally investigate 32 difficult VLSI instances from the well-known TSP homepage. In our experimental results we set world records for seven VLSI instances, i.e., find better tours than the best tours known so far (two of these world records have since been improved upon by Keld Helsgaun and Yuichi Nagata, respectively). For the remaining instances we find tours that are equally good or only slightly worse than the world record tours.

• 33.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Computing Science.
An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs2018In: 11th International Symposium on Algorithmic Game Theory, SAGT 2018, Beijing, China, September 11-14, 2018 / [ed] Xiaotie Deng, 2018, Vol. 11059, p. 261-266Conference paper (Refereed)

Mastermind is a famous game played by a codebreaker against a codemaker. We investigate its static (also called non-adaptive) black-peg variant. Given c colors and p pegs, the codemaker has to choose a secret, a p-tuple of c colors, and the codebreaker asks a set of questions all at once. Like the secret, a question is a p-tuple of c colors. The codemaker then tells the codebreaker how many pegs in each question are correct in position and color. Then the codebreaker has one final question to find the secret. His aim is to use as few of questions as possible. Our main result is an optimal strategy for the codebreaker for p=3 pegs and an arbitrary number c of colors using ⌊3c/2⌋+1questions.

A reformulation of our result is that the metric dimension of ℤn×ℤn×ℤnis equal to ⌊3n/2⌋.

• 34.
Institute for Computer Science, University of Halle-Wittenberg, Germany.
Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine. Institute for Computer Science, University of Halle-Wittenberg, Germany.
Some Basics on Tolerances2005Report (Refereed)

In this note we deal with sensitivity analysis of combinatorial optimization problems and its fundamental term, the tolerance. For three classes of objective functions (∑ ∏ MAX) we prove some basic properties on upper and lower tolerances. We show that the upper tolerance of an element is well defined, how to compute the upper tolerance of an element, and give equivalent formulations when the upper tolerance is +1 or > 0. Analogous results are proven for the lower tolerance and some results on the relationship between lower and upper tolerances are given.

• 35.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, Unites States. Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, United States.
The Theory of Set Tolerances2014In: Proceedings of 8th Conference on Learning and Intelligent Optimization (LION 2014), 2014, p. 362-377Conference paper (Refereed)
• 36.
Computer Science Institute, University of Halle-Wittenberg, Germany.
Computer Science Institute, University of Halle-Wittenberg, Germany.
Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order2008In: Proceedings of 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA 2008) / [ed] B. Yang, D.-Z. Du and C.A. Wang, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2008, p. 211-224Conference paper (Refereed)

We introduce a new combinatorial optimization problem, which is a generalization of the Traveling Salesman Problem (TSP) and which we call Traveling Salesman Problem of Second Order (2-TSP). It is motivated by an application in bioinformatics, especially the Permuted Variable Length Markov model. We propose seven elementary heuristics and two exact algorithms for the 2-TSP, some of which are generalizations of similar algorithms for the Asymmetric Traveling Salesman Problem (ATSP), some of which are new ideas. Finally we experimentally compare the algorithms for random instances and real instances from bioinformatics. Our experiments show that for the real instances most heuristics lead to optimum or almost-optimum solutions, and for the random instances the exact algorithms need less time than for the real instances.

• 37.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Bounding memory for Mastermind might not make it harder2015In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 596, p. 55-66Article in journal (Refereed)
• 38.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Institute of Informatics, University of Warsaw, Poland.
Playing several variants of mastermind with constant-size memory is not harder than with unbounded memory2015In: Combinatorial Algorithms: 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers / [ed] Kratochvíl Jan, Mirka Miller, Dalibor Froncek, Springer Berlin/Heidelberg, 2015, p. 188-199Conference paper (Refereed)

We investigate a version of the Mastermind game, where the codebreaker may only store a constant number of questions and answers, called Constant-Size Memory Mastermind, which was recently introduced by Doerr and Winzen. We concentrate on the most difficult case, where the codebreaker may store only one question and one answer, called Size-One Memory Mastermind. We consider two variants of the game: the original one, where the answer is coded with white and black pegs, and the simplified one, where only black pegs are used in the answer. We show that for two pegs and an arbitrary number of colors, the number of questions needed by the codebreaker in an optimal strategy in the worst case for these games is equal to the corresponding number of questions in the games without a memory restriction. In other words, for these cases restricting the memory size does not make the game harder for the codebreaker. This is a continuation of a result of Doerr and Winzen, who showed that this holds asymptotically for a fixed number of colors and an arbitrary number of pegs. Furthermore, by computer search we determine additional pairs (p, c), where again the numbers of questions in an optimal strategy in the worst case for Size-One Memory Mastermind and original Mastermind are equal.

• 39.
Institute for Applied Stochastics and Operations Research, Technical University of Clausthal, D-38678 Clausthal, Germany.
Institute of Informatics, University of Warsaw, ul. Banacha 2, PL-02-097 Warszawa, Poland.
The number of pessimistic guesses in Generalized Black-peg Mastermind2011In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 111, no 19, p. 933-940Article in journal (Refereed)

Mastermind is a famous two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible using information he receives from the codemaker after each guess. In Generalized Black-peg Mastermind for given arbitrary numbers p, c, the secret code consists of p pegs each having one of c colors, and the received information consists only of a number of black pegs, where this number equals the number of pegs matching in the corresponding question and the secret code. Let b(p; c) be the pessimistic number of questions for Generalized Black-peg Mastermind. By a computer program we compute several values b(p; c). By introducing some auxiliary games and combining this program with theoretical methods, for arbitrary c we obtain exact formulas for b(2; c), b(3; c) and b(4; c) and give upper and lower bounds for b(5; c) and a lower bound for b(6; c). Furthermore, for arbitrary p, we present upper bounds for b(p; 2), b(p; 3) and b(p; 4). Finally, we give bounds for the general case b(p; c). In particular, we improve an upper bound recently proved by Goodrich.

• 40.
Institute of Computer Science, Martin-Luther University of Halle-Wittenberg, D-06120 Halle (Saale), Germany.
Institute of Informatics, University of Warsaw, ul. Banacha 2, PL-02-097 Warszawa, Poland.
The number of pessimistic guesses in Generalized Mastermind2009In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 109, no 12, p. 635-641Article in journal (Refereed)

Mastermind is a famous two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible. The code consists of 4 pegs, each of which is one of 6 colors. In Generalized Mastermind a general number p of pegs and a general number c of colors is considered. Let f(p; c) be the pessimistic number of questions for the generalization of Mastermind with an arbitrary number p of pegs and c of colors. By a computer program we compute ten new values of f(p; c). Combining this program with theoretical methods, we compute all values f(3; c) and a tight lower and upper bound for f(4; c). For f(p; 2) we give an upper bound and a lower bound. Finally, combining results for fixed p and c, we give bounds for the general case f(p; c).

• 41.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Institute of Informatics, University of Warsaw, Poland.
The worst case number of questions in Generalized AB game with and without white-peg answers2015In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 184, p. 20-31Article in journal (Refereed)

The AB game is a two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible. It is a variant of the famous Mastermind game, with the only difference that all pegs in both, the secret and the questions must have distinct colors. In this work, we consider the Generalized AB game, where for given arbitrary numbers p, c with p <= c the secret code consists of p pegs each having one of c colors and the answer consists of a number of black and white pegs. There the number of black pegs equals the number of pegs matching in the corresponding question and the secret in position and color, and the number of white pegs equals the additional number of pegs matching in the corresponding question and the secret only in color. We consider also a variant of the Generalized AB game, where the information of white pegs is omitted. This variant is called Generalized Black-peg AB game. Let ab(p, c) and abb(p, c) be the number of questions in the worst case needed by the codebreaker to guess the secret for Generalized AB game and Generalized Black-peg AB game, respectively. Combining a computer program with theoretical considerations, we confirm known exact values of ab(2, c) and ab(3, c) and prove tight bounds for ab(4, c). Furthermore, we present exact values for abb(2, c) and abb(3, c) and tight bounds for abb(4, c)

• 42.
Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
Improved Approximation Algorithms for Maximum Graph Partitioning Problems2005In: Journal of combinatorial optimization, ISSN 1382-6905, E-ISSN 1573-2886, Vol. 10, no 2, p. 133-167Article in journal (Refereed)

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.

• 43.
Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
Improved Approximation Algorithms for Maximum Graph Partitioning Problems2004In: Proceedings of 24th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2004) / [ed] P.K. Lodaya and M. Mahajan, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2004, p. 348-359Conference paper (Refereed)

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  $k=\frac{n}{2}$  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.

• 44.
Department of Computer Science, Washington University, USA.
Institut für Informatik, Christian-Albrechts-Universität zu Kiel, Germany . Zentrum für Paralleles Rechnen Universität zu Köln, Germany.
Solving Generalized Maximum Dispersion with Linear Programming2007In: Proceedings of 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM 2007) / [ed] M.-Y. Kao and X.-Y. Li, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2007, p. 1-10Conference paper (Refereed)

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.

• 45.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Extending Single Tolerances to Set Tolerances2018In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 247, p. 197-215Article in journal (Refereed)

The theory of single upper and lower tolerances for combinatorial minimization problems was formalized in 2005 for the three types of cost functions sum, product, and maximum, and since then it has shown to be rather useful in creating heuristics and exact algorithms. However, such single tolerances are often used because the assessment of multiple cost changes is considered too complicated. This paper addresses that issue. In this paper we extend this theory from single to set tolerances for these three types of cost functions. In particular, we characterize specific values of set upper and lower tolerances as positive and infinite, and we show a criterion for the uniqueness of an optimal solution to a combinatorial minimization problem. Furthermore, we present one exact formula and several bounds for computing set upper and lower tolerances using the relation to their corresponding single tolerance counterparts.

• 46.
Computer Science Institute, University of Halle-Wittenberg, D-06120 Halle (Saale), Germany.
denkwerk, Vogelsanger Straße 66, D-50823 Köln, Germany.
Efficient parallelizations of Hermite and Smith normal form algorithms2009In: Parallel Computing, ISSN 0167-8191, E-ISSN 1872-7336, Vol. 35, no 6, p. 345-357Article in journal (Refereed)

Hermite and Smith normal form are important forms of matrices used in linear algebra. These terms have many applications in group theory and number theory. As the entries of the matrix and of its corresponding transformation matrices can explode during the computation, it is a very difficult problem to compute the Hermite and Smith normal form of large dense matrices. The main problems of the computation are the large execution times and the memory requirements which might exceed the memory of one processor. To avoid these problems, we develop parallelizations of Hermite and Smith normal form algorithms. These are the first parallelizations of algorithms for computing the normal forms with corresponding transformation matrices, both over the rings Z and F[x]. We show that our parallel versions have good efficiency, i.e., by doubling the processes, the execution time is nearly halved. Furthermore, they succeed in computing normal forms of dense large example matrices over the rings Q[x], F3[x], and F5[x].

• 47.
Computer Science Institute, Christian-Albrechts-University of Kiel, Germany .
Department of Computer Science/Department of Genetics, Washington University, United States .
A SAT Based Effective Algorithm for the Directed Hamiltonian Cycle Problem2010In: Proceedings of 5th International Computer Science Symposium in Russia (CSR 2010) / [ed] F. Ablayev and E.W. Mayr, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2010, p. 216-227Conference paper (Refereed)

The Hamiltonian cycle problem (HCP) is an important combinatorial problem with applications in many areas. While thorough theoretical and experimental analyses have been made on the HCP in undirected graphs, little is known for the HCP in directed graphs (DHCP). The contribution of this work is an e ective algorithm for the DHCP. Our algorithm explores and exploits the close relationship between the DHCP and the Assignment Problem (AP) and utilizes a technique based on Boolean satisfiability (SAT). By combining e ective algorithms for the AP and SAT, our algorithm signicantly outperforms previous exact DHCP algorithms including an algorithm based on the award-winning Concorde TSP algorithm.

• 48.
Computer Science Institute, Christian-Albrechts-University of Kiel, D-24118 Kiel, Germany.
Department of Computer Science and Engineering, Washington University, St. Louis, Missouri 63130, United States.
An Effective Algorithm for and Phase Transitions of the Directed Hamiltonian Cycle Problem2010In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 39, p. 663-687Article in journal (Refereed)

The Hamiltonian cycle problem (HCP) is an important combinatorial problem with applications in many areas. It is among the first problems used for studying intrinsic properties, including phase transitions, of combinatorial problems. While thorough theoretical and experimental analyses have been made on the HCP in undirected graphs, a limited amount of work has been done for the HCP in directed graphs (DHCP). The main contribution of this work is an effective algorithm for the DHCP. Our algorithm explores and exploits the close relationship between the DHCP and the Assignment Problem (AP) and utilizes a technique based on Boolean satisfiability (SAT). By combining effective algorithms for the AP and SAT, our algorithm significantly outperforms previous exact DHCP algorithms, including an algorithm based on the award-winning Concorde TSP algorithm. The second result of the current study is an experimental analysis of phase transitions of the DHCP, verifying and refining a known phase transition of the DHCP.

• 49.
Computer Science Institute, University of Halle-Wittenberg, Germany.
Faculty of Economic Sciences, University of Groningen, The Netherlands, University of Economics and Business, Lviv Highway 51/2, 29016 Khmelnitsky, Ukraine and Department of Applied Mathematics, Khmelnitsky National University, Ukraine. Department of Computer Science, Washington University, USA. Computer Science Institute, University of Halle-Wittenberg, Germany.
Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP2007In: Proceedings of the 4th conference on Combinatorial and Algorithmic Aspects of Networking (CAAN 2007) / [ed] J. Janssen and P. Pralat, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2007, p. 99-111Conference paper (Refereed)

Helsgaun has introduced and implemented the lower tolerances (-values) for an approximation of Held-Karp’s 1-tree with the purpose to improve the Lin-Kernighan Heuristic (LKH) for the Symmetric TSP (STSP). The LKH appears to exceed the performance of all STSP heuristic algorithms proposed to date. In this paper we improve Helsgaun’s LKH based on an approximation of Zhang and Looks’ backbones and an extension of double bridges further combined with implementation details by all of which we guide the search process instead of Helsgaun’s -values. Our computational results are competitive and lead to improved solutions for some of the VLSI instances announced at the TSP homepage.

• 50.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics. Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
The Zero Forcing Number of Bijection Graphs2015In: Proceedings of 26th International Workshop om Combinatorial Algorithms (IWOCA 2015), Berlin-Heidelberg, 2015, Vol. 9538, p. 334-345Conference paper (Refereed)
1 - 50 of 50
Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf