Library

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
    Springer
    Mathematical programming 14 (1978), S. 265-294 
    ISSN: 1436-4646
    Keywords: Heuristics ; Greedy Algorithm ; Interchange Algorithm ; Linear Programming ; Matroid Optimization ; Submodular Set Functions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetN be a finite set andz be a real-valued function defined on the set of subsets ofN that satisfies z(S)+z(T)≥z(S⋃T)+z(S⋂T) for allS, T inN. Such a function is called submodular. We consider the problem maxS⊂N{a(S):|S|≤K,z(S) submodular}. Several hard combinatorial optimization problems can be posed in this framework. For example, the problem of finding a maximum weight independent set in a matroid, when the elements of the matroid are colored and the elements of the independent set can have no more thanK colors, is in this class. The uncapacitated location problem is a special case of this matroid optimization problem. We analyze greedy and local improvement heuristics and a linear programming relaxation for this problem. Our results are worst case bounds on the quality of the approximations. For example, whenz(S) is nondecreasing andz(0) = 0, we show that a “greedy” heuristic always produces a solution whose value is at least 1 −[(K − 1)/K] K times the optimal value. This bound can be achieved for eachK and has a limiting value of (e − 1)/e, where e is the base of the natural logarithm.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 81 (1998), S. 229-256 
    ISSN: 1436-4646
    Keywords: Branch-and-cut algorithm ; Clustering ; Compiler design ; Equipartitioning ; Finite element method ; Graph partitioning ; Layout of electronic circuits ; Separation heuristics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we consider the problem ofk-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for cycle, cycle with ears, knapsack tree and path-block cycle inequalities among others. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including variables for the edges with nonzero costs and node partition variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    International journal of game theory 5 (1976), S. 227-238 
    ISSN: 1432-1270
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract An equivalence between simplen-person cooperative games and linear integer programs in 0–1 variables is presented and in particular the nucleolus and kernel are shown to be special valid inequalities of the corresponding 0–1 program. In the special case of weighted majority games, corresponding to knapsack inequalities, we show a further class of games for which the nucleolus is a representation of the game, and develop a single test to show when payoff vectors giving identical amounts or zero to each player are in the kernel. Finally we give an algorithm for computing the nucleolus which has been used successfully on weighted majority games with over twenty players.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical methods of operations research 36 (1992), S. 92-92 
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 5
    Title: Formulations and Valid Inequalities for the Node Capacitated Graph Partitioning Problem. /; Preprint SC 94-16
    Author: Ferreira, Carlos E.
    Contributer: Martin, Alexander , Souza, Cid C. de , Weismantel, Robert , Wolsey, L.
    Publisher: Berlin :Konrad-Zuse-Zentrum für Informationstechnik,
    Year of publication: 1994
    Series Statement: Preprint / Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 94-16
    ISSN: 0933-7911
    Type of Medium: Book
    Language: English
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 6
    Title: ¬The¬ Node Capacitated Graph Partitioning Problem: A Computational Study. /; Preprint SC 94-17
    Author: Ferreira, Carlos E.
    Contributer: Martin, Alexander , Souza, Cid C. de , Weismantel, Robert , Wolsey, L.
    Publisher: Berlin :Konrad-Zuse-Zentrum für Informationstechnik,
    Year of publication: 1994
    Series Statement: Preprint / Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 94-17
    ISSN: 0933-7911
    Type of Medium: Book
    Language: English
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...