资源描述：
《An approximation algorithm for max k-uncut with capacity constraints》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、NIIShonanMeetingReportNo.2011-1GraphAlgorithmandCombinatorialOptimizationSatoruIwataKen-ichiKawarabayashiFebruary13{18,2011NationalInstituteofInformatics2-1-2Hitotsubashi,Chiyoda-Ku,Tokyo,JapanGraphAlgorithmandCombinatorialOptimizationOrganizers:SatoruIwata(RIMS,Kyo
2、toUniversity)Ken-ichiKawarabayashi(NII)February13{18,2011Structuresthatcanberepresentedasgraphsareubiquitous,andmanyprac-ticalproblemscanberepresentedbygraphs.ThelinkstructureofawebinIn-ternetcouldberepresentedbyadirectedgraph:theverticesarethewebpagesavailableatthe
3、websiteandadirectededgefrompageAtopageBexistsifandonlyifAcontainsalinktoB.Agraphstructurecanbeextendedbyassigningaweighttoeachedgeofthegraph.Networkshavealsomanyusesinthepracticalsideofgraphtheory,networkanalysis(forexample,tomodelandanalyzetrafficnetworks).Withinnetw
4、orkanalysis,thede nitionofthetermetwork"varies,andmayoftenrefertoasimplegraph.Asimilarapproachcanbetakentoproblemsintravel,biology,computerchipdesign,andmanyother elds.Developmentofalgorithmstohandlegraphsisthereforeofmajorinterestincomputerscience.Theseapplicatio
5、nsofgraphsoftengivesrisetooptimization.Basicoptimiza-tionproblemsongraphs,includingtheshortestpath,maximum
ow,minimumspanningtreeproblemsallowefficientexactalgorithms.Thealgorithmicdevel-opmentsoftheseproblemshaveledtothetheoryofcombinatorialoptimization,combinedwithp
6、olyhedralcombinatorics,matroidsandsubmodularfunctions.Ontheotherhand,mostpracticaloptimizationproblemongraphssuchasthetravelingsalesman,stableset,maximumcutproblemsareNP-hard.Ap-proximationalgorithmsfortheseNP-hardcombinatorialoptimizationproblemshavebeeninvestigate
7、dextensivelyforacoupleofdecades.Designofapproxi-mationalgorithmsoftenrequiresdeepinsightsfromstructuralgraphtheoryandpolyhedralcombinatorics.Thepurposeofthisworkshopistobringexpertsingraphalgorithmandcombinatorialoptimizationtoshareideas,andtostimulatejointprojects.
8、1OverviewofTalksPropertiesofsparsegraphsZdenekDvorak,CharlesUniversity,PragueMyresearchconcernsmainlypropertiesofsparsegraphs,especiall
