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 >>An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs### 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}); 2018 (English)In: 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, Published paper (Refereed)
##### Abstract [en]

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

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

Available from: 2018-09-13 Created: 2018-09-13 Last updated: 2018-09-13

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

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

### Turkensteen, Marcel

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}); 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_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});
#####

##### Funder

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

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

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

### Schiemann, Jan

### Srivastav, Anand

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}); 2017 (English)In: Proceedings of 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017), Springer Berlin/Heidelberg, 2017Conference paper, Published paper (Refereed)
##### Abstract [en]

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

Springer Berlin/Heidelberg, 2017
##### Keywords

Mastermind, Game Theory, Upper Bound, Game Theory
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-139844 (URN)
##### Conference

The 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017), December 16-18, 2017, Shanghai, China
#####

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: 2017-09-22 Created: 2017-09-22 Last updated: 2018-06-09

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.

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_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}); 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_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});
#####

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_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}); 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_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});
#####

##### 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_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}); 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_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: 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_6_j_idt188_some",{id:"formSmash:j_idt184:6:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_some",multiple:true}); ### Molitor, Paul

### Grosse, Ivo

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}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_6_j_idt188_j_idt202",{id:"formSmash:j_idt184:6:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_6_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_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});
#####

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_7_j_idt188_some",{id:"formSmash:j_idt184:7:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_some",multiple:true}); ### Srivastav, Anand

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}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_7_j_idt188_j_idt202",{id:"formSmash:j_idt184:7:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_7_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_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: 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.

Open this publication in new window or tab >>Playing several variants of mastermind with constant-size memory is not harder than with unbounded memory### 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_8_j_idt188_some",{id:"formSmash:j_idt184:8:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_some",multiple:true}); 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}); 2015 (English)In: 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, Published paper (Refereed)
##### Abstract [en]

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

Springer Berlin/Heidelberg, 2015
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 ; 8986
##### Keywords

Game theory, Logic game, Mastermind, Space complexity
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-100113 (URN)10.1007/978-3-319-19315-1_17 (DOI)000365044500017 ()978-3-319-19314-4 (ISBN)978-3-319-19315-1 (ISBN)
##### Conference

25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014
#####

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-02-23 Created: 2015-02-23 Last updated: 2018-06-07Bibliographically approved

Institute of Informatics, University of Warsaw, Poland.

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.

Open this publication in new window or tab >>SAT and IP Based Algorithms for Magic Labeling Including a Complete Search for Total Magic Labelings### Jäger, Gerold

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

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}); 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}); 2015 (English)In: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675, Vol. 31, p. 87-103Article in journal (Refereed) Published
##### Abstract [en]

##### Keywords

Boolean satisfiability, Integer programming, Magic labeling
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-100105 (URN)10.1016/j.jda.2015.01.011 (DOI)000358518400008 ()
#####

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: 2015-02-23 Created: 2015-02-23 Last updated: 2018-06-07Bibliographically approved

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.