References of "Discrete Applied Mathematics"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailInfluence and interaction indexes for pseudo-Boolean functions: a unified least squares approach
Marichal, Jean-Luc; Mathonet, Pierre ULg

in Discrete Applied Mathematics (in press)

The Banzhaf power and interaction indexes for a pseudo-Boolean function (or a cooperative game) appear naturally as leading coefficients in the stan- dard least squares approximation of the function by a ... [more ▼]

The Banzhaf power and interaction indexes for a pseudo-Boolean function (or a cooperative game) appear naturally as leading coefficients in the stan- dard least squares approximation of the function by a pseudo-Boolean func- tion of a specified degree. We first observe that this property still holds if we consider approximations by pseudo-Boolean functions depending only on specified variables. We then show that the Banzhaf influence index can also be obtained from the latter approximation problem. Considering cer- tain weighted versions of this approximation problem, we introduce a class of weighted Banzhaf influence indexes, analyze their most important properties, and point out similarities between the weighted Banzhaf influence index and the corresponding weighted Banzhaf interaction index. We also discuss the issue of reconstructing a pseudo-Boolean function from prescribed influences and point out very different behaviors in the weighted and non-weighted cases. [less ▲]

Detailed reference viewed: 4 (0 ULg)
Full Text
Peer Reviewed
See detailThe interval ordering problem
Durr, Christophe; Queyranne, Maurice; Spieksma, Frits C.R. et al

in Discrete Applied Mathematics (2012)

Detailed reference viewed: 9 (0 ULg)
Full Text
Peer Reviewed
See detailApproximations of Lovász extensions and their induced interaction index
Marichal, Jean-Luc; Mathonet, Pierre ULg

in Discrete Applied Mathematics (2008), 156(1), 11-24

The Lovasz extension of a pseudo-Boolean function f : (0, 1)(n) -> R is defined on each simplex of the standard triangulation of [0, 1](n) as the unique affine function (f) over cap : [0, 1](n) -> R that ... [more ▼]

The Lovasz extension of a pseudo-Boolean function f : (0, 1)(n) -> R is defined on each simplex of the standard triangulation of [0, 1](n) as the unique affine function (f) over cap : [0, 1](n) -> R that interpolates f at the n + 1 vertices of the simplex. Its degree is that of the unique multilinear polynomial that expresses f. In this paper we investigate the least squares approximation problem of an arbitrary Lovasz extension (f) over cap by Lovasz extensions of (at most) a specified degree. We derive explicit expressions of these approximations. The corresponding approximation problem for pseudo-Boolean functions was investigated by Hammer and Holzman [Approximations of pseudo-Boolean functions; applications to game theory, Z. Oper. Res. 36(1) (1992) 3-21] and then solved explicitly by Grabisch et al. [Equivalent representations of set functions, Math. Oper. Res. 25(2) (2000) 157-178], giving rise to an alternative definition of Banzhaf interaction index. Similarly we introduce a new interaction index from approximations of (f) over cap and we present some of its properties. It turns out that its corresponding power index identifies with the power index introduced by Grabisch and Labreuche [How to improve acts: an alternative representation of the importance of criteria in MCDM, Internat. J. Uncertain. Fuzziness Knowledge-Based Syst. 9(2) (2001) 145-157]. (c) 2007 Elsevier B.V. All rights reserved. [less ▲]

Detailed reference viewed: 58 (10 ULg)
Full Text
Peer Reviewed
See detailCounting and enumerating aggregate classifiers
Adem, Jan; Crama, Yves ULg; Gochet, Willy et al

in Discrete Applied Mathematics (2008), 156(3), 2459-2468

We propose a generic model for the "weighted voting" aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to count the number of distinct ... [more ▼]

We propose a generic model for the "weighted voting" aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to count the number of distinct aggregate classifiers that arise in this model. When there are only two classes in the classification problem, we show that a class of functions that arises from aggregate classifiers coincides with the class of self-dual positive threshold Boolean functions. [less ▲]

Detailed reference viewed: 39 (14 ULg)
Full Text
Peer Reviewed
See detailConsensus algorithms for the generation of all maximal bicliques
Alexe, Gabriela; Alexe, Sorin; Crama, Yves ULg 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: 70 (6 ULg)
Full Text
Peer Reviewed
See detailThe maximum deviation just-in-time scheduling problem
Brauner, Nadia; Crama, Yves ULg

in Discrete Applied Mathematics (2004), 134(1-3), 25-50

This note revisits the maximum deviation just-in-time (MDJIT) scheduling problem previously investigated by Steiner and Yeomans. Its main result is a set of algebraic necessary and sufficient conditions ... [more ▼]

This note revisits the maximum deviation just-in-time (MDJIT) scheduling problem previously investigated by Steiner and Yeomans. Its main result is a set of algebraic necessary and sufficient conditions for the existence of a MDJIT schedule with a given objective function value. These conditions are used to provide a finer analysis of the complexity of the MDJIT problem. The note also investigates various special cases of the MDJIT problem and suggests several questions for further investigation. (C) 2003 Elsevier B.V. All rights reserved. [less ▲]

Detailed reference viewed: 164 (5 ULg)
Full Text
Peer Reviewed
See detailThe commutative closure of a binary slip-language is context-free: a new proof
Rigo, Michel ULg

in Discrete Applied Mathematics (2003), 131(3), 665-672

Using original arguments about sets of integers satisfying some first-order formula of the Presburger arithmetic <N, +>, we give a new proof that the commutative closure of a slip-language over a two ... [more ▼]

Using original arguments about sets of integers satisfying some first-order formula of the Presburger arithmetic <N, +>, we give a new proof that the commutative closure of a slip-language over a two letters alphabet is context-free. (C) 2003 Elsevier B.V. All rights reserved. [less ▲]

Detailed reference viewed: 17 (4 ULg)
Full Text
Peer Reviewed
See detailProduction planning problems in printed circuit board assembly
Crama, Yves ULg; van de Klundert, Joris; Spieksma, Frits CR

in Discrete Applied Mathematics (2002), 123(1-3), 339-361

This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical ... [more ▼]

This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical decomposition of the planning process into distinct optimization subproblems, addressing issues such as the assignment of board types to machine groups, the allocation of component feeders to individual machines, the determination of optimal production sequences, etc, The paper reviews the literature on this topic with an emphasis on the most recent developments, on the fundamental structure of the mathematical models and on the relation between these models and some 'environmental' variables such as the layout of the shop or the product mix. (C) 2002 Elsevier Science B.V, All rights reserved. [less ▲]

Detailed reference viewed: 269 (7 ULg)