Questions sur les algorithmes qui résolvent des problèmes jusqu'à une erreur limitée.
Je recherche un algorithme pour distribuer les valeurs d'une liste afin que la liste résultante soit aussi "équilibrée" ou "uniformément distribuée" que possible (entre guillemets car je ne suis pas sûr que ce soient les meilleures façons de la décrire ... plus tard, je fournirai un moyen de...
J'ai étudié quelque chose sur la complexité de Kolmogorov , lu des articles et des livres de Vitanyi et Li et utilisé le concept de la distance de compression normalisée pour vérifier la stilométrie des auteurs (identifier comment chaque auteur écrit des textes et des documents de groupe par leur...
J'aimerais commencer la question en disant que je suis programmeur et que je n'ai pas beaucoup d'expérience en théorie de la complexité. Une chose que j'ai remarquée est que bien que de nombreux problèmes soient NP-complets, lorsqu'ils sont étendus à des problèmes d'optimisation, certains sont...
J'ai un problème de décision NP-complet. Étant donné une instance du problème, je voudrais concevoir un algorithme qui génère OUI, si le problème est réalisable, et NON, sinon. (Bien sûr, si l'algorithme n'est pas optimal, il fera des erreurs.) Je ne trouve aucun algorithme d'approximation pour de...
J'ai regardé ce site et il dit que les gens ont trouvé des solutions pour les tournées TSP qui sont juste 0,031% plus élevées que la tournée optimale. Sans trouver le tour optimal, comment savent-ils quelle longueur il est censé
Le problème de bande passante minimale consiste à trouver un ordre des nœuds de graphique sur une ligne entière qui minimise la plus grande distance entre deux nœuds adjacents. Le problème de décision est NP-complet même pour les arbres binaires. Résultats de complexité pour la minimisation de la...
D'après ce que j'ai lu dans le preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D. Voici la définition PTAS : Un schéma d'approximation polynomiale du temps ( PTAS ) pour le...
Étant donné que l' énumération du chemin - est un problème # P-complet, pourrait-il y avoir des méthodes efficaces qui calculent (ou du moins approximent) la longueur moyenne du chemin - sans les énumérer? Que faire si les chemins sont autorisés à revoir les sommets?ssstttsssttt Des résultats...
Selon l'article de Wikipedia sur les schémas d'approximation du temps polynomial : Tous les problèmes dans FPTAS sont traitables à paramètres fixes. Ce résultat me surprend - ces classes semblent être totalement différentes les unes des autres. FPTAS caractérise les problèmes par leur facilité...
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...
Soit un problème de comptage connu pour être # -Complete .PΠΠ\PiPPP Cela implique-t-il que est -hard (c'est-à-dire qu'il n'y a pas de PTAS pour le problème sauf si )?A P X P = N
Le problème est le suivant: Nous avons un tableau / grille de nombres en deux dimensions, chacun représentant un «avantage» ou un «profit». Nous avons également deux entiers fixes et (pour "largeur" et "hauteur"). Et un entier fixe .h nwwwhhhnnn Nous souhaitons maintenant superposer rectangles de...
Soit une fonction assez agréable (par exemple, continue, différenciable, pas trop de maxima locaux, peut-être concave, etc.). Je veux trouver un maximum de : une valeur qui rend aussi grand que possible. f x ∈ R d f ( x )F: Rré→ Rf:Rd→Rf:\mathbb{R}^d \to \mathbb{R}Fffx ∈ Rréx∈Rdx \in \mathbb{R}^dF(...
j'ai un problème concernant la situation suivante. J'ai deux tableaux de nombres comme celui-ci: index/pos 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Array 1(i): 1 2 3 4 7 5 4 3 7 6 5 1 2 3 4 2 Array 2(j): 4 4 8 10 10 7 7 10 10 11 7 4 7 7 4 supposons maintenant que le deuxième tableau est très difficile...
Étant donné un programme entier (binaire) de la forme:0,10,10,1 mins.t.f(x)Ax=bxi≥0xi∈{0,1}∀i∀iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \quad \forall i \end{array} Notez que la taille de...
Soit le langage de toutes les formules -CNF , de sorte qu'au moins des clauses de puissent être satisfaites.LϵLϵL_\epsilon222φφ\varphi(12+ϵ)(12+ϵ)(\frac{1}{2}+\epsilon)φφ\varphi Je dois prouver qu'il existe st is -hard for any
Est-ce que le 2 dans un algorithme à 2 approximations signifie que la solution est dans 2 * OPT ou OPT /
Disons que j'ai trouvé un algorithme à 2 approximations pour un certain problème et je veux montrer que l'analyse est serrée. Dois-je maintenant trouver un exemple de taille générique ou suffit-il de montrer que j'ai un exemple de taille pour lequel l'algorithme donne ?nnndixdix102 O...
J'ai un problème logistique qui peut être vu comme une variante de TSPTSP\text{TSP}. C'est tellement naturel, je suis sûr qu'il a été étudié en recherche opérationnelle ou quelque chose de similaire. Voici une façon de voir le problème. J'ai entrepôts sur le plan cartésien. Il existe un chemin...