umu.sePublications

Please wait ... |

Link to record
http://umu.diva-portal.org/smash/person.jsf?pid=authority-person:62509 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt122_recordDirectLink",{id:"formSmash:upper:j_idt122:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt122_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt122_j_idt124",{id:"formSmash:upper:j_idt122:j_idt124",widgetVar:"widget_formSmash_upper_j_idt122_j_idt124",target:"formSmash:upper:j_idt122:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Jäger, Gerold

Open this publication in new window or tab >>The Metric Dimension of Z(n) x Z(n) x Z(n) is [3n/2]### Jäger, Gerold

### Drewes, Frank

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_some",{id:"formSmash:j_idt184:0:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_otherAuthors",{id:"formSmash:j_idt184:0:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_otherAuthors",multiple:true}); 2020 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 806, p. 78p. 344-362Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Elsevier, 2020. 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)10.1016/j.tcs.2019.05.042 (DOI)000510523000025 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt359",{id:"formSmash:j_idt184:0:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt365",{id:"formSmash:j_idt184:0:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt371",{id:"formSmash:j_idt184:0:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt371",multiple:true});
#####

##### Note

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Umeå University, Faculty of Science and Technology, Department of Computing Science.

In this work we determine the metric dimension of Z_{n} × Z_{n} × Z_{n} as ⌊3*n*/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 Z* _{c}^{p}* plus 1 which proves our main result.

Available online 4 July 2019.

Available from: 2019-05-23 Created: 2019-05-23 Last updated: 2020-02-24Bibliographically approvedOpen this publication in new window or tab >>Triples of Orthogonal Latin and Youden Rectangles of small order### Jäger, Gerold

### Markström, Klas

### Öhman, Lars-Daniel

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Shcherbak, Denys

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_some",{id:"formSmash:j_idt184:1:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_otherAuthors",{id:"formSmash:j_idt184:1:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_otherAuthors",multiple:true}); 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]

##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-158857 (URN)10.1002/jcd.21642 (DOI)000459040800001 ()2-s2.0-85059030594 (PubMedID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt359",{id:"formSmash:j_idt184:1:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt365",{id:"formSmash:j_idt184:1:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt371",{id:"formSmash:j_idt184:1:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt371",multiple:true});
#####

Available from: 2019-05-13 Created: 2019-05-13 Last updated: 2019-05-23Bibliographically approved

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.

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.

Open this publication in new window or tab >>An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Drewes, Frank

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_some",{id:"formSmash:j_idt184:2:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_otherAuthors",{id:"formSmash:j_idt184:2:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_otherAuthors",multiple:true}); 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]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt359",{id:"formSmash:j_idt184:2:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt365",{id:"formSmash:j_idt184:2:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt371",{id:"formSmash:j_idt184:2:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt371",multiple:true});
#####

Available from: 2018-09-13 Created: 2018-09-13 Last updated: 2019-06-19Bibliographically approved

Umeå University, Faculty of Science and Technology, Department of Computing Science.

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

Open this publication in new window or tab >>Extending Single Tolerances to Set Tolerances### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Turkensteen, Marcel

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_some",{id:"formSmash:j_idt184:3:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_otherAuthors",{id:"formSmash:j_idt184:3:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_otherAuthors",multiple:true}); 2018 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 247, p. 197-215Article in journal (Refereed) Published
##### Abstract [en]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt359",{id:"formSmash:j_idt184:3:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt365",{id:"formSmash:j_idt184:3:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt371",{id:"formSmash:j_idt184:3:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt371",multiple:true});
#####

##### Funder

The Kempe Foundations, SMK-1354
Available from: 2018-03-20 Created: 2018-03-20 Last updated: 2018-10-04Bibliographically approved

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.

Open this publication in new window or tab >>Bounds for Static Black-Peg AB Mastermind### Glazik, Christian

### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Schiemann, Jan

### Srivastav, Anand

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_some",{id:"formSmash:j_idt184:4:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_otherAuthors",{id:"formSmash:j_idt184:4:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_otherAuthors",multiple:true}); 2017 (English)In: COCOA 2017: Combinatorial Optimization and Applications, Springer Berlin/Heidelberg, 2017, p. 409-424Conference paper, Published paper (Refereed)
##### Abstract [en]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt359",{id:"formSmash:j_idt184:4:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt365",{id:"formSmash:j_idt184:4:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt371",{id:"formSmash:j_idt184:4:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt371",multiple:true});
#####

Available from: 2017-09-22 Created: 2017-09-22 Last updated: 2019-06-26Bibliographically approved

Christian-Albrechts Universität Kiel.

Christian-Albrechts Universität Kiel.

Christian-Albrechts Universität Kiel.

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

Open this publication in new window or tab >>An Optimal Strategy for Static Mastermind with Two Pegs### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_some",{id:"formSmash:j_idt184:5:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_otherAuthors",{id:"formSmash:j_idt184:5:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_otherAuthors",multiple:true}); 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]

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt359",{id:"formSmash:j_idt184:5:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt365",{id:"formSmash:j_idt184:5:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt371",{id:"formSmash:j_idt184:5:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt371",multiple:true});
#####

Available from: 2016-09-22 Created: 2016-09-22 Last updated: 2018-06-07Bibliographically approved

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 (*p*, *c*).

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### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Climer, Sharlee

### Zhang, Weixiong

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_some",{id:"formSmash:j_idt184:6:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_otherAuthors",{id:"formSmash:j_idt184:6:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_otherAuthors",multiple:true}); 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]

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt359",{id:"formSmash:j_idt184:6:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt365",{id:"formSmash:j_idt184:6:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt371",{id:"formSmash:j_idt184:6:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt371",multiple:true});
#####

##### Note

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.

Special Issue

Available from: 2016-08-01 Created: 2016-07-29 Last updated: 2018-06-07Bibliographically approvedOpen this publication in new window or tab >>Bounding memory for Mastermind might not make it harder### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Peczarski, Marcin

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_some",{id:"formSmash:j_idt184:7:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_otherAuthors",{id:"formSmash:j_idt184:7:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_otherAuthors",multiple:true}); 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt359",{id:"formSmash:j_idt184:7:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt365",{id:"formSmash:j_idt184:7:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt371",{id:"formSmash:j_idt184:7:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt371",multiple:true});
#####

Available from: 2015-06-25 Created: 2015-06-25 Last updated: 2018-06-07Bibliographically approved

Open this publication in new window or tab >>Computational Recognition of RNA Splice Sites by Exact Algorithms for the Quadratic Traveling Salesman Problem### Fischer, Anja

### Fischer, Frank

### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Keilwagen, Jens

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_some",{id:"formSmash:j_idt184:8:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_some",multiple:true}); ### Molitor, Paul

### Grosse, Ivo

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_otherAuthors",{id:"formSmash:j_idt184:8:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_8_j_idt188_j_idt202",{id:"formSmash:j_idt184:8:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"Show others..."}); 2015 (English)In: Computation, E-ISSN 2079-3197, Vol. 3, no 2, p. 285-298Article in journal (Refereed) Published
##### Abstract [en]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt359",{id:"formSmash:j_idt184:8:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt365",{id:"formSmash:j_idt184:8:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt371",{id:"formSmash:j_idt184:8:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt371",multiple:true});
#####

Available from: 2015-05-14 Created: 2015-05-14 Last updated: 2018-06-07Bibliographically approved

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.

Open this publication in new window or tab >>Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection### Baltz, Andreas

### El Ouali, Mourad

### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Sauerland, Volkmar

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_some",{id:"formSmash:j_idt184:9:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_some",multiple:true}); ### Srivastav, Anand

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_otherAuthors",{id:"formSmash:j_idt184:9:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_9_j_idt188_j_idt202",{id:"formSmash:j_idt184:9:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt359",{id:"formSmash:j_idt184:9:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt365",{id:"formSmash:j_idt184:9:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt371",{id:"formSmash:j_idt184:9:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt371",multiple:true});
#####

Available from: 2013-11-12 Created: 2013-11-12 Last updated: 2018-06-08Bibliographically approved

Christian-Albrechts Universität Kiel.

Christian-Albrechts Universität Kiel.

Christian-Albrechts Universität Kiel.

Christian-Albrechts Universität Kiel.

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.