Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2 + ε)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.

Resistance responses blocking systemic movement of Potato virus A in potato

Peruna kestää A-virusta estämällä sen leviämistä Peruna on maissin ohella maailman kolmanneksi tärkein ravintokasvi vehnän ja riisin jälkeen. Perunaa lisätään kasvullisesti mukuloita istuttamalla, jolloin virukset siirtyvät sairaiden siemenmukuloiden välityksellä kasvukaudesta toiseen. Virustauteja voi torjua ainoastaan terveen siemenperunan ja kestävien lajikkeiden avulla. Kestävyys perustuu usein siihen, että kasvi estää viruksen leviämisen tartuntakohdasta välttyäkseen virustaudilta. Tässä työssä tutkittiin kolmea perunan A-viruksen (PVA) liikkumista estävää kestävyysmekanismia perunassa. Lisäksi työn kokeelliseen osaan oleellisesti kuuluvaa virustartutusta varten kehitettiin uusi paranneltu versio geenipyssystä. Tämä itse rakennettu laite optimoitiin PVA:n tartuttamiseen mahdollisimman helposti ja pienin käyttökustannuksin. Tutkimuksen kohteena olleessa perunan risteytysjälkeläistössä oli PVA:ta kestäviä kasveja (ryhmä nnr), jotka estivät viruksen liikkumisen aiheuttamatta oireita tartutuskohdassa, sekä kasveja, joissa PVA aiheutti kuolioläikkinä näkyvän yliherkkyysvasteen (ryhmä HR). Molemmissa kestävyystyypeissä virus pystyi monistumaan ja leviämään solusta soluun paikallisesti, mutta liikkuminen muihin kasvinosiin nilan kautta estyi. Ryhmän nnr kasveissa PVA-tartunta ei aiheuttanut tilastollisesti merkitsevää muutosta useimpien geenien ilmenemiseen tartuntakohdassa. Ainoastaan geeniperhe, joka ilmentää tiettyä proteinaasi-inhibiittoria (PI), reagoi PVA:han 24 tuntia tartutuksesta. Kun tämän PVA:han reagoivan geeniperheen jäsenet hiljennettiin nnr- perunalinjoissa, ne muuttuivat alttiiksi PVA:lle ja virus levisi tartuntakohdasta muihin kasvinosiin. Tulos osoittaa, että PI on viruskestävyystekijä. Lisäksi muut tutkimuksessa saadut tulokset tukevat mahdollisuutta, että PI estää PVA:n P1-proteinaasin toimintaa. HR-linjoissa todettiin erilaisiin puolustusvasteisiin liittyvien PR-geenien aktivoitumista PVA-tartunnan seurauksena, mutta myös ilman sitä kasvien kasvettua mullassa noin neljä viikkoa. Sen sijaan solukkoviljelyssä tai vasta kaksi viikkoa mullassa kasvaneissa kasveissa vastaavaa ei vielä todettu. Tulos viittaa siihen, että HR-perunat reagoivat herkemmin ympäristöön ja/tai kasvin kehitysasteeseen laukaisten puolustusvasteita, jotka saattavat parantaa kestävyyttä taudinaiheuttajia vastaan. Kolmas tutkittu kestävyystyyppi havaittiin Pito-perunalajikkeessa. Se muistutti nnr-kestävyyttä siten, että myös siinä viruksen liikkuminen nilassa muihin kasvinosiin estyi. PVA:n todettiin pysähtyvän vasta lehtiruodin tyvelle muodostuvaan irtoamisvyöhykkeeseen, mitä havainnollistettiin käyttämällä muunnettua PVA-rotua, joka tuotti UV-valossa fluoresoivaa vihreää valoa. Tulos viittaa siihen, että virus ei pääse kulkemaan vyöhykkeeseen kuuluvan suojaavan kerroksen läpi, jollei sillä ole pääsyä nilaan. Tällainen kestävyys on tarpeen, jotta virus ei voi korvata nilakuljetusta solusta soluun leviämisellä. Tulokset tuovat uusia näkökulmia kasvien viruskestävyyteen ja auttavat selittämään viruksen nilakuljetuksen estymistä sekä solusta soluun leviämisen pysähtymistä kestävissä kasveissa.

Kalman Filter Algorithm for Rating and Prediction in Basketball

The Thesis presents a state-space model for a basketball league and a Kalman filter algorithm for the estimation of the state of the league. In the state-space model, each of the basketball teams is associated with a rating that represents its strength compared to the other teams. The ratings are assumed to evolve in time following a stochastic process with independent Gaussian increments. The estimation of the team ratings is based on the observed game scores that are assumed to depend linearly on the true strengths of the teams and independent Gaussian noise. The team ratings are estimated using a recursive Kalman filter algorithm that produces least squares optimal estimates for the team strengths and predictions for the scores of the future games. Additionally, if the Gaussianity assumption holds, the predictions given by the Kalman filter maximize the likelihood of the observed scores. The team ratings allow probabilistic inference about the ranking of the teams and their relative strengths as well as about the teams’ winning probabilities in future games. The predictions about the winners of the games are correct 65-70% of the time. The team ratings explain 16% of the random variation observed in the game scores. Furthermore, the winning probabilities given by the model are concurrent with the observed scores. The state-space model includes four independent parameters that involve the variances of noise terms and the home court advantage observed in the scores. The Thesis presents the estimation of these parameters using the maximum likelihood method as well as using other techniques. The Thesis also gives various example analyses related to the American professional basketball league, i.e., National Basketball Association (NBA), and regular seasons played in year 2005 through 2010. Additionally, the season 2009-2010 is discussed in full detail, including the playoffs.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

An optimal local approximation algorithm for max-min linear programs

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.