WILBERT

Wildauer Bücher+E-Medien Recherche-Tool

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
    Online Resource
    Online Resource
    Amsterdam : North-Holland Pub. Co.
    Keywords: Discrete programmering ; Optimaliseren ; Mathematical optimization ; Optimisation mathematique ; Discrete programmering / gtt ; Optimaliseren / gtt
    Type of Medium: Online Resource
    Pages: 1 Online-Ressource (1 online resource (1 v.))
    ISBN: 9780444853226 , 0444853227
    Series Statement: Annals of discrete mathematics 4
    DDC: 519.7/2
    Language: English
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
  • 2
    Online Resource
    Online Resource
    Amsterdam : North-Holland Pub. Co.
    Keywords: Integer programming / Congresses ; Programmation en nombres entiers / Congres ; Konferenzschrift
    Type of Medium: Online Resource
    Pages: 1 Online-Ressource (1 online resource (vii, 562 p.))
    ISBN: 9780720407655 , 0720407656
    Series Statement: Annals of discrete mathematics 1
    Language: English
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Abstract An independence system Σ=(X, F) is called bimatroidal if there exist two matroidsM=(X F M) andN=(X, F N) such thatF=F M∪ FN. When this is the case, {M,N} is called a bimatroidal decomposition of Σ. This paper initiates the study of bimatroidal systems. Given the collection of circuits of an arbitrary independence system Σ (or, equivalently, the constraints of a set-covering problem), we address the following question: does Σ admit a bimatroidal decomposition {M,N} and, if so, how can we actually produce the circuits ofM andN? We derive a number of results concerning this problem, and we present a polynomial time algorithm to solve it when every two circuits of Σ have at most one common element. We also propose different polynomial time algorithms for set covering problems defined on the circuit-set of bimatroidal systems.
    Notes: Zusammenfassung Ein Unabhängigkeitssystem Σ=(X, F) heißt bimatroidal, wenn zwei MatroideM=(X, F M) undN=(X, F N) existieren, so daßF=F M∪ FN. In diesem Falle heißt {M,N} eine bimatroidale Zerlegung von Σ. In dieser Arbeit werden erstmals bimatroidale Systeme untersucht. Ist die Klasse aller Kreise eines beliebigen Unabhängigkeitssystems Σ (oder sind äquivalent damit die Restriktionen eines Mengenüberdeckunsproblems) gegeben, so stellt sich folgende Frage: erlaubt Σ eine bimatroidale Zerlegung (M, N), und wenn, wie können die Kreise vonM undN erzeugt werden? Für dieses Problem werden eine Reihe von Resultaten gezeigt. Ferner wird ein zeitpolynomialer Algorithmus für dieses Problem in dem Fall angegeben, daß je zwei verschiedene Kreise von Σ höchstens ein Element gemeinsam haben. Außerdem schlagen wir verschiedene zeitpolynomiale Algorithmen für Mengenüberdeckungsprobleme vor, die über der Klasse der Kreise bimatroidaler Systeme derfiniert sind.
    Type of Medium: Electronic Resource
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    ISSN: 1432-5217
    Keywords: pseudo-Boolean functions ; linear approximations ; least squares ; bestkth approximations ; power indices
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In dieser Arbeit wird die Approximation Pseudo-Boole'scher Funktionen lineare Funktionen bzw. allgemeiner durch Funktion kleiner/gleich eines festen Grades studiert. Dabei ist eine Pseudo-Boole'sche Funktion eine reellwertige Funktion definiert auf {0,1} n und ihr Grad ist jener des eindeutig bestimmten multilinearen Polynoms, durch die sie dargestellt werden kann. Lineare Funktionen sind jene mit einem Grad kleiner oder gleich Eins. Die Approximation besteht darin, daß unter allen linearen Funktionen jene mit dem kleinsten Euklidischen Abstand inR 2n gewählt wird. Es wird eine Charakterisierung der besten linearen Approximation durch den Mittelwert der Funktion und ihrer ersten Ableitungen angegeben. Sie führt auf eine explizite Formel, um die Approximation aus der Polynomform gegebenen Funktion zu berechnen. Diese Ergebnisse werden später verallgemeinert, um Approximationen höheren Grades zu behandeln. Ferner werden Ergebnisse bezüglich des Zusammenhanges von Approximationen verschiedenen Grades gewonnen. Im linearen Fall wird auch eine im gewissen Sinne eingeschränkte Approximationsaufgabe behandelt. Spezielle Betrachtung wird jenen wichtigen Eigenschaften Pseudo-Boole'scher Funktionen gezollt, die bei der Approximation erhalten bleiben. Ein weiterer Abschnitt zeigt die Relevanz linearer Approximationen in der Spieltheorie auf und zeigt Verbindungen zwischen den hier erzielten Ergebnissen und dem wohlbekannten Banzhaf Index auf.
    Notes: Abstract This paper studies the approximation of pseudo-Boolean functions by linear functions and more generally by functions of (at most) a specified degree. Here a pseudo-Boolean function means a real valued function defined on {0,1} n , and its degree is that of the unique multilinear polynomial that expresses it; linear functions are those of degree at most one. The approximation consists in choosing among all linear functions the one which is closest to a given function, where distance is measured by the Euclidean metric onR 2n . A characterization of the best linear approximation is obtained in terms of the average value of the function and its first derivatives. This leads to an explicit formula for computing the approximation from the polynomial expression of the given function. These results are later generalized to handle approximations of higher degrees, and further results are obtained regarding the interaction of approximations of different degrees. For the linear case, a certain constrained version of the approximation problem is also studied. Special attention is given to some important properties of pseudo-Boolean functions and the extent to which they are preserved in the approximation. A separate section points out the relevance of linear approximations to game theory and shows that the well known Banzhaf power index and Shapley value are obtained as best linear approximations of the game (each in a suitably defined sense).
    Type of Medium: Electronic Resource
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Es wird ein Verfahren vorgestellt, das für eine lineare UngleichungL in binären Variablen mit positiven ganzzahligen Koeffizienten alle Facetten der konvexen Hülle der Lösungen vonL bestimmt. Um diese Facetten für irgendeine UngleichungL mit rechter Seiteb zu erhalten, braucht man nur die Facetten des sogenannten Master-Knapsack-ProblemsM b zu kennen, dasO (b log b) Variablen besitzt. Fürb=1,..., 7 werden alle Facetten vonM b angegeben.
    Notes: Abstract A procedure is proposed that, given a linear inequalityL having positive integral coefficients in 0–1 variables, finds all the facets of the convex hull of the solutions ofL. This is done for allL by doing once and for all the computations for a particular sequenceM 1,M 2,... of such linear inequalities, called master knapsack problems. To find the facets for a givenL, it is enough to know the facets for the master knapsack problemM b, whereb is the free term inL (no matter how many variablesL might have). ThisM b has no more than order ofb logb variables. The procedure is based on polarity. All the facets forM 1,...,M 7 are tabulated.
    Type of Medium: Electronic Resource
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Summary RecentlyWilde andSanchez-Anton [1971] have studied monotonically increasing pseudo-Boolean functions, and have given a very efficient method for their minimization. The role of this note is to give an equivalent formulation of this property and to show how the new formulation makes it possible to read the sought minimum directly from the expression of the given function.
    Type of Medium: Electronic Resource
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    ISSN: 1573-7470
    Keywords: Propositional logic ; inference ; resolution ; Horn formulae ; complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper investigates the complexity of a general inference problem: given a propositional formula in conjunctive normal form, find all prime implications of the formula. Here, a prime implication means a minimal clause whose validity is implied by the validity of the formula. We show that, under some reasonable assumptions, this problem can be solved in time polynomially bounded in the size of the input and in the number of prime implications. In the case of Horn formulae, the result specializes to yield an algorithm whose complexity grows only linearly with the number of prime implications. The result also applies to a class of formulae generalizing both Horn and quadratic formulae.
    Type of Medium: Electronic Resource
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
  • 8
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 8 (1975), S. 179-206 
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The role of 0–1 programming problems having monotone or regular feasible sets was pointed out in [6]. The solution sets of covering and of knapsack problems are examples of monotone and of regular sets respectively. Some connections are established between prime implicants of a monotone or a regular Boolean functionβ on the one hand, and facets of the convex hullH of the zeros ofβ on the other. In particular (Corollary 2) a necessary and sufficient condition is given for a constraint of a covering problem to be a facet of the corresponding integer polyhedron. For any prime implicantP ofβ, a nonempty familyF(P) of facets ofH is constructed. Proposition 17 gives easy-to-determine sharp upper bounds for the coefficients of these facets whenβ is regular. A special class of prime implicants is described for regular functions and it is shown that for anyP in this class,F(P) consists of one facet ofH, and this facet has 0–1 coefficients. Every nontrivial facet ofH with 0–1 coefficients is obtained from this class.
    Type of Medium: Electronic Resource
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
  • 9
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 58 (1995), S. 201-226 
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We take a regression-based approach to the problem of induction, which is the problem of inferring general rules from specific instances. Whereas traditional regression analysis fits a numerical formula to data, we fit a logical formula to boolean data. We can, for instance, construct an expert system for fitting rules to an expert's observed behavior. A regression-based approach has the advantage of providing tests of statistical significance as well as other tools of regression analysis. Our approach can be extended to nonboolean discrete data, and we argue that it is better suited to rule construction than logit and other types of categorical data analysis. We find maximum likelihood and bayesian estimates of a best-fitting boolean function or formula and show that bayesian estimates are more appropriate. We also derive confidence and significance levels. We show that finding the best-fitting logical formula is a pseudo-boolean optimization problem, and finding the best-fitting monotone function is a network flow problem.
    Type of Medium: Electronic Resource
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...