L'analyse lissée a été appliquée à plusieurs reprises pour comprendre le temps d'exécution d'algorithmes exacts pour de nombreux problèmes comme la programmation linéaire et les k-means. Il existe des résultats assez généraux dans ce domaine, par exemple Heiko Röglin et Berthold Vöcking, Smoothed...
Quelle est la relation entre PLSPLS\mathsf{PLS} et APXAPX\mathsf{APX} ? En d'autres termes, les problèmes qui admettent une recherche locale en temps polynomial sont-ils approximables? Les problèmes d'optimisation approximatifs impliquent-ils un algorithme de recherche local en
L' entrée est un univers et une famille de sous - ensembles de U , par exemple, F ⊆ 2 U . Nous supposons que les sous - ensembles de F peuvent couvrir U , c. -à- ⋃ E ∈ F E = U .UUUUUUF⊆ 2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃E∈ FE= U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Une séquence de recouvrement...
Quels sont les problèmes avec le meilleur rapport d'approximation connu obtenu par un algorithme renvoyant une solution uniformément aléatoire? Je connais un tel exemple pour le problème de magasin de flux de permutation : dans le document " Limites serrées pour la planification des ateliers de...
Je recherche un nom ou des références à ce problème. Étant donné un graphe pondéré G = ( V, E, w )G=(V,E,w)G = (V, E, w) trouver une partition des sommets jusqu'à n = | V|n=|V|n = |V|fixe S1, … , SnS1,…,SnS_1,\ldots,S_n façon à maximiser la valeur des arêtes coupées: c ( S1, … , Sn) = ∑i ≠ j⎛⎝∑( u...
Dans mon travail, le problème suivant se pose: Existe-t-il un algorithme connu, qui se rapproche du nombre chromatique d'un graphique sans un ensemble indépendant d'ordre 65? (Donc alpha (G) <= 64 est connu et | V | / 64 est une borne inférieure triviale, | V | une borne supérieure triviale....
Étant donné que 2 problèmes NP-complets sont par définition réductibles l'un à l'autre, une solution à l'un d'eux peut donc être obtenue en utilisant une boîte noire résolvant l'autre, pourquoi n'ont-ils pas des ratios d'approximation similaires (en se référant à leurs homologues d'optimisation )?...
Je serais très intéressé par les références à la théorie des fonctions sous-modulaires (des bases aux avancées). En particulier, j'étudie des approximations de problèmes d'optimisation difficiles et je souhaite développer mes fondations dans les fonctions sous-modulaires car elles sont pertinentes...
Ce problème a-t-il été étudié auparavant? Étant donné un graphe métrique non orienté G (les longueurs d'arête satisfont l'inégalité du triangle), trouver un ensemble S de sommets tel que MST (G [S]) est maximisé, où MST (G [S]) est l'arbre couvrant minimum du sous-graphe induit par S. Ce problème...
J'ai quelques millions de valeurs 32 bits. Pour chaque valeur, je veux trouver toutes les autres valeurs dans une distance de 5 brouillage. Dans l'approche naïve, cela nécessite des comparaisons O(N2)O(N2)O(N^2) , que je veux éviter. J'ai réalisé que si je traitais simplement ces valeurs 32 bits...
Dans un graphe dirigé, , F ⊂ E , si G ∖ F est un DAG (graphe acyclique dirigé), F est appelé un ensemble d'arc de rétroaction. G=(V,E)G=(V,E)G=(V,E)F⊂EF⊂EF\subset EG∖FG∖FG\setminus FFFF Si chaque bord est associé à un poids , le problème de jeu d'arc à rétroaction de coût minimum est de trouver un...
Le lemme de Johnson-Lindenstrauss dit grosso modo que pour toute collection de points dans , il existe une carte où tel que pour tout : Il est connu que des instructions similaires ne sont pas possibles pour la métrique , mais est-il connu s'il existe un moyen de contourner une telle baisse limites...
Les algorithmes d'approximation peuvent donner une sortie jusqu'à un facteur constant. C'est un peu moins satisfaisant que les algorithmes exacts. Cependant, des facteurs constants sont ignorés dans la complexité temporelle. Je me demande donc si l'astuce suivante est possible ou a été utilisée...
(X,d)(X,d)(X, d)(Y,f)(Y,f)(Y, f)μ:X→Yμ:X→Y\mu : X \rightarrow Yμμ\muρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)}ρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)} \rho = \max_{p,q \in X} \{ \frac{d(x,y)}{f(\mu(x), \mu(y))}, \frac{f(\mu(x), \mu(y))}{d(x,y)} \} Il existe cependant d'autres...
On nous donne un matroïde. Notre objectif est de trouver un ensemble d'éléments de taille minimale ayant une intersection non vide avec chaque base du matroïde. Le problème est-il étudié auparavant? Est-ce en P? Par exemple, dans un matroïde couvrant un arbre, l'ensemble de frappe minimum doit être...
Je connais l'algorithme de descente de gradient qui peut trouver le minimum local (maximum) d'une fonction donnée. Y a-t-il une modification de la descente du gradient qui permet de trouver le minimum absolu (maximum), où la fonction a plusieurs extrema locaux? Existe-t-il des techniques générales,...
J'ai une question de faisabilité qui peut être formulée comme suit. On me donne un point dans un espace vectoriel dimensionnel, et je veux trouver le point le plus proche de qui satisfait un ensemble de " contraintes" de la formed q p ℓ 0pppdddqqqpppℓ0ℓ0\ell_0 Étant donné un ensemble , au plus l'un...
Il semble y avoir de nombreux algorithmes randomisés pour les tests d'identité polynomiale, vérifiant si un polynôme donné est nul ou non. Y a-t-il des résultats d'algorithmes qui font une sorte d'estimation des polynômes sur un ensemble spécifique de points? Cela pourrait être, par exemple, une...
Le théorème de Borsuk-Ulam dit que pour chaque fonction impaire continue ggg d'une sphère n dans un espace n euclidien, il y a un point X0x0x_0 tel que g( x0) = 0g(X0)=0g(x_0)=0 . Simmons et Su (2002) décrivent une méthode pour approximer le point X0X0x_0 utilisant le lemme de Tucker . Cependant,...
Considérez le problème de l'ensemble dominant dans les graphiques généraux, et soit le nombre de sommets dans un graphique. Un algorithme d'approximation gourmand donne une garantie d'approximation du facteur 1 + log n , c'est-à-dire qu'il est possible de trouver en temps polynomial une solution S...