Approximations of Lovász extensions and their induced interaction index

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 ▲]

Approximations of Lovasz extensions and their induced interaction index

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

The Lovász 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 \hat f : [0,1]^n --> R that ... [more ▼]

The Lovász 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 \hat f : [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 Lovász extension \hat f by Lovász 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 and then solved explicitly by Grabisch, Marichal, and Roubens, giving rise to an alternative definition of Banzhaf interaction index. Similarly we introduce a new interaction index from approximations of \hat f 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. [less ▲]

The maximum deviation just-in-time scheduling problem

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 ▲]

Production planning problems in printed circuit board assembly

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 ▲]