ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    ISSN: 1436-4646
    Keywords: Quadratic assignment ; Special cases ; Polynomially solvable ; Anti-Monge matrices ; Toeplitz matrices
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper investigates a restricted version of the Quadratic Assignment Problem (QAP), where one of the coefficient matrices is an Anti-Monge matrix with non-decreasing rows and columns and the other coefficient matrix is a symmetric Toeplitz matrix. This restricted version is called the Anti-Monge—Toeplitz QAP. There are three well-known combinatorial problems that can be modeled via the Anti-Monge—Toeplitz QAP: (Pl) The “Turbine Problem”, i.e. the assignment of given masses to the vertices of a regular polygon such that the distance of the center of gravity of the resulting system to the center of the polygon is minimized. (P2) The Traveling Salesman Problem on symmetric Monge distance matrices. (P3) The arrangement of data records with given access probabilities in a linear storage medium in order to minimize the average access time. We identify conditions on the Toeplitz matrixB that lead to a simple solution for the Anti-Monge—Toeplitz QAP: The optimal permutation can be given in advance without regarding the numerical values of the data. The resulting theorems generalize and unify several known results on problems (P1), (P2), and (P3). We also show that the Turbine Problem is NP-hard and consequently, that the Anti-Monge—Toeplitz QAP is NP-hard in general. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 12 (1977), S. 318-327 
    ISSN: 1436-4646
    Keywords: Combinatorial Optimization ; Assignment Problem ; Ordered Semigroups ; Bottleneck Objective ; Lexicographical Objective ; Labeling Method ; Admissible Transformation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract For assignment problems a class of objective functions is studied by algebraic methods and characterized in terms of an axiomatic system. It says essentially that the coefficients of the objective function can be chosen from a totally ordered commutative semigroup, which obeys a divisibility axiom. Special cases of the general model are the linear assignment problem, the linear bottleneck problem, lexicographic multicriteria problems,p-norm assignment problems and others. Further a polynomial bounded algorithm for solving this generalized assignment problem is stated. The algebraic approach can be extended to a broader class of combinatorial optimization problems.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Journal of combinatorial optimization 2 (1998), S. 333-350 
    ISSN: 1573-2886
    Keywords: travelling salesman problem ; subtour patching ; combinatorial optimization ; computational complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We consider traveling salesman problems (TSPs) with a permuted Monge matrix as cost matrix where the associated patching graph has a specially simple structure: a multistar, a multitree or a planar graph. In the case of multistars, we give a complete, concise and simplified presentation of Gaikov's theory. These results are then used for designing an O(m3 + mn) algorithm in the case of multitrees, where n is the number of cities and m is the number of subtours in an optimal assignment. Moreover we show that for planar patching graphs, the problem of finding an optimal subtour patching remains NP-complete.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Journal of global optimization 10 (1997), S. 391-403 
    ISSN: 1573-2916
    Keywords: Quadratic assignment problem ; data instances ; problem library
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A collection of electronically available data instances for the QuadraticAssignment Problem is described. For each instance, we provide detailedinformation, indicating whether or not the problem is solved to optimality. Ifnot, we supply the best known bounds for the problem. Moreover we surveyavailable software and describe recent dissertations related to the QuadraticAssignment Problem.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 57 (1995), S. 29-44 
    ISSN: 1572-9338
    Keywords: Automation ; heuristic search ; partial enumeration
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This study concerns the design of an operating system for vehicles in an automated warehouse. The layout of the warehouse and the number and properties of the vehicles are given. The objective is to maximize the throughput. Using a partial enumeration technique, we simulate several alternatives for the control and interplay of the vehicles within a reasonable time horizon. A subproblem is solved by network flow techniques. The algorithm is implemented as part of an automatic control system, and it has led to a satisfactory performance.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 76 (1998), S. 0-0 
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The goal of the series "Mathematics of Industrial Systems" (MIS) is to describe and promote the role of applied mathematics in industrial systems. In particular, the publication focuses on discrete models and combinatorial solution approaches in industry, where the term industry should be understood in a broad sense.The third volume of this series contains fourteen contributions. The papers describe successful applications of mathematics to applied problems and propose new solution procedures. Two papers deal with interesting applications in telecommunication, namely network synthesis problems and frequency assignment for cellular phone networks. Further articles describe an efficient routing of helicopters for crew exchange, stowage planning for container ships, and mathematical tools in airline schedule planning. Several papers deal with aspects of production processes, starting from dynamic facility layout and the design and operation of AGV-served manufacturing systems, via matching of assembly operations, material planning and tool allocation to certain aspects of scheduling problems.Many people have helped in the preparation of this third volume of MIS. In particular, we would like to thank the referees for their careful work and thoughtful remarks. Their efforts substantially improved the quality of this volume. Moreover, our appreciation is due to Mrs. Nelly Segal, RUTCOR, for providing much help to the editors and for handling editorial matters in such an excellent way.The fourth volume of this series is already in preparation. Submissions for this or another forthcoming volume in the series can be sent to any of the editors. Moreover, comments and proposals for future volumes are welcome and appreciated by the editors.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical methods of operations research 19 (1975), S. 183-193 
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Summary A survey of the most important heuristic approaches for quadratic assignment problems is given.
    Notes: Zusammenfassung Es wird ein Überblick über die wichtigsten in der Literatur beschriebenen heuristischen Lösungsverfahren für quadratische Zuordnungsprobleme gegeben.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 8
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical methods of operations research 37 (1993), S. 31-58 
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Consider a network $$\mathcal{N}$$ =(G, c, τ) whereG=(N, A) is a directed graph andc ij andτ ij , respectively, denote the capacity and the transmission time of arc (i, j) ∈A. The quickest flow problem is then to determine for a given valueυ the minimum numberT(υ) of time units that are necessary to transmit (send)υ units of flow in $$\mathcal{N}$$ from a given sources to a given sinks′. In this paper we show that the quickest flow problem is closely related to the maximum dynamic flow problem and to linear fractional programming problems. Based on these relationships we develop several polynomial algorithms and a strongly polynomial algorithm for the quickest flow problem. Finally we report computational results on the practical behaviour of our metholds. It turns out that some of them are practically very efficient and well-suited for solving large problem instances.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 9
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical methods of operations research 50 (1999), S. 1-7 
    ISSN: 1432-5217
    Keywords: Key words: Transportation problems ; permuted demand vector ; computational complexity ; Monge property ; solution procedure
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract. This paper deals with transportation problems whose demand vectors can be permuted. This additional freedom makes these problems ??-hard, even in the case that the cost matrix fulfills a Monge property. We outline some solution procedures based on good lower and upper bounds.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 10
    Publication Date: 1975-10-01
    Print ISSN: 1432-2994
    Electronic ISSN: 1432-5217
    Topics: Mathematics , Economics
    Published by Springer
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...