Qu'est-ce qu'un algorithme d'approximation à deux critères?

Qu'est-ce qu'un algorithme d'approximation à deux critères? Cela continue de se produire dans le cas du clustering de flux de données. Est-ce lié à l'optimisation multi-objectifs?

C'est là que je l'ai rencontré: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. L'article porte sur une version en streaming de l'algorithme k-means. Il y a des références dans l'article mais aucune d'entre elles ne donne d'explication sur ce qu'est un algorithme d'approximation à deux critères. Je n'arrive pas à trouver quoi que ce soit sur Google qui me donnera une définition précise non plus.

Je développerai la réponse de Yuval Filmus en fournissant une interprétation basée sur des problèmes d'optimisation multi-objectifs .

Optimisation et approximation à objectif unique

En informatique, nous étudions souvent les problèmes d'optimisation avec un seul objectif (par exemple, minimiser f ( x ) soumis à une certaine contrainte). Pour prouver, par exemple, l'exhaustivité de NP, il est courant de considérer le problème budgétaire correspondant . Par exemple, dans le problème de la clique maximale, l'objectif est de maximiser la cardinalité de la clique, et le problème budgétaire est le problème de décider s'il existe une clique de taille au moins k , où k est donné dans le cadre de l'entrée à le problème.

Lorsqu'il n'est pas possible de calculer efficacement une solution optimale, comme dans le cas du problème de clique maximale, nous recherchons un algorithme d'approximation , une fonction qui génère une solution dans un facteur multiplicatif d'une solution optimale. Vous pouvez également envisager un algorithme d'approximation pour le problème budgétaire, une fonction qui génère une solution qui satisfait f ( x ) ≥ ck dans le cas d'un problème de maximisation, où c est un nombre inférieur à un. Dans cette situation, la solution peut violer la contrainte dure f ( x ) ≥ k , mais la "gravité" de la violation est limitée par c .

Optimisation multi-objectif et approximation bi-critère

Dans certains cas, vous souhaiterez peut-être optimiser deux objectifs simultanément. Pour un exemple approximatif, je peux vouloir maximiser mes "revenus" tout en minimisant mes "coûts". Dans une telle situation, il n'y a pas de valeur optimale unique, car il y a un compromis entre les deux objectifs; pour plus d'informations, consultez l'article Wikipedia sur l'efficacité de Pareto .

Une façon de transformer un problème d'optimisation à deux objectifs en un problème d'optimisation à objectif unique (pour lequel nous pouvons raisonner sur la valeur optimale de la fonction objectif) est de considérer les deux problèmes de contrainte , un pour chaque objectif. Si le problème est de maximiser simultanément f ( x ) tout en minimisant g ( x ), le premier problème de contrainte est de minimiser g ( x ) soumis à la contrainte f ( x ) ≥ k , où k est donné dans le cadre de l'entrée de ce problème d'optimisation à objectif unique. Le deuxième problème de contrainte est défini de manière similaire.

Un algorithme d'approximation ( α , β ) - bicriteria pour le premier problème de contrainte est une fonction qui prend un paramètre de budget k en entrée et sort une solution x telle que

• $f(x) \geq \alpha k$ ,
• $g(x) \leq \beta g(x^*)$ ,

où est une solution qui atteint la valeur optimale pour g . Un algorithme d'approximation à deux critères pour le deuxième problème de contrainte génère une solution telle que$x^*$

• $f(x) \geq \alpha f(x^*)$ ,
• $g(x) \leq \beta \ell$ ,

En d'autres termes, l'algorithme d'approximation à deux critères est simultanément une approximation du problème budgétaire dans le premier objectif et du problème d'optimisation dans le deuxième objectif. (Cette définition a été adaptée de la page quatre de « Optimisation submodulaire avec couverture submodulaire et contraintes de sac à dos submodulaire », par Iyer et Bilmes, 2013.)

Les inégalités changent de direction lorsque les objectifs passent du maximum au minimum ou vice versa.

Souvent, un problème d'optimisation implique plusieurs paramètres. Par exemple, considérons le problème du partitionnement des graphes. Étant donné un graphe pondéré, un entier et un paramètre , nous voulons partitionner le sommet défini en parties de taille au plus tout en minimisant le nombre d'arêtes coupées (arêtes reliant des sommets appartenant à différentes parties). Notez qu'il y a deux paramètres ici: et le nombre d'arêtes coupées.$k$$\rho$$k$$V_1,\ldots,V_k$$\rho$$E(V_1,\ldots,V_k)$$\rho$

Pour , un algorithme d'approximation produirait une partition où chaque partie est de taille au plus , et le nombre d'arêtes coupées est au plus , où est le nombre optimal d'arêtes coupées dans le problème d'origine , avec les pièces contraintes d'être au plus de taille .$f(n),g(n) \geq 1$$f(n),g(n)$$V_1,\ldots,V_k$$f(n)\rho$$g(n)\mathrm{OPT}$$\mathrm{OPT}$$\rho$

En d'autres termes, un algorithme d'approximation à deux critères atteint un certain rapport d'approximation tout en violant certaines contraintes d'une certaine quantité limitée. Pour un exemple d'algorithme d'approximation à deux critères pour le problème qui vient d'être décrit, voir cet article des frères Makarychev.