Library

X
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
    Electronic Resource
    Electronic Resource
    Algorithmus 25 Verfahren zur gemischt-ganzzahligen, konvexen Optimierung (1975)
    Springer
    Computing 14 (1975), S. 389-396 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Abstract This paper contains an ALGOL-Procedure for solving mixed integer programming problems with convex objective function and constraints according to a method of Burkard [2].
    Notes: Zusammenfassung Diese Arbeit enthält ein ALGOL-Programm zur Lösung gemischt-ganzzahliger Optimierungsaufgaben mit konvexer Zielfunktion und konvexen Restriktionen nach einer Methode von Burkard [2].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02253549
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Shortest polygonal paths in space (1990)
    Springer
    Computing 45 (1990), S. 51-68 
    Details
    ISSN: 1436-5057
    Keywords: 68U05 ; 90C25 ; Shortest polygonal paths ; shortest inpolygons ; funnel ; linear time algorithm ; constrained paths ; convex function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Ein klassisches Problem der Geometrie fragt nach einem einbeschriebenen Polygon kürzesten Umfanges eines gegebenen konvexen Polygons. Wir verallgemeinern dieses Problem auf beliebige Polygonzüge im Raum und untersuchen zwei Fälle: im “offenen” Fall kann der gesuchte Streckenzug kürzester Länge einen unterschiedlichen Anfangs- und Endpunkt haben, während im “geschlossenen” Fall diese beiden Punkte zusammenfallen müssen. Es wird gezeigt, daß solche kürzesten Polygonzüge durch kürzeste Streckenzüge in einem ebenen “Kanal” bestimmt werden, die in beiden Fällen durch einen Algorithmus mit linearer Laufzeit bestimmt werden können. Ferner wird der Fall behandelt, daß der gesuchte Polygonzug ohne Knick durch einen vorgegebenen Punkt gehen soll. Es wird gezeigt, daß die Länge des Polygonzuges dann eine streng konvexe Funktion eines bestimmten Winkels ist, wodurch es möglich wird, auch dieses Problem effizient zu lösen.
    Notes: Abstract A classical problem of geometry is the following: given a convex polygon in the plane, find an inscribed polygon of shortest circumference. In this paper we generalize this problem to arbitrary polygonal paths in space and consider two cases: in the “open” case the wanted path of shortest length can have different start and end point, whereas in the “closed” case these two points must coincide. We show that finding such shortest paths can be reduced to finding a shortest path in a planar “channel”. The latter problem can be solved by an algorithm of linear-time complexity in the open as well in the closed case. Finally, we deal with constrained problems where the wanted path has to fulfill additional properties; in particular, if it has to pass straight through a further point, we show that the length of such a constrained polygonal path is a strictly convex function of some angle α, and we derive an algorithm for determining such constrained polygonal paths efficiently.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02250584
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Buchbesprechungen (1980)
    Springer
    OR spectrum 1 (1980), S. 207-209 
    Details
    ISSN: 1436-6304
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01719342
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Reshipments and overshipments in transportation problems with minimax objective (1991)
    Springer
    OR spectrum 13 (1991), S. 133-140 
    Details
    ISSN: 1436-6304
    Keywords: Transportation problem ; minimax objective ; sharing problem ; reshipments ; overshipments ; Transportproblem ; Minimax-Zielfunktion ; Sharing Probleme ; Reshipments ; Overshipments
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In dieser Arbeit behandeln wir das Transportproblem mit Minimax-Zielfunktion. Wir zeigen, daß die Möglichkeit der Verbesserung der Lösung durch Umleitungen und Mehrlieferung in linearer Zeit entschieden werden kann. Wir formulieren neue Algorithmen, die die lexikographische Version des zugrundeligenden Minimax-Transportproblems, Reshipment und Overshipment Problems lösen. Die ersten beiden Probleme können dabei mit einem Algorithmus der KomplexitätO(n 2), mitn der Anzahl der Anbieter und Nachfrager, gelöst werden, während das Overshipment-Problem in linearer Zeit lösbar ist. Abschließend diskutieren wir Erweiterungen des Problems.
    Notes: Summary In this paper transportation problems with minimax objective are studied. It is shown that it can be decided in linear time whether reshipments and overshipments can improve the solution. Moreover, new algorithms are stated which solve even the lexicographic version of the underlying minimax transportation, reshipment and overshipment problems. The first two problems can be solved by an algorithm of time complexityO(n 2), wheren is the number of origins and destinations, whereas the overshipment problem is solved in linear time. Moreover, some extensions of the problems are addressed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01720146
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Buchbesprechungen (1984)
    Springer
    OR spectrum 6 (1984), S. 92-92 
    Details
    ISSN: 1436-6304
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01721083
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Buchbesprechungen (1986)
    Springer
    OR spectrum 8 (1986), S. 54-58 
    Details
    ISSN: 1436-6304
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01720777
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    On random quadratic bottleneck assignment problems (1982)
    Springer
    Mathematical programming 23 (1982), S. 227-232 
    Details
    ISSN: 1436-4646
    Keywords: Quadratic Bottleneck Assignment Problem ; Probabilistic Error Bounds
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The relative error between best and worst solution of quadratic bottleneck assignment problems with cost coefficientsd ijpq =a ip b jq is considered, wherea ip is either arbitrarily given or corresponds to a distance in the plane. It is shown that the relative error is bounded by a function∈(m), tending to zero, with probability tending to one asm → ∞, provided the data are uniformly distributed. This implies that any algorithm for the above mentioned problems yields asymptotically an arbitrarily small relative error with probability tending to one.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01583791
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Volume Maximization and Orthoconvex Approximation of Orthogons (1999)
    Springer
    Computing 63 (1999), S. 317-330 
    Details
    ISSN: 1436-5057
    Keywords: AMS Subject Classifications:90C27, 68Q25, 05B40, 52C15, 52C17, 90C35. ; Key words.Combinatorial optimization, geometric optimization, polynomially solvable cases, constrained critical path problem, orthoconvex approximation, VLSI design, cutting stock.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract. Let n axes-parallel hyperparallelepipeds (also called blocks) of the d-dimensional Euclidean space and a positive integer r be given. The volume maximization problem (VMP) selects at most r blocks such that the volume of their union becomes maximum. VMP is shown to be $\Cal{NP}$ -hard in the 2-dimensional case and polynomially solvable for the line via a constrained critical path problem (CCPP) in an acyclic digraph. This CCPP leads to further well solvable special cases of the maximization problem. In particular, the following approximation problem (OAP) becomes polynomially solvable: given an orthogon P (i.e., a simple polygon in the plane which is a union of blocks) and a positive integer q, find an orthoconvex orthogon with at most q vertices and minimum area, which contains P.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s006070050037
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Time-slot assignment for TDMA-systems (1985)
    Springer
    Computing 35 (1985), S. 99-112 
    Details
    ISSN: 1436-5057
    Keywords: 90C08 ; 90C10 ; Matrix decomposition ; time-slot assignment ; assignment problem ; max flow min cost flow problem ; computational complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Bei der Nachrichtenübertragung via Satelliten unter Benützung der TDMA-Technik, wie auch bei mannigfachen anderen technischen Systemen, tritt das Problem auf, daß eine gegebene (n×n)-Matrix mit nichtnegativen Elementen derart in eine Summe von Permutationsmatrizen zu zerlegen ist, daß die Summe der Gewichte minimal wird. Zunächst wird gezeigt, daß eine Optimallösung dieses Problems inO(n 4) Schritten konstruiert werden kann. Dabei werden maximaln 2−2n+2 verschiedene Permutationsmatrizen verwendet. Danach wird kurz die Zerlegung inn Matrizen diskutiert. Dieses Problem ist NP-schwer. Wenn 2n Permutationsmatrizen im vorhinein fixiert werden, kann eine optimale Zerlegung in eine gewichtete Summe dieser Permutationsmatrizen inO(n 3) Zeit durch das Lösen eines linearen Zuordnungsproblems gefunden werden. Dieses letztere Problem kann auf beliebige Boolesche Matrizen verallgemeinert werden. Dies führt dann auf ein maximales Flußproblem mit minimalen Kosten und kann daher ebenfalls durch einen echt-poynomialen Algorithmus gelöst werden.
    Notes: Abstract In satellite communication as in other technical systems using the TDMA-technique (time division multiple access) the problem arises to decompose a given (n×n)-matrix in a weighted sum of permutation matrices such that the sum of the weights becomes minimal. We show at first that an optimal solution of this problem can be obtained inO(n 4)-time using at mostO(n 2) different permutation matrices. Thereafter we discuss shortly the decomposition inO(n) different matrices which turns out to be NP-hard. Moreover it is shown that an optimal decomposition using a class of 2n permutation matrices which are fixed in advance can be obtained by solving a classical assignment problem. This latter problem can be generalized by taking arbitrary Boolean matrices. The corresponding decomposition problem can be transformed to a special max flow min cost network flow problem, and is thus soluble by a genuinely polynomial algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02260498
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Preface (1995)
    Springer
    Annals of operations research 57 (1995), S. ix 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02099686
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...