UNIVERSITY OF CALIFORNIA Santa Barbara Approximation Algorithms for Problems on Networks and Streams of Data A Dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Computer Science by Luca Foschini CommitteeinCharge: ProfessorS.Suri,Chair ProfessorJ.Gilbert ProfessorT.Gonzalez September2012 TheDissertationof LucaFoschiniisapproved: ProfessorJ.Gilbert ProfessorT.Gonzalez ProfessorS.Suri,CommitteeChairperson September2012 ApproximationAlgorithmsforProblemsonNetworksandStreamsofData Copyright(cid:13)c 2012 by LucaFoschini iii Tomybrother,andtoallthosewhocan’twaitto properlydecoratethisabundanceofwhitespace. iv Acknowledgements First and foremost, I would like to thank my advisor, Professor Subhash Suri, for his guidance during these years. I am very grateful for everything I have learned from him. Iwouldalsoliketothankmycommitteewhosefeedbackhasbeencrucialforthe developmentofthisdissertation. I greatly appreciated the mentorship of those who hosted me during my summer researchinternships,includingVahabMirrokniandEyalCarmiatGoogle,andProfessor WidmayeratETHZurich. Finally,Iwouldlike toacknowledgemyformerandcurrentlabmatesPegah, Kyle, Hakan,andSorabhfortheirassistanceandsupport. Otherswhohaveprovidedsignificant input and guidance along the way include Prof. Giovanni and Sebastiano Vigna, Dr. AntonioGulliandDr. AntonioSavona. Withoutanyofthem, thisdissertationwouldbe incomplete. v Curriculum Vitæ Luca Foschini Education 2012(Expected) PhDinComputerScience,UniversityofCalifornia, SantaBarbara. 2012 MasterofScienceinComputerScience,UniversityofCalifornia, SantaBarbara. 2007 Master of Engineering in Computer Engineering, University of Pisa, Pisa,Italy. (CumLaude) 2004 BachelorofEngineeringinComputerEngineering,UniversityofPisa, Pisa,Italy. (CumLaude) Experience 2012 Co-founderandChiefScientistatTheActivityExchangeInc. (AchieveMint) 2011 ResearchIntern,GoogleResearchNYC 2010 VisitingScholaratETHZurich,Zurich. 2005–2009 SoftwareEngineeratAsk.com 2004 ResearchInternatCERN,Geneva. vi SelectedPublications A.E.Feldmann,L.FoschiniBalancedPartitionsofTreesandAppli- cations. SubmittedtoAlgorithmica. L. Foschini, J. Hershberger, S. Suri On the Complexity of Time- DependentShortestPaths. SubmittedtoAlgorithmica. A. E. Feldmann and L. Foschini Balanced Partitions of Trees and Applications, 29th Symposium on Theoretical Aspects of Computer Science(STACS12) H.Yıldız, L.Foschini, J.Hershberger, S.SuriMaintainingtheVol- umeoftheUnionofBoxesandRelatedProblems,19thAnnualEuro- peanSymposiumonAlgorithms(ESA11) L. Cavedon, L. Foschini, G. Vigna Getting the Face Behind the Squares: ReconstructingPixelizedVideoStreams,5thUSENIXWork- shoponOffensiveTechnologies(WOOT11) S. Gauglitz, L. Foschini, M. Turk, T. Ho¨llerer Efficiently Selecting SpatiallyDistributedKeypointsforVisualTracking,IEEEInternational ConferenceonImageProcessing(ICIP11) F. Uyeda, L. Foschini, S. Suri, G. Varghese Efficiently Measuring BandwidthatAllTimeScales,8thUSENIXSymposiumonNetworked SystemsDesignandImplementation(NSDI11) vii L. Foschini, J. Hershberger, S. Suri On the Complexity of Time- DependentShortestPaths,22ndAnnualACM-SIAMSymposiumon DiscreteAlgorithms(SODA11) C. Buragohain, L. Foschini, S. Suri Untangling the Braid: Finding OutliersinaSetofStreams,SODAWorkshoponAlgorithmEngineer- ingandExperiments(ALENEX10) S. Gandhi, L. Foschini, S. Suri Space-efficient Online Approxima- tion of Time Series Data: Streams, Amnesia, and Out-of-order, 26th InternationalConferenceonDataEngineering(ICDE10) L.Foschini,R.Grossi,A.Gupta,J.S.VitterWhenindexingequals compression: Experimentswithcompressingsuffixarraysandapplica- tions,ACMTransactionsonAlgorithms2(4): 611-639(2006) L.Foschini,RGrossi,A.Gupta,J.S.VitterFastCompressionwith astaticmodelinHigh-OrderEntropy,2004IEEEDataCompression Conference(DCC04) M.Cococcioni,L.Foschini,B.Lazzerini,F.MarcelloniComplexity ReductionofMamdaniFuzzySystemsthroughMulti-valuedLogicMin- imization,2008IEEEInternationalConferenceonSystems,Manand Cybernetics(SMC08) L.Valcarenghi,L.Foschini,F.Paolucci,F.Cugini,andP.Castoldi TopologyDiscoveryServicesforMonitoringtheGlobalGridCommu- viii nicationsMagazine,OpticalControlPlaneforGridNetworks: Oppor- tunities,ChallengesandtheVision,March2006. L. Foschini, A. V. Thapliyal, L. Cavallaro, C. Kruegel, G. Vigna A Parallel Architecture for Stateful, High-Speed Intrusion Detection, FourthInternationalConferenceonInformationSystemsSecurity(ICISS 2008) A. Gulli, S. Cataudella, L. Foschini TC-SocialRank: Ranking the SocialWeb,The6thWorkshoponAlgorithmsandModelsfortheWeb Graph(WAW09) L.Valcarenghi,F.Paolucci,L.Foschini,F.Cugini,P.CastoldiCen- tralizedandDistributedGridTopologyDiscoveryServiceImplementa- tionsAcceptedasaPosteratHotInterconnects13,(IEEESymposium onHighPerformanceInterconnects). Patents A.Savona,A.Gulli,L.Foschini,Systemsandmethodsforselecting and organizing information using temporal clustering United States Patent: 20070260586 A. Savona, A. Gulli, L. Foschini, G. Deretta Systems and methods forclusteringinformationUnitedStatesPatent: 20090070346 ix Awards UCSBDean’sfellowship. UCSB2011-2012 Sant’Anna Scholarship. Full scholarship (room and board) for the fulldurationofundergraduateandgraduatestudies(2001-2007)atthe Sant’Anna School of Advanced Studies, Pisa, Italy as a winner of a nation-widecompetition. x