Approksimointialgoritmit (kev¨ at 2010) Harjoitus 9 (12. huhtikuuta)
Ratkaisuja (Jouni Siren)
1. Osoitetaan, ett¨a mitk¨a tahansa n pistett¨a metrisess¨a avaruudessa (Rk, l1) voidaan kuvata et¨aisyydet s¨ailytt¨aen avaruuteen (Rm, l22) jollainm≥k.
Olkoon pisteiden joukko P. Muodostetaan bijektiot fi : P → {1, . . . , n} kaikilla i siten, ett¨a jokainen funktio fi on kasvava komponentin i suhteen. Lis¨aksi muodostetaan funktiot gi : {1, . . . , n} → R, joilla gi(j) = fi−1(j)i kaikilla i ja j. My¨os funktiot gi ovat kasvavia.
Etsitty kuvaus onh:Rk 7→R(n−1)k, miss¨a h(x) = (z1, . . . , zk) ja zi= (p
gi(2)−gi(1), . . . ,p
gi(fi(x))−gi(fi(x)−1),0, . . . ,0) kaikillai.
Olkootx, y∈P mielivaltaisia pisteit¨a. Nyt
||x−y||1=
k
X
i=1
||xi−yi||1 ja ||h(x)−h(y)||22=
k
X
i=1
||h(x)i−h(y)i||22,
joten riitt¨a¨a tarkastella mielivaltaista komponenttia i. Oletetaan yleisyydest¨a tinkim¨att¨a fi(x)< fi(y) ja merkit¨a¨ana=h(x)i sek¨ab=h(y)i. T¨all¨oin
||a−b||22 =
n−1
X
j=1
(aj−bj)2=
fi(y)−1
X
j=fi(x)
b2j =
fi(y)−1
X
j=fi(x)
(gi(j+ 1)−gi(j))
= gi(fi(y))−gi(fi(x)) =yi−xi=||yi−xi||1, joten||x−y||1=||h(x)−h(y)||22.
2. Approksimointisuhteen s¨ailytt¨av¨a palautus tasapainoisesta leikkauksesta mielivaltaisellab≤ 1/2 puolitusleikkaukseen (eli tapaukseenb= 1/2) saadaan lis¨a¨am¨all¨a verkkoon uusia solmuja, joihin ei liity yht¨a¨an kaarta. Solmuja lis¨at¨a¨an n solmun verkkoonm kappaletta niin, ett¨a bn+m= (n+m)/2.
Olkoon alkuper¨ainen verkko G ja lis¨aysten j¨alkeinen verkko G0. Nyt jokaista tasapainoista leikkausta (S, S) verkossa G vastaa kapasiteetiltaan yht¨a suuri verkon G0 puolitusleikkaus (S0, S0). T¨am¨a saadaan sijoittamalla lis¨atyt solmut leikkaukseen (S, S) niin, ett¨a kummankin puolen kooksi tulee (n+m)/2.
Toisaalta mielivaltaisesta verkon G0 puolitusleikkauksesta (S0, S0) saadaan kapasiteetiltaan yht¨a suuri verkonGleikkaus (S, S) poistamalla siit¨a kaikki lis¨atyt solmut. Koska|S0|=|S0|= (n+m)/2, on verkonGleikkauksen pienemm¨an puolen koko v¨ahint¨a¨an (n+m)/2−m=bn solmua. Kysymyksess¨a on siis verkon Gtasapainoinen leikkaus.
Koska jokaisesta verkon G tasapainoisesta leikkauksesta saadaan helposti kapasiteetiltaan yht¨a suuri verkonG0 puolitusleikkaus, ja p¨ainvastoin, on tasapainoisesta leikkauksesta app- roksimointisuhteen s¨ailytt¨av¨a palautus puolitusleikkaukseen.
3. Olkoon (V, d) jokin metriikka ja n = |V|. Luennoilla (sivut 293–312) esitettiin metriikan O(logn)-v¨a¨aristynyt l1-upotus O((logn)2)-ulotteiseen avaruuteen. Yleistet¨a¨an upotus nyt vastaavaksilp-upotukseksi mielivaltaisellap≥1.
Olkoon Q kohdeavaruuden ulottuvuuksien m¨a¨ar¨a. Valitaan joukot Si kaikilla 1 ≤ i ≤ Q vastaavalla tavalla kuin luennoilla. Etsitty upotus on σp : V → RQ, miss¨a σp(u) = x ja xi=d(u, Si)/Q1/p.
Olkootu, v∈V mielivaltaisia alkioita. Niiden v¨aliseksi et¨aisyydeksi upotuksessa tulee
||σp(u)−σp(v)||p =
Q
X
i=1
d(u, Si)
Q1/p −d(v, Si) Q1/p
p!1/p
= 1
Q
Q
X
i=1
|d(u, Si)−d(v, Si)|p
!1/p
≥ 1
Q
Q
X
i=1
|d(u, Si)−d(v, Si)|
!
=||σ1(u)−σ1(v)||1.
Et¨aisyys on siis v¨ahint¨a¨an yht¨a suuri kuin tapauksessap= 1. Luennoilla esitetyn mukaisesti kaikkien alkioparien v¨aliset et¨aisyydet ovat korkeintaanO(logn) kertaa pienempi¨a kuin met- riikassadainakin todenn¨ak¨oisyydell¨a 1/2. Riitt¨a¨a siis osoittaa, ettei mik¨a¨an et¨aisyys kasva suuremmaksi kuin metriikassad.
Kolmioep¨ayht¨al¨ost¨a seuraa|d(u, Si)−d(v, Si)| ≤d(u, v) kaikillai. N¨ain ollen
||σp(u)−σp(v)||p= 1 Q
Q
X
i=1
|d(u, Si)−d(v, Si)|p
!1/p
≤ 1
Q
Q
X
i=1
d(u, v)p
!1/p
=d(u, v).
Mink¨a¨an alkioparin v¨alinen et¨aisyys upotuksessa ei siis ole suurempi kuin metriikassa d.
