Pourquoi les ratios d'approximation différentiels ne sont-ils pas bien étudiés par rapport aux ratios standard malgré leurs avantages revendiqués?

$\sup\frac{A}{OPT}$ $MIN$ $A$ $A$ $OPT$ $\inf\frac{\Omega-A}{\Omega-OPT}$ $\Omega$

il donne le même rapport d'approximation pour des problèmes tels que la couverture minimale des sommets et l'ensemble indépendant maximal qui sont connus pour être des réalisations différentes du même problème;
il donne le même rapport pour les versions max et min du même problème. En même temps, nous savons que dans la théorie standard, les MIN TSP et MAX TSP ont des rapports très différents.
Il mesure la distance non seulement à l'optimum mais aussi au pessimum $\Omega$ . Donc, dans le cas de la théorie d'approximation standard de Vertex Cover, $2$ est la meilleure borne supérieure. Mais l'essentiel $2$ est le rapport maximum entre le pessimum et l'optimum. Ainsi, un tel algorithme est garanti pour produire la solution avec la pire valeur.

Mon argument pro est le suivant: dans l'analyse asymptotique, nous ne prenons pas en compte les constantes et les termes d'ordre bas (ici, je me souviens de la citation d'Avi Widgerson: "Nous réussissons parce que nous utilisons le bon niveau d'abstraction.") Et c'est le niveau d'abstraction pour comparer l'utilisation des ressources par l'algorithme. Mais lorsque nous étudions l'approximation, nous introduisons pour une raison quelconque la différence dans les endroits où nous pouvons l'éviter.

Ma question est

pourquoi la théorie d'approximation différentielle si mal étudiée. Ou les arguments impliqués ne sont-ils pas suffisamment solides?

ds.algorithms approximation-algorithms approximation-hardness Oleksandr Bondarenko
la source

Je n'ai jamais vu cette notion auparavant et je pense qu'elle est au moins intéressante. Très curieux des réponses! (bien que la vraie raison puisse être aussi triviale que "Doh, je n'y ai jamais pensé" ou "Les preuves deviennent plus difficiles" ou "Je ne peux pas comparer cela à d'autres résultats quand je commence")

Raphael

Réponses:

Il existe deux interprétations de la revendication "l'algorithme trouve une approximation du problème " $A$ $\alpha$ $P$ :

Le problème est facile à résoudre assez bien, car nous avons un algorithme qui trouve une bonne approximation. $P$
L'algorithme est bon , car il trouve une bonne approximation. $A$

Je pense que la définition classique du facteur d'approximation met l'accent sur la première interprétation. Nous classons les problèmes en fonction de leur facilité de résolution.

Le rapport d'approximation différentielle semble donner un peu plus de poids à la deuxième interprétation: nous ne voulons pas "récompenser" les algorithmes triviaux (par exemple, les algorithmes qui sortent juste un ensemble vide, ou l'ensemble de tous les nœuds).

Bien sûr, les deux sont des points de vue valides, mais ce sont des points de vue différents .

Nous pouvons également étudier la question d'un point de vue un peu plus pratique. Malheureusement, les couvertures de sommets en tant que telles n'ont pas beaucoup d'utilisations directes, mais pour les besoins de l'argument, considérons ces deux applications (quelque peu artificielles):

Couverture de sommet: les nœuds sont des ordinateurs et les bords sont des liens de communication; nous voulons surveiller toutes les liaisons de communication et donc au moins un point d'extrémité de chaque front doit exécuter un processus spécial.
Ensemble indépendant: les nœuds sont des ouvriers et les bords modélisent les conflits entre leurs activités; nous voulons trouver un ensemble d'activités sans conflit pouvant être effectuées simultanément.

Maintenant, les deux problèmes ont une solution triviale: l'ensemble de tous les nœuds est une couverture de sommets et l'ensemble vide est un ensemble indépendant.

La principale différence est qu'avec le problème de la couverture des sommets, la solution triviale fait le travail . Bien sûr, nous utilisons plus de ressources que nécessaire, mais au moins nous avons une solution que nous pouvons utiliser dans la pratique. Cependant, avec le problème d'ensemble indépendant, la solution triviale est complètement inutile . Nous ne faisons aucun progrès. Personne ne fait rien. La tâche n'est jamais terminée.

De même, nous pouvons comparer les solutions presque triviales: couverture sommet qui se compose des extrémités d'une correspondance maximale, et ensemble indépendant qui est le complément de . Encore une fois, certainement le travail dans notre application, et cette fois, nous ne gaspillons pas les ressources de plus du facteur deux. Cependant, pourrais être à nouveau un ensemble vide, ce qui est complètement inutile. $C$ $I$ $C$ $C$ $I$

La définition standard de la garantie d'approximation nous indique donc directement si la solution est utile ou non. Une approximation 2 de la couverture des sommets fait le travail. Un ensemble indépendant sans aucune garantie d'approximation pourrait être complètement inutile.

Dans un sens, le rapport d'approximation différentielle essaie de mesurer «à quel point la solution est non triviale», mais est-ce important dans l'une ou l'autre de ces applications? (Est-ce important dans n'importe quelle application?)

Jukka Suomela
la source

Je ne comprends pas votre point dans la deuxième partie. Tout choix d'approximation des sommets est une couverture de vertex faisable, nous n'avons pas besoin de savoir que l'algorithme est une approximation à 2 pour cela. D'un autre côté, même une approximation 2 pour un ensemble indépendant pourrait très bien aboutir à une solution irréalisable. Il apparaît donc que le danger d'infaisabilité est lié au problème et non à des limites d'approximation (inconnues).

Raphael

@Raphael: Une approximation 2 de l'ensemble indépendant maximum est, par définition, un ensemble indépendant (et assez grand; certainement pas un ensemble vide).

Jukka Suomela

Tant pis, lisez trop vite. Mais encore, je pense que votre point devrait être formulé comme: Un algorithme sans garantie d'approximation fait le travail en cas de VC, mais pas en IS. (Vous comparez des pommes et des poires, n'est-ce pas?) Mais alors, comment cette étude se rapporte-t-elle au choix de la garantie? L'un ou l'autre ferait pour opter pour des solutions réalisables.

Raphael

@Raphael: Non, je dis que le VC trivial a une garantie d'approximation finie (quelque chose comme ), et il fait le travail, tandis que le SI trivial n'a pas de garantie d'approximation finie, et il n'a pas finis le travail. Par conséquent, les garanties d'approximation indiquent au moins quelque chose sur l'utilité de la solution.

O (Δ)

$O(\Delta)$

Jukka Suomela

+1 parce que les exemples sont amusants. Je ne pense pas qu'il y ait une différence bien définie entre «le problème est facile» et «il y a un bon algorithme», mais je le comprends en quelque sorte à un niveau vague.

Tsuyoshi Ito

Je ne connais pas la notion d'approximation différentielle et je n'ai aucune théorie pour expliquer pourquoi elle n'est pas bien étudiée. Cependant, je voudrais souligner qu'il n'est pas toujours souhaitable de décrire les performances d'un algorithme d'approximation par une seule mesure. En ce sens, je trouve difficile de convenir qu'une mesure est meilleure qu'une autre.

Par exemple, comme vous l'avez dit, la couverture minimale des sommets admet un algorithme d'approximation à temps polynomial alors qu'il est difficile de NP d'appréhender un ensemble indépendant maximum à n'importe quel rapport constant. Bien que je comprenne que cela peut être surprenant à première vue, il a une signification légitime: (1) la couverture minimale des sommets peut être bien approchée quand elle est petite mais (2) elle ne peut pas être bien approchée quand elle est grande. Lorsque nous déclarons qu'il est difficile de NP d'approximer la couverture minimale des sommets (et l'ensemble indépendant maximum) avec un rapport d'approximation différentielle constante positive, nous ignorons effectivement la propriété (1). Il est probablement suffisant pour certaines raisons d'ignorer la propriété (1), mais ce n'est certainement pas toujours le cas.

Notez que nous n'utilisons pas toujours le rapport d'approximation pour décrire les performances des algorithmes d'approximation. Par exemple, pour énoncer un résultat d'inapproximabilité basé sur le théorème PCP dans sa pleine généralité, nous avons besoin de la formulation basée sur des problèmes d'écart. Voir ma réponse à une autre question pour plus de détails. Dans ce cas, ni en utilisant le rapport d'approximation standard ni en utilisant le rapport d'approximation différentielle ne nous permet d'énoncer le résultat en général.

Tsuyoshi Ito
la source

0

$0$

2

$2$

O P T ⩾ n / 2

$OPT\geqslant n/2$

@Oleksandr: «Dans le cas de Vertex Cover, si l'approximation coïncide avec la pire solution lorsque OPT⩾n / 2, nous avons le ratio 2.» Que vous le considériez comme un inconvénient ou non est un point de vue. On peut soutenir que si chaque solution a la valeur objective dans un facteur de 2, alors peu importe la solution produite par un algorithme. Le rapport d'approximation standard modélise la situation comme celle-ci.

Tsuyoshi Ito,

Si ce facteur de 2 ou tout autre petit facteur est la pire solution, un tel résultat est peu utile.

Oleksandr Bondarenko

@Oleksandr: Comme je l'ai dit, c'est un point de vue.

Tsuyoshi Ito du

Comme Tsuyoshi le fait remarquer, le problème pourrait être de savoir quel type d'argument vous souhaitez utiliser la borne obtenue. Dans ce qui suit, je vais essayer de développer deux motivations différentes.

$\alpha = \frac{A}{OPT}$

$\alpha = \frac{\Omega - A}{\Omega - OPT}$ $\alpha\cdot 100\%$

Donc, selon le type de déclaration que la borne dérivée doit sauvegarder, vous devez choisir l'alternative appropriée.

$[\Omega, OPT]$

Raphael
la source