References of "Hammer, Peter L"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailLogical Analysis of Data: Classification with justification
Boros, Endre; Crama, Yves ULiege; Hammer, Peter L. et al

in Annals of Operations Research (2011), 188

Learning from examples is a frequently arising challenge, with a large number of algorithms proposed in the classification, data mining and machine learning literature. The evaluation of the quality of ... [more ▼]

Learning from examples is a frequently arising challenge, with a large number of algorithms proposed in the classification, data mining and machine learning literature. The evaluation of the quality of such algorithms is frequently carried out ex post, on an experimental basis: their performance is measured either by cross validation on benchmark data sets, or by clinical trials. Few of these approaches evaluate the learning process ex ante, on its own merits. In this paper, we dis- cuss a property of rule-based classifiers which we call "justifiability", and which focuses on the type of information extracted from the given training set in order to classify new observations. We investigate some interesting mathematical properties of justifiable classifiers. In partic- ular, we establish the existence of justifiable classifiers, and we show that several well-known learning approaches, such as decision trees or nearest neighbor based methods, automatically provide justifiable clas- sifiers. We also identify maximal subsets of observations which must be classified in the same way by every justifiable classifier. Finally, we illustrate by a numerical example that using classifiers based on "most justifiable" rules does not seem to lead to over fitting, even though it involves an element of optimization. [less ▲]

Detailed reference viewed: 82 (5 ULiège)
Full Text
See detailBoolean Functions: Theory, Algorithms, and Applications
Crama, Yves ULiege; Hammer, Peter L.

Book published by Cambridge University Press (2011)

This monograph provides the first comprehensive presentation of the theoretical, algorithmic and applied aspects of Boolean functions, i.e., {0,1}-valued functions of a finite number of {0,1}-valued ... [more ▼]

This monograph provides the first comprehensive presentation of the theoretical, algorithmic and applied aspects of Boolean functions, i.e., {0,1}-valued functions of a finite number of {0,1}-valued variables. The book focuses on algebraic representations of Boolean functions, especially normal form representations. It presents the fundamental elements of the theory (Boolean equations and satisfiability problems, prime implicants and associated representations, dualization, etc.), an in-depth study of special classes of Boolean functions (quadratic, Horn, shellable, regular, threshold, read-once, etc.), and two fruitful generalizations of the concept of Boolean functions (partially defined and pseudo-Boolean functions). It features a rich bibliography of about one thousand items. Prominent among the disciplines in which Boolean methods play a significant role are propositional logic, combinatorics, graph and hypergraph theory, complexity theory, integer programming, combinatorial optimization, game theory, reliability theory, electrical and computer engineering, artificial intelligence, etc. The book contains applications of Boolean functions in all these areas. [less ▲]

Detailed reference viewed: 813 (18 ULiège)
Full Text
See detailBoolean Models and Methods in Mathematics, Computer Science, and Engineering
Crama, Yves ULiege; Hammer, Peter L.

Book published by Cambridge University Press (2010)

This collection of papers proposes in-depth presentations of a variety of advanced topics related to Boolean functions and expressions. The chapters are written by some of the most prominent experts in ... [more ▼]

This collection of papers proposes in-depth presentations of a variety of advanced topics related to Boolean functions and expressions. The chapters are written by some of the most prominent experts in their respective fields, and cover topics ranging from algebra and propositional logic to learning theory, cryptography, computational complexity, electrical engineering, and reliability theory. Beyond the diversity of the questions raised and investigated in different chapters, a remarkable feature of the collection is the common thread created by the fundamental language, concepts, models and tools provided by Boolean theory. Many readers will certainly be surprised to discover countless links between seemingly remote topics discussed in various chapters of the book. They will hopefully be able to draw on such connections to further their understanding of their own scientific discipline and to explore new avenues for research. [less ▲]

Detailed reference viewed: 136 (17 ULiège)
Full Text
Peer Reviewed
See detailConsensus algorithms for the generation of all maximal bicliques
Alexe, Gabriela; Alexe, Sorin; Crama, Yves ULiege et al

in Discrete Applied Mathematics (2004), 145(1 Sp. Iss. SI), 11-21

We describe a new algorithm for generating all maximal bicliques (i.e. complete bipartite. not necessarily induced subgraphs) of a graph. The algorithm is inspired by, and is quite similar to. the ... [more ▼]

We describe a new algorithm for generating all maximal bicliques (i.e. complete bipartite. not necessarily induced subgraphs) of a graph. The algorithm is inspired by, and is quite similar to. the consensus method used in propositional logic. We show that some variants of the algorithm are totally polynomial, and even incrementally polynomial. The total complexity of the most efficient variant of the algorithms presented here is polynomial in the input size. and only linear in the output size. Computational experiments demonstrate its high efficiency on randomly generated graphs with up to 2000 vertices and 20,000 edges. (C) 2003 Elsevier B.V. All rights reserved. [less ▲]

Detailed reference viewed: 86 (6 ULiège)
Full Text
Peer Reviewed
See detailPseudo-Boolean optimization
Crama, Yves ULiege; Hammer, Peter L.

in Resende, M.G.C.; Pardalos, P.M. (Eds.) Handbook of Applied Optimization (2002)

This article briefly surveys some fundamental results regarding pseudo-Boolean functions.

Detailed reference viewed: 15 (1 ULiège)
Peer Reviewed
See detailBoolean normal forms, shellability and reliability computations
Boros, Endre; Crama, Yves ULiege; Ekin, Oya et al

in SIAM Journal on Discrete Mathematics (2000), 13

Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal ... [more ▼]

Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete. [less ▲]

Detailed reference viewed: 16 (1 ULiège)
Full Text
Peer Reviewed
See detailVariable and term removal from Boolean formulae
Crama, Yves ULiege; Ekin, Oya; Hammer, Peter L.

in Discrete Applied Mathematics (1997), 75

Given a Boolean formula in disjunctive normal form, the variable deletion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF ... [more ▼]

Given a Boolean formula in disjunctive normal form, the variable deletion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF satisfying some prescribed property. Similar problems can be defined with respect to the fixation of variables or the deletion of terms in a DNF. In this paper, we investigate the complexity of such problems for a broad class of DNF properties. [less ▲]

Detailed reference viewed: 25 (4 ULiège)
Full Text
Peer Reviewed
See detailA complexity index for satisfiability problems
Boros, Endre; Crama, Yves ULiege; Hammer, Peter L. et al

in SIAM Journal on Computing (1994), 23

This paper associates a linear programming problem (LP) to any conjunctive normal form p, and shows that the optimum value Z(p) of this LP measures the complexity of the corresponding SAT (Boolean ... [more ▼]

This paper associates a linear programming problem (LP) to any conjunctive normal form p, and shows that the optimum value Z(p) of this LP measures the complexity of the corresponding SAT (Boolean satisfiability) problem. More precisely, there is an algorithm for SAT that runs in polynomial time on the class of satisfiability problems satisfying Z(p) \leq 1 + \frac{c \log n}{n} for a fixed constant c, where n is the number of variables. In contrast, for any fixed \beta < 1, SAT is still NP-complete when restricted to the class of CNFs for which Z(p) \leq 1 + (1/n^\beta ). [less ▲]

Detailed reference viewed: 17 (0 ULiège)
Full Text
Peer Reviewed
See detailChvátal cuts and odd cycle inequalities in quadratic 0-1 optimization
Boros, Endre; Crama, Yves ULiege; Hammer, Peter L.

in SIAM Journal on Discrete Mathematics (1992), 5

In this paper a new lower bound for unconstrained quadratic 0-1 minimization is investigated. It is shown that this bound can be computed by solving a linear programming problem of polynomial size in the ... [more ▼]

In this paper a new lower bound for unconstrained quadratic 0-1 minimization is investigated. It is shown that this bound can be computed by solving a linear programming problem of polynomial size in the number of variables; and it is shown that the polyhedron S[3], defined by the constraints of this LP formulation is precisely the first Chvátal closure of the polyhedron associated with standard linearization procedures. By rewriting the quadratic minimization problem as a balancing problem in a weighted signed graph, it can be seen that the polyhedron defined by the odd cycle inequalities is equivalent, in a certain sense, with S[3]. As a corollary, a compact linear programming formulation is presented for the maximum cut problem for the case of weakly bipartite graphs. [less ▲]

Detailed reference viewed: 14 (0 ULiège)
Full Text
Peer Reviewed
See detailUpper-bounds for quadratic 0-1 maximization
Boros, Endre; Crama, Yves ULiege; Hammer, Peter L.

in Operations Research Letters (1990), 9

In this paper, three different approaches are generalised to obtain upper bounds for the maximum of a quadratic pseudo-Boolean function f over [0,1]^n. The original approaches (complementation ... [more ▼]

In this paper, three different approaches are generalised to obtain upper bounds for the maximum of a quadratic pseudo-Boolean function f over [0,1]^n. The original approaches (complementation, majorization and linearization) were introduced by Hammer, Hansen and Simeone. The generalization in this paper yields three upper bounds, Ck, Mk and Lk for each integer k ⩾ 2, where Cn = Ln = Mn is the maximum of f, and C2 = L2 = M2 is the roof duality bound studied by Hammer, Hansen and Simeone. It is proved that Ck = Mk = Lk for all values of k. [less ▲]

Detailed reference viewed: 18 (0 ULiège)
Full Text
Peer Reviewed
See detailPacking, covering and partitioning problems with strongly unimodular constraint matrices
Crama, Yves ULiege; Hammer, Peter L.; Ibaraki, Toshihide

in Mathematics of Operations Research (1990), 15

A 0-1 matrix A is called strongly unimodular if all its nonsingular square submatrices are triangular. We present an efficient algorithm for linear programming problems in binary variables, when all ... [more ▼]

A 0-1 matrix A is called strongly unimodular if all its nonsingular square submatrices are triangular. We present an efficient algorithm for linear programming problems in binary variables, when all constraints are of the packing, covering or partitioning type, and the constraint matrix is strongly unimodular. The algorithm uses a certain decomposition of strongly unimodular matrices into their so-called "restricted unimodular" components, and an efficient optimization algorithm for linear programs with restricted unimodular cosntraints. [less ▲]

Detailed reference viewed: 22 (0 ULiège)
Full Text
Peer Reviewed
See detailMore characterizations of triangulated graphs
Benzaken, Claude; Crama, Yves ULiege; Duchet, Pierre et al

in Journal of Graph Theory (1990), 14(4), 413-422

New characterizations of triangulated and cotriangulated graphs are presented. Cotriangulated graphs form a natural subclass of the class of strongly perfect graphs, and they are also characterized in ... [more ▼]

New characterizations of triangulated and cotriangulated graphs are presented. Cotriangulated graphs form a natural subclass of the class of strongly perfect graphs, and they are also characterized in terms of the shellability of some associated collection of sets. Finally, the notion of stability function of a graph is introduced, and it is proved that a graph is triangulated if and only if the polynomial representing its stability function has all its coefficients equal to 0, +1 or −1. [less ▲]

Detailed reference viewed: 23 (0 ULiège)
Full Text
Peer Reviewed
See detailPolynomial-time inference of all valid implications for Horn and related formulae
Boros, Endre; Crama, Yves ULiege; Hammer, Peter L.

in Annals of Mathematics & Artificial Intelligence (1990), 1

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 23 (0 ULiège)
Peer Reviewed
See detailBimatroidal independence systems
Crama, Yves ULiege; Hammer, Peter L.

in Zeitschrift für operations research (1989), 33

An independence system Σ=(X, F) is called bimatroidal if there exist two matroids M=(X,FM) and N=(X,FN) such that F=FM∪FN. When this is the case, {M,N} is called a bimatroidal decomposition of Σ. This ... [more ▼]

An independence system Σ=(X, F) is called bimatroidal if there exist two matroids M=(X,FM) and N=(X,FN) such that F=FM∪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 of M 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. [less ▲]

Detailed reference viewed: 25 (0 ULiège)
Peer Reviewed
See detailRecognition of quadratic graphs and adjoints of bidirected graphs
Crama, Yves ULiege; Hammer, Peter L.

in Bloom, G.S.; Graham, R.L.; Malkevitch, J. (Eds.) Combinatorial Mathematics : Proceedings of the Third International Conference (1989)

Detailed reference viewed: 18 (0 ULiège)
Full Text
Peer Reviewed
See detailA characterization of a cone of pseudo-Boolean functions via supermodularity-type inequalities
Crama, Yves ULiege; Hammer, Peter L.; Holzman, Ron

in Kall, P.; Kohlas, J.; Popp, W. (Eds.) et al Quantitative Methoden in den Wirtschaftswissenschaften (1989)

A pseudo-Boolean function is a real valued function defined on the vertices of the unit n-dimensional hypercube. It has a unique expression as a multilinear polynomial in n variables. It is called almost ... [more ▼]

A pseudo-Boolean function is a real valued function defined on the vertices of the unit n-dimensional hypercube. It has a unique expression as a multilinear polynomial in n variables. It is called almost-positive if all the coefficients in that expression, except maybe those in the linear part, are nonnegative. The almost-positive functions form a convex cone, given explicitly by its extreme rays. Here we describe this cone by a system of linear inequalities, which can be viewed as a natural generalization of supermodularity to higher orders. We also point out a characterization in terms of the sign of partial derivatives. [less ▲]

Detailed reference viewed: 38 (0 ULiège)
Full Text
Peer Reviewed
See detailProduct form parametric representation of the solutions to a quadratic boolean equation
Crama, Yves ULiege; Hammer, Peter L.; Jaumard, Brigitte et al

in RAIRO : Operations Research = Recherche Opérationnelle (1987), 21

A parametric représentation of the solutions to a consistent quadratic boolean equation in n variables is obtained. Each variable (or its complement) is expressed as a product of free boolean parameters ... [more ▼]

A parametric représentation of the solutions to a consistent quadratic boolean equation in n variables is obtained. Each variable (or its complement) is expressed as a product of free boolean parameters or their complements. These expressions provide a complete description of the solution set of the equation. An O (n^3) algorithm is proposed to produce such a representation. An application to the maximization of some classes of pseudoboolean functions is discussed. [less ▲]

Detailed reference viewed: 10 (0 ULiège)
Full Text
Peer Reviewed
See detailStrong unimodularity for matrices and hypergraphs
Crama, Yves ULiege; Hammer, Peter L.; Ibaraki, Toshihide

in Discrete Applied Mathematics (1986), 15

A 0–1 matrix A is called strongly unimodular if all the bases of (A, I) are triangular. We develop equivalent conditions for strong unimodularity, first in algebraic, then in graph theoretic terms. This ... [more ▼]

A 0–1 matrix A is called strongly unimodular if all the bases of (A, I) are triangular. We develop equivalent conditions for strong unimodularity, first in algebraic, then in graph theoretic terms. This provides a link with the theory of unimodular and balanced hypergraphs, and allows us to produce a polynomial-time recognition algorithm for strongly unimodular matrices. We consider next the constraint matrix of the problem obtained by linearizing a general, unconstrained optimization problem in 0–1 variables. Because that matrix has 0, 1 and −1 entries, we are led to introduce the concept of signed hypergraph in which every edge is affected of a positive or negative sign. Our results on strong unimodularity are extended to the class of signed hypergraphs. [less ▲]

Detailed reference viewed: 14 (0 ULiège)