APX luokka

APX-luokka (englannin sanasta "approximable") laskennallisen monimutkaisuuden teoriassa on NP-kovien ongelmien  luokka , joille on olemassa polynomin monimutkaisuuden approksimaatioalgoritmeja, joilla on vakio approksimaatiokerroin. Yksinkertaisesti sanottuna tämän luokan ongelmissa on tehokkaat algoritmit, jotka löytävät optimaalista huonompia ratkaisuja enintään kiinteällä prosentilla. Esimerkiksi konttien pakkausongelman ratkaisemiseksi on olemassa polynominen monimutkaisuusalgoritmi, joka käyttää enintään 5 % enemmän säiliöitä kuin pienin tarvittava määrä säiliöitä.

Approksimaatioalgoritmia kutsutaan c -approksimaatioalgoritmiksi, jolla on vakio c , jos voidaan osoittaa, että tällä algoritmilla saatu ratkaisu on enintään c kertaa huonompi kuin optimaalinen [1] .

Vakiota c kutsutaan approksimaatiokertoimeksi . Riippuen siitä, onko ongelma maksimointi- vai minimointiongelma, ratkaisu voi olla c kertaa suurempi tai c kertaa pienempi kuin optimaalinen.

Esimerkiksi sekä kärjenpeiteongelmalla että kolmio-epäyhtälön matkustavan myyjän ongelmalla on yksinkertaiset algoritmit, joille c = 2 [2] . Toisaalta on todistettu, että liikkuvan myyjän ongelmaa mielivaltaisilla reunapituuksilla (joka ei välttämättä täytä kolmion epäyhtälöä) ei voida approksimoida vakiokertoimella, koska Hamiltonin polun löytämisongelmaa ei voida ratkaista polynomiajassa (in tapaus P ≠ NP ) [3] .

Jos on olemassa algoritmi ongelman ratkaisemiseksi polynomiajassa mille tahansa kiinteälle kertoimelle, joka on suurempi kuin yksi (yksi algoritmi mille tahansa kertoimelle), ongelmalla sanotaan olevan polynomiajan approksimaatiomalli ( PTAS ) . Jos P ≠ NP, voidaan osoittaa, että on ongelmia, jotka ovat APX -luokassa, mutta eivät PTAS :ssa , eli ongelmia, jotka voidaan approksimoida jollain tekijällä, mutta ei millään tekijällä.

Ongelmaa kutsutaan APX -kovaksi, jos jokin APX -luokan ongelma voidaan tiivistää tähän ongelmaan, ja APX -täydellinen, jos ongelma on APX - hard ja itse kuuluu APX -luokkaan [1] . Epäyhtälö P ≠ NP viittaa siihen, että PTAS ≠ APX , P ≠ NP, joten mikään APX -kova ongelma ei kuulu PTAS :iin .

Jos ongelma on APX -kova, tämä on yleensä huono, koska P ≠ NP:lle se tarkoittaa, että PTAS -algoritmia ei ole, mikä on hyödyllisin approksimaatioalgoritmi. Yksi yksinkertaisimmista APX - täydellisistä ongelmista on Boolen kaavojen maksimitäytettävyysongelma , muunnos Boolen kaavan tyydyttävyysongelmasta . Tässä tehtävässä meillä on konjunktiivisessa normaalimuodossa looginen kaava , ja haluamme saada suurimman määrän osalausekkeita, jotka suoritetaan yhdellä vaihtamalla muuttujien tosi/epätosi-arvot. Huolimatta siitä, että ongelma ei todennäköisesti kuulu PTAS :iin, oikea arvo voidaan saada 30 %:n tarkkuudella ja joissakin ongelman yksinkertaistetuissa versioissa on PTAS [4] [5] [6] .

Esimerkkejä

• Christofides-algoritmi

Muistiinpanot

1. ↑ 1 2 Tjark Vredeveld. Kombinatoriset approksimaatioalgoritmit: taattu vs. kokeellinen suorituskyky. - Technische Universiteit Eindhoven, 2002. - P. 4.12. — ISBN 90-386-0532-3 .
2. ↑ kirjoittanut Dorit S. Hochbaum. Approksimaatioalgoritmit NP-koville ongelmille. - PWS Publishing Company, 1995. - P. 94-144. - ISBN 0-534-94968-1 .
3. ↑ Sanjeev Arora. NP-kovien ongelmien lähentyvyys. – Princetonin yliopisto.
4. ↑ MICHEL X. GOEMANS, DAVID P. WILLIAMSON. UUDET 3/4-LÄHESTYMINEN ALGORITMIT MAKSIMITYYTYVÄISYYDEN ONGELMAAN // SIAM J. DISC. MATH.. - 1994. - V. 7 , no. 4 . - S. 656-666 .
5. ↑ MICHEL X. GOEMANS, DAVID P. WILLIAMSON. Parannetut approksimaatioalgoritmit maksimileikkaus- ja tyydyttävyysongelmiin puolimäärityksellä // Journal of the Association for Computins Machinery. - 1995. - T. 42 , no. 6 . - S. 1115-1145 .
6. ↑ Miguel F. Anjos. Semidefinite Optimization Approaches for Satisfability and Maximum-Satisfability Problems // Journal on Satisfiability, Boolean Modeling and Computation. - 2005. - T. 1 . - S. 1-47 .

Linkit

• C. Papadimitriou ja M. Yanakakis. Optimointi-, approksimaatio- ja monimutkaisuusluokat. Journal of Computer and System Sciences, 43:425-440, 1991.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski ja Gerhard Woeginger. Maximum Satisfiability Arkistoitu 13. huhtikuuta 2007 Wayback Machinessa . Kokoelma NP-optimointiongelmista Arkistoitu 5. huhtikuuta 2007 Wayback Machineen . Päivitetty viimeksi 20. maaliskuuta 2000.