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
    Randomized online algorithms for maximizing busy time interval scheduling (1996)
    Springer
    Computing 56 (1996), S. 95-104 
    Details
    ISSN: 1436-5057
    Keywords: 68M20 ; Probabilistic algorithm ; online scheduling ; interval ; busy time
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Wir betrachten das Problem der Zuteilung von Aufgaben bestimmter Rechenzeit auf einem Rechner, um so seine Auslastung zu maximieren. Die Aufgabe besteht darin, einen probabilistischen Online-Algorithmus mit vernünftigem worst-case Performance-Verhältnis zu finden. Wir geben die Antwort auf ein offenes Problem von Lipton und Tompkins, das das bestmögliche Verhältnis betrifft. Weiter verallgemeinern wir ihre Ergebnisse auf einm-Maschinen-Analogon. Schließlich wird eine Variante des Problems analysiert, in dem der Rechner mit einem Zwischenspeicher für einen Job versehen ist.
    Notes: Abstract We consider the problem of scheduling tasks requiring certain processing times on one machine so that the busy time of the machine is maximized. The problem is to find a probabilistic online algorithm with reasonable worst case performance ratio. We answer an open problem of Lipton and Tompkins concerning the best possible ratio that can be achieved. Furthermore, we extend their results to anm-machine analogue. Finally, a variant of the problem is analyzed, in which the machine is provided with a buffer to store one job.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02309339
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Interval orders without odd crowns are defect optimal (1987)
    Springer
    Computing 38 (1987), S. 59-69 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Der Defekt einer HalbordnungP ist definiert als der Korang der zugehörigen Inzidenzmatrix. Gierz und Poguntke [7] haben den Defekt als eine untere Schranke für die Anzahl von Paaren unvergleichbarer Elemente, die in einer gegebenen linearen Erweiterung benachbart auftreten können, nachgewiesen. Wir zeigen, daß für Intervallordnungen ohne ungerade Kronen die Schranke exakt ist, und wir geben einen effizienten Algorithmus zur Konstruktion linearer Erweiterungen an, die in diesem Fall die Schranke erreichen. Wir weisen weiter nach, daß die Menge der optimalen linearen Erweiterungen einer solchen Ordung in natürlicher Weise eine Matroidstruktur induziert, die sich zur Lösung des gewichteten Problems verwenden läßt.
    Notes: Abstract The defect of a (partial) order relationP is defined to be the rank of the kernel of the associated incidence matrix. Gierz and Poguntke [7] have shown that the defect provides a lower bound for the number of incomparable adjacent pairs in an arbitrary topological sorting ofP. We show that this bound is sharp for interval orders without odd crowns. Furthermore, an efficient algorithm for topological sortings of such orders is presented which achieves the bound. We finally exhibit a natural matroid structure associated with the optimal topological sortings under consideration, which permits to solve the weighted case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02253744
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    The Shapley value for cooperative games under precedence constraints (1992)
    Springer
    International journal of game theory 21 (1992), S. 249-266 
    Details
    ISSN: 1432-1270
    Keywords: Cooperative Game ; Shapley Value ; Precedence Constraint ; Marginal Contribution
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Cooperative games are considered where only those coalitions of players are feasible that respect a given precedence structure on the set of players. Strengthening the classical symmetry axiom, we obtain three axioms that give rise to a unique Shapley value in this model. The Shapley value is seen to reflect the expected marginal contribution of a player to a feasible random coalition, which allows us to evaluate the Shapley value nondeterministically. We show that every exact algorithm for the Shapley value requires an exponential number of operations already in the classical case and that even restriction to simple games is #P-hard in general. Furthermore, we outline how the multi-choice cooperative games of Hsiao and Raghavan can be treated in our context, which leads to a Shapley value that does not depend on pre-assigned weights. Finally, the relationship between the Shapley value and the permission value of Gilles, Owen and van den Brink is discussed. Both refer to formally similar models of cooperative games but reflect complementary interpretations of the precedence constraints and thus give rise to fundamentally different solution concepts.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01258278
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Book reviews (1998)
    Springer
    Journal of economics 67 (1998), S. 338-351 
    Details
    ISSN: 1617-7134
    Source: Springer Online Journal Archives 1860-2000
    Topics: Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01234649
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Book reviews (1991)
    Springer
    Mathematical methods of operations research 35 (1991), S. 346-349 
    Details
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01417522
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Some order dimension bounds for communication complexity problems (1991)
    Springer
    Acta informatica 28 (1991), S. 593-601 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary We associate with a general (0, 1)-matrixM an ordered setP(M) and derive lower and upper bounds for the deterministic communication complexity ofM in terms of the order dimension ofP(M). We furthermore consider the special class of communication matricesM obtained as cliques vs. stable sets incidence matrices of comparability graphsG. We bound their complexity byO((logd)·(logn)), wheren is the number of nodes ofG andd is the order dimension of an orientation ofG. In this special case, our bound is shown to improve other well-known bounds obtained for the general cliques vs. stable set problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01463947
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Book reviews (1985)
    Springer
    Mathematical methods of operations research 29 (1985), S. 132-139 
    Details
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Summary It is a pleasure to read this book. The state of art for Newton-type methods is given. It is strongly recommended also for teaching purposes. Numerical analysis is presented in an optimal way including both theory and computational aspects.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01918202
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Book reviews (1988)
    Springer
    Mathematical methods of operations research 32 (1988), S. 346-351 
    Details
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01920303
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Cores of games with restricted cooperation (1989)
    Springer
    Mathematical methods of operations research 33 (1989), S. 405-422 
    Details
    ISSN: 1432-5217
    Keywords: games ; restricted cooperation ; core ; convex functions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Spiele mit beschränkter Kooperation sind kooperativeN-Personenspiele mit Nebenzahlungen, wobei nicht jede Teilmenge von Spielern zulässig zu sein braucht. In diesem Sinn sind die Kooperationsmöglichkeiten beschränkt. Balancierte und vollständig balancierte Spiele werden in diesem Zusammenhang untersucht. Die entsprechenden Sätze über die Existenz von Kernen werden von einem Sandwichsatz über Mengenfunktionen im Rahmen der linearen Programmierung abgeleitet. Insbesondere werden allgemeine konvexe Spiele diskutiert, deren Bedeutung auch für die kombinatorische Optimierung Edmonds and Giles (1977) aufgezeigt haben.
    Notes: Abstract Games with restricted cooperation are cooperativeN-person games with sidepayments, where the collection of feasible coalitions need not comprise all subsets of players and thus is restricted. We study balanced and completely balanced games in this context and derive the corresponding core theorems from a sandwich theorem for set functions within the setting of linear programming. In particular, we discuss general convex games, which Edmonds and Giles (1977) have shown to be of particular importance also in combinatorial optimization.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01415939
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Simplices by point-sliding and the Yamnitsky-Levin algorithm (1997)
    Springer
    Mathematical methods of operations research 46 (1997), S. 131-142 
    Details
    ISSN: 1432-5217
    Keywords: Ellipsoid method ; linear programming ; simplex ; volume
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Yamnitsky and Levin proposed a variant of Khachiyan's ellopsoid method for testing feasibility of systems of linear inequalities that also runs in polynomial time but uses simplices instead of ellipsoids. Starting with then-simplexS and the half-space {x¦a Tx ≤ β}, the algorithm finds a simplexS YL of small volume that enclosesS ∩ {x¦a Tx ≤ β}. We interpretS YL as a simplex obtainable by point-sliding and show that the smallest such simplex can be determined by minimizing a simple strictly convex function. We furthermore discuss some numerical results. The results suggest that the number of iterations used by our method may be considerably less than that of the standard ellipsoid method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01199467
    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...