Pytania otagowane jako approximation-algorithms

Pytania dotyczące algorytmów aproksymacyjnych.

1
Przybliżony 1d TSP z porównaniami liniowymi?
Jednowymiarowy problem ścieżki sprzedawcy podróży jest oczywiście tym samym, co sortowanie, a zatem można go rozwiązać dokładnie przez porównanie w czasie , ale sformułowano go w taki sposób, aby przybliżenie, a także dokładne rozwiązanie ma sens. W modelu obliczeń, w którym dane wejściowe są liczbami rzeczywistymi i możliwe jest zaokrąglanie …
5
Teoretyczne zastosowania algorytmów aproksymacyjnych
Ostatnio zacząłem szukać algorytmów aproksymacyjnych dla problemów trudnych dla NP i zastanawiałem się nad teoretycznymi przyczynami ich badania. (To pytanie nie ma być zapalne - jestem po prostu ciekawy). Z badań algorytmów aproksymacyjnych wynikła pewna naprawdę piękna teoria - związek między twierdzeniem PCP a twardością aproksymacji, hipoteza UGC, algorytm aproksymacji …
1
Jakie są najlepsze możliwe kompromisy czas / błąd dla przybliżonego rozwiązania programów liniowych?
Dla konkretności rozważ LP za rozwiązanie gry dla dwóch graczy o sumie zerowej, w której każdy gracz ma akcji. Załóżmy, że każdy zapis macierzy wypłat ma najwyżej 1 wartość bezwzględną. Dla uproszczenia nie róbmy żadnych założeń sparity.nnnZAZAA Załóżmy, że środowisko wykonawcze jest dostępne w celu przybliżenia wartości tej gry.T.T.T Jedną …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
3
Luka integralności i współczynnik aproksymacji
Gdy weźmiemy pod uwagę algorytm aproksymacji dla problemu minimalizacji, luka integralności formuły IP dla tego problemu daje dolną granicę współczynnika aproksymacji dla pewnej klasy algorytmów (takich jak algorytm zaokrąglania lub pierwotny podwójny). W rzeczywistości istnieje wiele problemów, których najlepszy współczynnik aproksymacji odpowiada luce integralności. Niektóre algorytmy mogą mieć lepszy współczynnik …
1
Przybliżenie do zliczania liczby prostych ścieżek
I powiedziano, że istnieją dobre wielomianowe algorytmy czasu dla zbliżenia liczbę prostych odcinków w skierowanej wykresie począwszy od danego wierzchołka do danego zakończony wierzchołek T . Czy ktoś zna dobre referencje na ten temat?sssttt Tło: zliczanie dokładnej liczby ścieżek na ogólnym wykresie jest # P-pełne, ale mogą istnieć przybliżone wielomianowe …
3
Czy istnieje algorytm aproksymacji stałego współczynnika dla problemu kolorowania prostokąta 2D?
Problem, który rozważamy tutaj, to rozszerzenie znanego problemu kolorowania interwałów. Zamiast przedziałów uważamy prostokąty o bokach równoległych do osi. Celem jest pokolorowanie prostokątów przy użyciu minimalnej liczby kolorów, tak aby każdemu z dwóch nachodzących na siebie prostokątów przypisano różne kolory. Ten problem jest znany jako trudny dla NP. Xin Han, …
2
Charakterystyka problemów, dla których istnieją algorytmy czasu podliniowego
Zastanawiałem się, czy problemy, dla których istnieją algorytmy czasu podliniowego (w wielkości wejściowej), można scharakteryzować jako posiadające określone właściwości. Obejmuje to czas podliniowy (np. Testowanie właściwości, alternatywne pojęcie przybliżenia problemów decyzyjnych), przestrzeń podliniowa (np. Algorytmy szkicowania / przesyłania strumieniowego, w których maszyna Turinga ma taśmę tylko do odczytu, podliniową przestrzeń …
3
Dlaczego różnicowe współczynniki aproksymacji nie są dobrze zbadane w porównaniu ze standardowymi pomimo deklarowanych korzyści?
Istnieje standardowa teoria aproksymacji, w której stosunek aproksymacji wynosi supAOPTsupAOPT\sup\frac{A}{OPT} (dla problemów zcelamiMINMINMIN),AAA- wartość zwracana przez niektóre algorytmyAAAiOPTOPTOPT- wartość optymalna. I inna teoria, żeprzybliżenie różnicowe,gdzie stosunek przybliżenia wynosiinfΩ−AΩ−OPTinfΩ−AΩ−OPT\inf\frac{\Omega-A}{\Omega-OPT} ,ΩΩ\Omega- najgorsza wartość wykonalnego rozwiązania dla danego wystąpienia. Doautorówz tego twierdzenia teorii, że ma jakieś konkretne korzyści w stosunku do klasycznego jednego. …
2
Co wiadomo o tym wariancie TSP?
To pytanie zostało wcześniej opublikowane w Computer Science Stack Exchange tutaj . Wyobraź sobie, że jesteś odnoszącym sukcesy podróżnym sprzedawcą z klientami w całym kraju. Aby przyspieszyć wysyłkę, opracowałeś flotę dronów jednorazowego użytku o efektywnym zasięgu 50 kilometrów. Dzięki tej innowacji zamiast podróżować do każdego miasta w celu dostarczenia towarów, …
2
Przybliżenie w czasie podwykonawczym
Istnieją badania dotyczące algorytmów aproksymacyjnych dla całkowitych problemów NP w czasie wielomianowym i dokładnych algorytmów w czasie wykładniczym. Czy istnieją badania na temat algorytmów aproksymacyjnych dla kompletnych problemów NP w podwykładniczym czasie formy gdzie δ 2 ∈ ( 0 , 1 ) ?2nδ22nδ22^{n^{\delta_2}}δ2∈(0,1)δ2∈(0,1)\delta_2\in(0,1) Szczególnie interesuje mnie to, co wiadomo o …
1
Rozkłady grafów do łączenia „lokalnych” funkcji etykietowania wierzchołków
∑x∏i j ∈ Efa( xja, xjot)∑x∏jajot∈mifa(xja,xjot)\sum_x \prod_{ij \in E} f(x_i,x_j)maxx∏i j ∈ Efa( xja, xjot)maxx∏jajot∈mifa(xja,xjot)\max_x \prod_{ij \in E} f(x_i,x_j) Gdzie Max lub suma przejmuje wszystkie labelings z , produkt wprowadza się na wszystkie krawędzie dla grafu G = \ {V, E \} i f jest dowolną funkcją. Ilość ta jest …
2
Dowód użycia asystenta w badaniach teorii złożoności?
Biorąc pod uwagę tematy poruszane na konferencji, takie jak STOC, czy naukowcy zajmujący się algorytmem lub złożonością aktywnie korzystają z COQ lub Isabelle? Jeśli tak, to jak wykorzystują go w swoich badaniach? Zakładam, że większość ludzi nie użyłaby takich narzędzi, ponieważ dowody byłyby zbyt niskie. Czy ktoś używa tych asystentów …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.