Mathematics – Combinatorics
Scientific paper
2007-06-26
Discrete Applied Mathematics 156 (1) (2008) 11-24
Mathematics
Combinatorics
19 pages
Scientific paper
The Lovasz extension of a pseudo-Boolean function $f : \{0,1\}^n \to R$ is defined on each simplex of the standard triangulation of $[0,1]^n$ as the unique affine function $\hat f : [0,1]^n \to 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 $\hat f$ 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 (1992) and then solved explicitly by Grabisch, Marichal, and Roubens (2000), 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 (2001).
Marichal Jean-Luc
Mathonet Pierre
No associations
LandOfFree
Approximations of Lovasz extensions and their induced interaction index does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximations of Lovasz extensions and their induced interaction index, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximations of Lovasz extensions and their induced interaction index will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-506242