Interpolation by lattice polynomial functions: a polynomial time algorithm

Quentin Brabant (1) , Miguel Couceiro (1) , José Rui Figueira (2)

1 ORPAILLEUR - Knowledge representation, reasonning
2 CEG - IST - Center for Management Studies, Instituto Superior Técnico [Porto Salvo]

This paper deals with the problem of interpolating partial functions over finite distributive lattices by lattice polynomial functions. More precisely, this problem can be formulated as follows: Given a finite dis-tributive lattice L and a partial function f from D ⊆ L n to L, find all the lattice polynomial functions that interpolate f on D. If the set of lattice polynomials interpolating a function f is not empty, then it has a unique upper bound and a unique lower bound. This paper presents a new description of these bounds and proposes an algorithm for computing them that runs in polynomial time, thus improving existing methods. Furthermore, we present an empirical study on randomly generated datasets that illustrates our theoretical results.

Mots clés: multiple criteria evaluation; interpolation; lattice polynomials; non-additive measures; Distributive lattices

Domaines: Informatique [cs]; Mathématique discrète [cs.DM]

Quentin Brabant, Miguel Couceiro, José Rui Figueira. Interpolation by lattice polynomial functions: a polynomial time algorithm. Fuzzy Sets and Systems, 2019, 368, pp.101-118. ⟨10.1016/j.fss.2018.12.009⟩. ⟨hal-01958903v2⟩