Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Quadratization of symmetric pseudo-Boolean functions ; ; Crama, Yves et al in Discrete Applied Mathematics (2016), 203 A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to ${\bbr}$. For a pseudo-Boolean function $f(x)$ on $\{0,1 ... [more ▼] A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to ${\bbr}$. For a pseudo-Boolean function $f(x)$ on $\{0,1\}^n$, we say that $g(x,y)$ is a quadratization of $f$ if $g(x,y)$ is a Quadratic polynomial depending on $x$ and on $m$ auxiliary binary variables $y_1,y_2,\ldots,y_m$ such that $f(x)= \min \{ g(x,y) : y \in \{0,1\}^m \} $ for all $x \in \{0,1\}^n$. By means of quadratizations, minimization of $f$ is reduced to minimization (over its extended set of variables) of the quadratic function $g(x,y)$. This is of some practical interest because minimization of quadratic functions has been thoroughly studied for the last few decades, and much progress has been made in solving such problems exactly or heuristically. A related paper initiated a systematic study of the minimum number of auxiliary $y$-variables required in a quadratization of an arbitrary function $f$ (a natural question, since the complexity of minimizing the quadratic function $g(x,y)$ depends, among other factors, on the number of binary variables). In this paper, we determine more precisely the number of auxiliary variables required by quadratizations of \emph{symmetric} pseudo-Boolean functions $f(x)$, those functions whose value depends only on the Hamming weight of the input $x$ (the number of variables equal to 1). [less ▲] Detailed reference viewed: 82 (12 ULg)Influence and interaction indexes for pseudo-Boolean functions: a unified least squares approach ; Mathonet, Pierre in Discrete Applied Mathematics (2014), 179 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: 10 (0 ULg)The interval ordering problem ; ; et al in Discrete Applied Mathematics (2012) Detailed reference viewed: 11 (0 ULg)Approximations of Lovász extensions and their induced interaction index ; Mathonet, Pierre 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: 64 (10 ULg)Counting and enumerating aggregate classifiers ; Crama, Yves ; 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: 48 (14 ULg)Consensus algorithms for the generation of all maximal bicliques ; ; Crama, Yves 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: 83 (6 ULg)The maximum deviation just-in-time scheduling problem ; Crama, Yves 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: 178 (5 ULg)The commutative closure of a binary slip-language is context-free: a new proof Rigo, Michel 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: 19 (4 ULg)Production planning problems in printed circuit board assembly Crama, Yves ; ; 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: 347 (7 ULg) |
||