umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Jäger, Gerold
Publications (10 of 54) Show all publications
Jäger, G. & Drewes, F. (2019). The Metric Dimension of Zn × Zn × Zn is ⌊3n/2⌋. Theoretical Computer Science
Open this publication in new window or tab >>The Metric Dimension of Zn × Zn × Zn is ⌊3n/2⌋
2019 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, , p. 78Article in journal (Refereed) In press
Abstract [en]

In this work we determine the metric dimension of Zn × Zn × Zn as ⌊3n/2⌋ for all n ≥ 2. We prove this result by investigating a variant of Mastermind.

Mastermind is a famous two-player game that has attracted much attention in the literature in recent years. In particular we consider the static (also called non-adaptive) black-peg variant of Mastermind. The game is played by a codemaker and a codebreaker. Given c colors and p pegs, the principal rule is that the codemaker has to choose a secret by assigning colors to the pegs, i.e., the secret is a p-tuple of colors, and the codebreaker asks a number of questions all at once. Like the secret, a question is a p-tuple of colors chosen from the c available colors. The codemaker then answers all of those questions by telling the codebreaker how many pegs in each question are correctly colored. The goal is to find the minimal number of questions that allows the codebreaker to determine the secret from the received answers. We present such a strategy for this game for p = 3 pegs and an arbitrary number c ≥ 2 of colors using ⌊3c/2⌋ + 1 questions, which we prove to be both feasible and optimal.

The minimal number of questions required for p pegs and c colors is easily seen to be equal to the metric dimension of Zpc plus 1 which proves our main result.

Publisher
p. 78
Keywords
weighted tree automaton, N-best analysis, tropical semiring
National Category
Computer Sciences Discrete Mathematics
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-159286 (URN)
Available from: 2019-05-23 Created: 2019-05-23 Last updated: 2019-05-23
Jäger, G., Markström, K., Öhman, L.-D. & Shcherbak, D. (2019). Triples of Orthogonal Latin and Youden Rectangles of small order. Journal of combinatorial designs (Print), 27(4), 229-250
Open this publication in new window or tab >>Triples of Orthogonal Latin and Youden Rectangles of small order
2019 (English)In: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 27, no 4, p. 229-250Article in journal (Refereed) Published
Abstract [en]

We have performed a complete enumeration of non-isotopic triples of mutually orthogonal k × n Latin rectangles for k ≤ n ≤ 7. Here we will present a census of such triples, classified by various properties, including the order of the autotopism group of the triple. As part of this we have also achieved the first enumeration of pairwise orthogonal triples of Youden rectangles. We have also studied orthogonal triples of k×8 rectangles which are formed by extending mutually orthogonal triples with non-trivial autotopisms one row at a time, and requiring that the autotopism group is non-trivial in each step. This class includes a triple coming from the projective plane of order 8. Here we find a remarkably symmetrical pair of triples of 4 × 8 rectangles, formed by juxtaposing two   selected copies of complete sets of MOLS of order 4.

National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-158857 (URN)10.1002/jcd.21642 (DOI)000459040800001 ()2-s2.0-85059030594 (PubMedID)
Available from: 2019-05-13 Created: 2019-05-13 Last updated: 2019-05-23Bibliographically approved
Jäger, G. & Drewes, F. (2018). An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs. In: Xiaotie Deng (Ed.), SAGT: International Symposium on Algorithmic Game Theory: 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings. Paper presented at 11th International Symposium on Algorithmic Game Theory, Beijing, China, September 11-14, 2018 (pp. 261-266). Springer, 11059
Open this publication in new window or tab >>An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs
2018 (English)In: SAGT: International Symposium on Algorithmic Game Theory: 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings / [ed] Xiaotie Deng, Springer, 2018, Vol. 11059, p. 261-266Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
Springer, 2018
Series
Lecture Notes in Computer Science
Keywords
Mastermind, winning strategy, optimality
National Category
Discrete Mathematics Other Computer and Information Science
Identifiers
urn:nbn:se:umu:diva-151844 (URN)10.1007/978-3-319-99660-8_25 (DOI)
Conference
11th International Symposium on Algorithmic Game Theory, Beijing, China, September 11-14, 2018
Available from: 2018-09-13 Created: 2018-09-13 Last updated: 2019-06-19Bibliographically approved
Jäger, G. & Turkensteen, M. (2018). Extending Single Tolerances to Set Tolerances. Discrete Applied Mathematics, 247, 197-215
Open this publication in new window or tab >>Extending Single Tolerances to Set Tolerances
2018 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 247, p. 197-215Article in journal (Refereed) Published
Abstract [en]

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. 

Place, publisher, year, edition, pages
Elsevier, 2018
Keywords
Sensitivity analysis, Combinatorial optimization, Single tolerance, Set tolerance
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-145877 (URN)10.1016/j.dam.2018.03.053 (DOI)000444362700022 ()
Funder
The Kempe Foundations, SMK-1354
Available from: 2018-03-20 Created: 2018-03-20 Last updated: 2018-10-04Bibliographically approved
Glazik, C., Jäger, G., Schiemann, J. & Srivastav, A. (2017). Bounds for Static Black-Peg AB Mastermind. In: COCOA 2017: Combinatorial Optimization and Applications. Paper presented at The 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017), Shanghai, China, December 16-18, 2017 (pp. 409-424). Springer Berlin/Heidelberg
Open this publication in new window or tab >>Bounds for Static Black-Peg AB Mastermind
2017 (English)In: COCOA 2017: Combinatorial Optimization and Applications, Springer Berlin/Heidelberg, 2017, p. 409-424Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2017
Series
Lecture Notes in Computer Science ; 10628
Keywords
Mastermind, Game Theory, Upper Bound, Game Theory
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-139844 (URN)10.1007/978-3-319-71147-8_28 (DOI)978-3-319-71146-1 (ISBN)978-3-319-71147-8 (ISBN)
Conference
The 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017), Shanghai, China, December 16-18, 2017
Available from: 2017-09-22 Created: 2017-09-22 Last updated: 2019-06-26Bibliographically approved
Jäger, G. (2016). An Optimal Strategy for Static Mastermind with Two Pegs. In: Proceedings of 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016): . Paper presented at 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016) (pp. 670-682). Springer Berlin/Heidelberg
Open this publication in new window or tab >>An Optimal Strategy for Static Mastermind with Two Pegs
2016 (English)In: Proceedings of 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016), Springer Berlin/Heidelberg, 2016, p. 670-682Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2016
Series
Lecture Notes in Computer Science (LNCS), ISSN 0302-9743 ; 10043
Keywords
Game theory, Logic game, Strategy, Static Mastermind
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-125916 (URN)10.1007/978-3-319-48749-6_48 (DOI)
Conference
10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016)
Available from: 2016-09-22 Created: 2016-09-22 Last updated: 2018-06-07Bibliographically approved
Jäger, G., Climer, S. & Zhang, W. (2016). The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability. Paper presented at 2015 London Stringology Days and London Algorithmic Workshop (LSD & LAW). Journal of Discrete Algorithms, 37, 68-83
Open this publication in new window or tab >>The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability
2016 (English)In: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675, Vol. 37, p. 68-83Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2016
Keywords
Haplotype inference, Pure parsimony, Branch-and-bound, Integer programming, Boolean satisfiability
National Category
Algebra and Logic
Identifiers
urn:nbn:se:umu:diva-124271 (URN)10.1016/j.jda.2016.06.001 (DOI)000379021500007 ()
Conference
2015 London Stringology Days and London Algorithmic Workshop (LSD & LAW)
Note

Special Issue

Available from: 2016-08-01 Created: 2016-07-29 Last updated: 2018-06-07Bibliographically approved
Jäger, G. & Peczarski, M. (2015). Bounding memory for Mastermind might not make it harder. Theoretical Computer Science, 596, 55-66
Open this publication in new window or tab >>Bounding memory for Mastermind might not make it harder
2015 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 596, p. 55-66Article in journal (Refereed) Published
Keywords
Game theory, Logic game, Mastermind, Space complexity
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-105534 (URN)10.1016/j.tcs.2015.06.039 (DOI)000358972800005 ()
Available from: 2015-06-25 Created: 2015-06-25 Last updated: 2018-06-07Bibliographically approved
Fischer, A., Fischer, F., Jäger, G., Keilwagen, J., Molitor, P. & Grosse, I. (2015). Computational Recognition of RNA Splice Sites by Exact Algorithms for the Quadratic Traveling Salesman Problem. Computation, 3(2), 285-298
Open this publication in new window or tab >>Computational Recognition of RNA Splice Sites by Exact Algorithms for the Quadratic Traveling Salesman Problem
Show others...
2015 (English)In: Computation, E-ISSN 2079-3197, Vol. 3, no 2, p. 285-298Article in journal (Refereed) Published
Abstract [en]

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.

Keywords
splice site, permuted Markov model, permuted variable length Markov model, quadratic traveling salesman problem, combinatorial optimization, dynamic programming, branch and bound, branch and cut, integer linear programming
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:umu:diva-103009 (URN)10.3390/computation3020285 (DOI)000362074700005 ()
Available from: 2015-05-14 Created: 2015-05-14 Last updated: 2018-06-07Bibliographically approved
Baltz, A., El Ouali, M., Jäger, G., Sauerland, V. & Srivastav, A. (2015). Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection. Journal of the Operational Research Society, 66(4), 615-626
Open this publication in new window or tab >>Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection
Show others...
2015 (English)In: Journal of the Operational Research Society, ISSN 0160-5682, E-ISSN 1476-9360, Vol. 66, no 4, p. 615-626Article in journal (Refereed) Published
Abstract [en]

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.

Keywords
Traveling Salesman Problem, Branch-and-bound, Branch-and-cut, Heuristical methods, Exact methods
National Category
Discrete Mathematics Economics and Business
Identifiers
urn:nbn:se:umu:diva-82881 (URN)10.1057/jors.2014.17 (DOI)000351561600008 ()
Available from: 2013-11-12 Created: 2013-11-12 Last updated: 2018-06-08Bibliographically approved
Organisations

Search in DiVA

Show all publications