Hardness of Approximation

Kefˆlaio 1

MH PROSEGGISIMOTHTA

1.1 Eisagwg 

ρ.

Mèqri t¸ra èqoun anaferjeÐ proseggistikoÐ algìrijmoi oi opoÐoi eggu¸ntai parˆgonta prosèggishc Ta apotelèsmata autˆ ìmwc apoteloÔn èna ˆnw Ston ìrio sthn prosèggish sugkekrimènwn problhmˆtwn beltistopoÐhshc. parakˆtw pÐnaka anafèrontai sunoptikˆ merikˆ tètoia apotelèsmata.

Prìblhma

Parˆgontac

ρ

P ||Cmax ∆ -TSP Set Cover Edge Disjoint Paths

ρ ≤ 1 + ε, ∀ε ρ≤

3 2

ρ ≤ O(log n) ρ ≤ m2

1

Sthn enìthta aut n ja parousiastoÔn mejìdoi oi opoÐec mporoÔn na parˆxoun apotelèsmata pou apoteloÔn èna kˆtw ìrio sthn prosèggish sugkekrimènwn problhmˆtwn. Ta apotelèsmata autˆ ja mporoÔsan na perigrafoÔn wc arnhtikˆ apotelèsmata afoÔ apoteloÔn ena ìrio pèra apo to opoÐo ta probl mata sta opoÐa anafèrontai den mporoÔn na proseggistoÔn, ektìc an

P = NP.

Se autì to shmeÐo axÐzei na shmeiwjeÐ pwc metaxÔ tou kˆtw kai tou ˆnw orÐou

1

prosèggishc enìc probl matoc dhmiourgeÐtai èna kenì. EpijumÐa thc ereunhtik c koinìthtac eÐnai to kenì autì na kalufjeÐ, dhlad  to ˆnw kai to kˆtw ìrio na eÐnai Ðsa. Wstìso h epijumÐa aut  èqei ekplhrwjeÐ gia elˆqista probl mata (èna tètoio prìblhma eÐnai to 1 −ε 2 proseggisteÐ me parˆgonta ).

Edge Disjoint Paths

to opoÐo den mporeÐ na

m

Ta apotelèsmata mh proseggisimìthtac qwrÐzontai se 3 klˆseic.

Sthn

perÐptwsh twn problhmˆtwn elaqistopoÐhshc upˆrqoun oi akìloujec klˆseic (to

n •

anafèretai sto mègejoc tou stigmiotÔpou): stajerˆ

c>1

• Ω(log n) • nε

gia èna stajerì

ε>0

Sthn perÐptwsh twn problhmˆtwn megistopoÐhshc upˆrqoun oi akìloujec klˆseic:

•

stajerˆ

c0

Sthn pr¸th enìthta ja parou-

H sÔnoyh aut  ja èqei thn akìloujh dom .

sisteÐ h mèjodoc thc anagwg c eisagwg c qˆsmatoc. Sthn epìmenh enìthta ja parousiastoÔn oi mèjodoi anagwg c diat rhshc qˆsmatoc kai anagwg  enÐsqushc qˆsmatoc. Sthn teleutaÐa enìthta ja parousiastoun oi Pijanotikˆ elègximec apodeÐxeic

(PCP).

1.2

Anagwgèc eisagwg c qˆsmatoc

Oi teqnikèc...