umu.sePublikationer
Ändra sökning
Avgränsa sökresultatet
12 1 - 50 av 54
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1.
    Baltz, Andreas
    et al.
    Christian-Albrechts Universität Kiel.
    El Ouali, Mourad
    Christian-Albrechts Universität Kiel.
    Jäger, Gerold
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Sauerland, Volkmar
    Christian-Albrechts Universität Kiel.
    Srivastav, Anand
    Christian-Albrechts Universität Kiel.
    Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection2015Ingår i: Journal of the Operational Research Society, ISSN 0160-5682, E-ISSN 1476-9360, Vol. 66, nr 4, s. 615-626Artikel i tidskrift (Refereegranskat)
    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.

  • 2.
    Baltz, Andreas
    et al.
    Christian-Albrechts Universität Kiel, Germany.
    Jäger, Gerold
    Christian-Albrechts Universität Kiel, Germany.
    Srivastav, Anand
    Christian-Albrechts Universität Kiel, Germany.
    Construction of Sparse Asymmetric Connectors2003Ingår i: Proceedings of European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2003), 2003Konferensbidrag (Refereegranskat)
  • 3.
    Baltz, Andreas
    et al.
    Christian-Albrechts-Universität Kiel, Germany.
    Jäger, Gerold
    Christian-Albrechts-Universität Kiel, Germany.
    Srivastav, Anand
    Christian-Albrechts-Universität Kiel, Germany.
    Constructions of Sparse Asymmetric Connectors2003Ingår i: 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, s. 13-22Konferensbidrag (Refereegranskat)
  • 4.
    Baltz, Andreas
    et al.
    Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
    Jäger, Gerold
    Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
    Srivastav, Anand
    Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
    Constructions of Sparse Asymmetric Connectors with Number Theoretic Methods2005Ingår i: Networks, ISSN 0028-3045, E-ISSN 1097-0037, Vol. 45, nr 3, s. 119-124Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We consider the problem of connecting a set I of n inputs to a set O of N outputs (n ≤ N) by as few edges as possible such that for every injective mapping f : I → O there are n vertex disjoint paths from i to f(i) of length k for a given k . For k = Ω(log N + logn) Oruς (1994) gave the presently best (n,N)-connector with O(N+n·log n) edges. For k=2 and N the square of a prime, Richards and Hwang (1985) described a construction using edges. We show by a probabilistic argument that an optimal (n,N)-connector has Θ (N) edges, if for some ε>0. Moreover, we give explicit constructions based on a new number theoretic approach that need at most edges for arbitrary choices of n and N. The improvement we achieve is based on applying a generalization of the Erdös-Heilbronn conjecture on the size of restricted sums.

  • 5.
    Climer, Sharlee
    et al.
    School of Medicine, Washington University, United States.
    Jäger, Gerold
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Templeton, Alan R
    Department of Biology, Washington University, United States.
    Zhang, Weixiong
    Department of Computer Science/Department of Genetics, Washington University, United States.
    How frugal is mother nature with haplotypes?2009Ingår i: Bioinformatics, ISSN 1367-4803, E-ISSN 1367-4811, Vol. 25, nr 1, s. 68-74Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.
    Dong, Changxing
    et al.
    Computer Science Institute, University of Halle Wittenberg, Germany .
    Ernst, Christian
    Computer Science Institute, University of Halle Wittenberg, Germany .
    Jäger, Gerold
    Computer Science Institute, University of Halle Wittenberg, Germany .
    Richter, Dirk
    Computer Science Institute, University of Halle Wittenberg, Germany .
    Molitor, Paul
    Computer Science Institute, University of Halle Wittenberg, Germany .
    Effective Heuristics for Large Euclidean TSP Instances Based on Pseudo Backbones2009Ingår i: 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, s. 3-6Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.
    Dong, Changxing
    et al.
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Jäger, Gerold
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Richter, Dirk
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Molitor, Paul
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Effective Tour Searching for TSP by Contraction of Pseudo Backbone Edges2009Ingår i: Proceedings of 5th International Conference on Algorithmic Aspects in Information and Management (AAIM 2009) / [ed] A. Goldberg and Y. Zhou, Berlin-Heidelberg: Springer , 2009, s. 175-187Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.
    El Ouali, Mourad
    et al.
    Computer Science Institute, Christian-Albrechts-University of Kiel, Germany.
    Jäger, Gerold
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    The b-Matching Problem in Hypergraphs: Hardness and Approximability2012Ingår i: COCOA 2012: Combinatorial Optimization and Applications / [ed] Guohui Lin, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2012, s. 200-211Konferensbidrag (Refereegranskat)
    Abstract [en]

    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 ∈ ℕ and a hypergraph H=(V,E)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">H=(V,E)H=(V,E) a subset Mb&#x2286;E" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">Mb⊆EMb⊆E 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 ∈ ℕ , this problem has no approximation scheme, unless P=NP" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">P=NPP=NP. This result generalizes a result of Kann from b = 1 to the case that b ∈ ℕ with 0&lt;b&#x2264;B3" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">0<b≤B30<b≤B3. Furthermore, we extend a result of Srivastav and Stangier, who gave an approximation algorithm for the unweighted b-matching problem.

  • 9.
    Ernst, Christian
    et al.
    Martin-Luther-University Halle-Wittenberg, Germany and GISA GmbH, D-06112 Halle (Saale), Germany.
    Dong, Changxing
    Martin-Luther-University Halle-Wittenberg, Germany.
    Jäger, Gerold
    Martin-Luther-University Halle-Wittenberg, Germany and Christian-Albrechts-University Kiel, Germany.
    Richter, Dirk
    Martin-Luther-University Halle-Wittenberg, Germany.
    Molitor, Paul
    Martin-Luther-University Halle-Wittenberg, Germany.
    Finding Good Tours for Huge Euclidean TSP Instances by Iterative Backbone Contraction2010Ingår i: Proceedings of 6th International Conference on Algorithmic Aspects in Information and Management (AAIM 2010) / [ed] B. Chen, Berlin-Heidelberg: Springer , 2010, Vol. 6124, s. 119-130Konferensbidrag (Refereegranskat)
    Abstract [en]

    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
    et al.
    Fischer, Frank
    Jäger, Gerold
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Keilwagen, Jens
    Molitor, Paul
    Grosse, Ivo
    Computational Recognition of RNA Splice Sites by Exact Algorithms for the Quadratic Traveling Salesman Problem2015Ingår i: Computation, E-ISSN 2079-3197, Vol. 3, nr 2, s. 285-298Artikel i tidskrift (Refereegranskat)
    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.

  • 11. Fischer, Anja
    et al.
    Fischer, Frank
    Jäger, Gerold
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Keilwagen, Jens
    Molitor, Paul
    Grosse, Ivo
    Exact algorithms and heuristics for the Quadratic Traveling Salesman Problem with an application in bioinformatics2014Ingår i: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 166, s. 97-114Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.
    Ghosh, Diptesh
    et al.
    P&QM Area, IIM Ahmedabad, India.
    Goldengorin, Boris
    Faculty to Economics Sciences, University of Groningen, the Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
    Gutin, Gregory
    Department of Computer Science, Royal Holloway University of London, UK and Department of Computer Science, University of Haifa, Israel.
    Jäger, Gerold
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Improving the Performance of Greedy Heuristics for TSPs Using Tolerances2007Ingår i: Communications in Dependability and Quality Management, Vol. 10, nr 1, s. 52-70Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.
    Ghosh, Diptesh
    et al.
    P&QM Area, IIM Ahmedabad, India.
    Goldengorin, Boris
    Faculty of Economic Sciences, University of Groningen, The Netherlands.
    Gutin, Gregory
    Department of Computer Science, Royal Holloway University of London, UK and Department of Computer Science, University of Haifa, Israel.
    Jäger, Gerold
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Tolerance-based algorithms for the traveling salesman problem2008Ingår i: 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, s. 47-59Kapitel i bok, del av antologi (Refereegranskat)
    Abstract [en]

    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.
    Glazik, Christian
    et al.
    Christian-Albrechts Universität Kiel.
    Jäger, Gerold
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Schiemann, Jan
    Christian-Albrechts Universität Kiel.
    Srivastav, Anand
    Christian-Albrechts Universität Kiel.
    Bounds for Static Black-Peg AB Mastermind2017Ingår i: COCOA 2017: Combinatorial Optimization and Applications, Springer Berlin/Heidelberg, 2017, s. 409-424Konferensbidrag (Refereegranskat)
    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) .

  • 15.
    Goldengorin, Boris
    et al.
    Department of Econometrics and Operations Research, University of Groningen, The Netherlands.
    Jäger, Gerold
    Computer Science Institute, Martin-Luther-University, Halle-Wittenberg, Germany.
    How To Make a Greedy Heuristic for the Asymmetric Traveling Salesman Problem Competitive2005Rapport (Refereegranskat)
    Abstract [en]

    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.
    Goldengorin, Boris
    et al.
    Faculty of Economics and Business, University of Groningen, The Netherlands.
    Jäger, Gerold
    Computer Science Institute, University of Halle-Wittenberg, D-06099 Halle (Saale), Germany.
    The Computational Efficiency of Ji-Lee-Li Algorithm for the Assignment Problem2008Ingår i: Algorithmic Operations Research, ISSN 1718-3235, Vol. 3, nr 1, s. 79-81Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.
    Goldengorin, Boris
    et al.
    Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
    Jäger, Gerold
    University of Halle-Wittenberg, Computer Science Institute, Germany.
    Molitor, Paul
    University of Halle-Wittenberg, Computer Science Institute, Germany.
    Some Basics on Tolerances2006Ingår i: 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, s. 194-206Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.
    Goldengorin, Boris
    et al.
    Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
    Jäger, Gerold
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Molitor, Paul
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Tolerance Based Contract-or-Patch Heuristic for the Asymmetric TSP2006Ingår i: Proceedings of 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN 2006) / [ed] T. Erlebach, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2006, s. 86-97Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.
    Goldengorin, Boris
    et al.
    Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
    Jäger, Gerold
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Molitor, Paul
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Tolerances Applied in Combinatorial Optimization2006Ingår i: Journal of Computer Science, ISSN 1549-3636, E-ISSN 1552-6607, Vol. 2, nr 9, s. 716-734Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.
    Jäger, Gerold
    Mathematisches Seminar Christian-Albrechts-Universität zu Kiel, Germany.
    A New Algorithm for Computing the Smith Normal Form and its Implementation on Parallel Machines2004Ingår i: Proceedings of 6th Workshop on Advances in Parallel and Distributed Computation Models, International Parallel and Distributed Processing Symposium (IPDPS 2004), IEEE Press, 2004Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.
    Jäger, Gerold
    University of Essen.
    Algorithmen zur Berechnung der Smith-Normalform und deren Implementation auf Parallelrechnern2001Doktorsavhandling, monografi (Övrigt vetenskapligt)
  • 22.
    Jäger, Gerold
    Computer Science Institute, University of Kiel, Germany.
    An Effective SAT encoding for Magic Labeling2010Ingår i: Proceedings of 9th Cologne/Twente workshop on graphs and combinatorial optimization (CTW 2010) / [ed] U. Faigle, R. Schrader, and D. Herrmann, 2010, s. 97-100Konferensbidrag (Refereegranskat)
  • 23.
    Jäger, Gerold
    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 Triangularizations2007Ingår i: Applied Mathematical Sciences, ISSN 1312-885X, E-ISSN 1314-7552, Vol. 1, nr 25, s. 1203-1215Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.
    Jäger, Gerold
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    An Optimal Strategy for Static Mastermind with Two Pegs2016Ingår i: Proceedings of 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016), Springer Berlin/Heidelberg, 2016, s. 670-682Konferensbidrag (Refereegranskat)
    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).

  • 25.
    Jäger, Gerold
    Mathematisches Seminar der Christian-Albrechts-Universität zu Kiel, Germany.
    Parallel Algorithms for Computing the Smith Normal Form of Large Matrices2003Ingår i: Proceedings of 10th European PVM/MPI 2003 / [ed] J. Dongarra, D. Laforenza, S. Orlando, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2003, s. 170-179Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.
    Jäger, Gerold
    Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Germany.
    Reduction of Smith Normal Form Transformation Matrices2005Ingår i: Computing, ISSN 0010-485X, E-ISSN 1436-5057, Vol. 74, nr 4, s. 377-388Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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 Applications2013Ingår i: Proceedings of 24th International Workshop om Combinatorial Algorithms (IWOCA 2013), Berlin-Heidelberg, 2013, s. 258-268Konferensbidrag (Refereegranskat)
  • 28.
    Jäger, Gerold
    Christian-Albrechts-Universität Kiel.
    The Theory of Tolerances with Applications to the Traveling Salesman Problem2011Övrigt (Refereegranskat)
  • 29.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Arnold, Florian
    SAT and IP Based Algorithms for Magic Labeling Including a Complete Search for Total Magic Labelings2015Ingår i: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675, Vol. 31, s. 87-103Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.
    Jäger, Gerold
    et al.
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Climer, Sharlee
    School of Medicine, Washington University, United states.
    Zhang, Weixiong
    Department of Computer Science/Department of Genetics, Washington University, United States.
    Complete Parsimony Haplotype Inference Problem and Algorithms2009Ingår i: Proceedings of 17th Annual European Symposium on Algorithms (ESA 2009) / [ed] A. Fiat and P. Sanders, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2009, s. 337-348Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Climer, Sharlee
    Zhang, Weixiong
    The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability2016Ingår i: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675, Vol. 37, s. 68-83Artikel i tidskrift (Refereegranskat)
    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.

  • 32.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Dong, Changxing
    Goldengorin, Boris
    Molitor, Paul
    Richter, Dirk
    A backbone based TSP heuristic for large instances2014Ingår i: Journal of Heuristics, ISSN 1381-1231, E-ISSN 1572-9397, Vol. 20, nr 1, s. 107-124Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs2018Ingår i: 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, s. 261-266Konferensbidrag (Refereegranskat)
    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⌋.

  • 34.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Drewes, Frank
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
    The Metric Dimension of Z(n) x Z(n) x Z(n) is [3n/2]2020Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 806, s. 78s. 344-362Artikel i tidskrift (Refereegranskat)
    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 Zcp plus 1 which proves our main result.

  • 35.
    Jäger, Gerold
    et al.
    Institute for Computer Science, University of Halle-Wittenberg, Germany.
    Goldengorin, Boris
    Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
    Molitor, Paul
    Institute for Computer Science, University of Halle-Wittenberg, Germany.
    Some Basics on Tolerances2005Rapport (Refereegranskat)
    Abstract [en]

    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.

  • 36.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Goldengorin, Boris
    Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, Unites States.
    Pardalos, Panos M.
    Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, United States.
    The Theory of Set Tolerances2014Ingår i: LION 2014: Learning and Intelligent Optimization: Conference Proceedings, 2014, s. 362-377Konferensbidrag (Refereegranskat)
    Abstract [en]

    The theory of single upper and lower tolerances for combinatorial minimization problems has been formalized in 2005 for the three types of cost functions sum, product and maximum, and since then shown to be rather useful in creating heuristics and exact algorithms for the Traveling Salesman Problem and related problems. In this paper for these three types of cost functions we extend this theory from single to set tolerances and the related reverse set tolerances. In particular, we characterize specific values of (reverse) set upper and lower tolerances as positive and infinite, and we present a criterion for the uniqueness of an optimal solution to a combinatorial minimization problem. Furthermore, we present formulas or bounds for computing (reverse) set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. Finally, we give formulas for the minimum and maximum (reverse) set upper and lower tolerances using again their corresponding single tolerance counterparts.

  • 37.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Shcherbak, Denys
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Enumeration of t-tuples of Mutually Orthogonal Latin Rectangles and Finite GeometriesManuskript (preprint) (Övrigt vetenskapligt)
  • 38.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Shcherbak, Denys
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Triples of Orthogonal Latin and Youden Rectangles of small order2019Ingår i: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 27, nr 4, s. 229-250Artikel i tidskrift (Refereegranskat)
    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.

  • 39.
    Jäger, Gerold
    et al.
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Molitor, Paul
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order2008Ingår i: 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, s. 211-224Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 40.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Peczarski, Marcin
    Bounding memory for Mastermind might not make it harder2015Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 596, s. 55-66Artikel i tidskrift (Refereegranskat)
  • 41.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Peczarski, Marcin
    Institute of Informatics, University of Warsaw, Poland.
    Playing several variants of mastermind with constant-size memory is not harder than with unbounded memory2015Ingår i: 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, s. 188-199Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 42.
    Jäger, Gerold
    et al.
    Institute for Applied Stochastics and Operations Research, Technical University of Clausthal, D-38678 Clausthal, Germany.
    Peczarski, Marcin
    Institute of Informatics, University of Warsaw, ul. Banacha 2, PL-02-097 Warszawa, Poland.
    The number of pessimistic guesses in Generalized Black-peg Mastermind2011Ingår i: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 111, nr 19, s. 933-940Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.

  • 43.
    Jäger, Gerold
    et al.
    Institute of Computer Science, Martin-Luther University of Halle-Wittenberg, D-06120 Halle (Saale), Germany.
    Peczarski, Marcin
    Institute of Informatics, University of Warsaw, ul. Banacha 2, PL-02-097 Warszawa, Poland.
    The number of pessimistic guesses in Generalized Mastermind2009Ingår i: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 109, nr 12, s. 635-641Artikel i tidskrift (Refereegranskat)
    Abstract [en]

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

  • 44.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Peczarski, Marcin
    Institute of Informatics, University of Warsaw, Poland.
    The worst case number of questions in Generalized AB game with and without white-peg answers2015Ingår i: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 184, s. 20-31Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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)

  • 45.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Shcherbak, Denys
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Enumeration of Youden Rectangles of Small ParametersManuskript (preprint) (Övrigt vetenskapligt)
  • 46.
    Jäger, Gerold
    et al.
    Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
    Srivastav, Anand
    Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
    Improved Approximation Algorithms for Maximum Graph Partitioning Problems2005Ingår i: Journal of combinatorial optimization, ISSN 1382-6905, E-ISSN 1573-2886, Vol. 10, nr 2, s. 133-167Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.

  • 47.
    Jäger, Gerold
    et al.
    Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
    Srivastav, Anand
    Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
    Improved Approximation Algorithms for Maximum Graph Partitioning Problems2004Ingår i: 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, s. 348-359Konferensbidrag (Refereegranskat)
    Abstract [en]

    In this paper we improve the analysis of approximation algorithms based on semidefinite programming for the maximum graph partitioning problems MAX-k-CUT, MAX-k-UNCUT, MAX-k-DIRECTEDCUT, MAX-k-DIRECTED-UNCUT, MAX-k-DENSE-SUBGRAPH, and MAX-k-VERTEX-COVER. It was observed by Han, Ye, Zhang (2002) and Halperin, Zwick (2002) that a parameter-driven random hyperplane can lead to better approximation factors than obtained by Goemans and Williamson (1994). Halperin and Zwick could describe the approximation factors by a mathematical optimization problem for the above problems for    and found a choice of parameters in a heuristic way. The innovation of this paper is twofold. First, we generalize the algorithm of Halperin and Zwick to cover all cases of k, adding some algorithmic features. The hard work is to show that this leads to a mathematical optimization problem for an optimal choice of parameters. Secondly, as a key-step of this paper we prove that a sub-optimal set of parameters is determined by a linear program. Its optimal solution computed by CPLEX leads to the desired improvements. In this fashion a more systematic analysis of the semidefinite relaxation scheme is obtained which leaves room for further improvements.

  • 48.
    Jäger, Gerold
    et al.
    Department of Computer Science, Washington University, USA.
    Srivastav, Anand
    Institut für Informatik, Christian-Albrechts-Universität zu Kiel, Germany .
    Wolf, Katja
    Zentrum für Paralleles Rechnen Universität zu Köln, Germany.
    Solving Generalized Maximum Dispersion with Linear Programming2007Ingår i: 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, s. 1-10Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 49.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Turkensteen, Marcel
    Extending Single Tolerances to Set Tolerances2018Ingår i: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 247, s. 197-215Artikel i tidskrift (Refereegranskat)
    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. 

  • 50.
    Jäger, Gerold
    et al.
    Computer Science Institute, University of Halle-Wittenberg, D-06120 Halle (Saale), Germany.
    Wagner, Clemens
    denkwerk, Vogelsanger Straße 66, D-50823 Köln, Germany.
    Efficient parallelizations of Hermite and Smith normal form algorithms2009Ingår i: Parallel Computing, ISSN 0167-8191, E-ISSN 1872-7336, Vol. 35, nr 6, s. 345-357Artikel i tidskrift (Refereegranskat)
    Abstract [en]

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

12 1 - 50 av 54
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf