http://www.informatik.uni-trier.de/~ley/db/conf/soda/soda2006.html
SODA 2006
http://doi.acm.org/10.1145/1109557.1109619	61	On the tandem duplication-random loss model of genome rearrangement	academic aggregating aggregation ailon algorithms analysis ancient andrej animal animals annu applications approximating approximation arbitrary arora arrangement articulate assignment associates aury bensch best bibe biol biology birren bogdanov boore brachiop breakp brown brunet caprara cerevisiae charikar clustering cocoon combinatiorial comparative complete computational conf content contiguous cuts data deep deletions dense depamphilis deuterostome deyoung directed discussions distance distances dowling duplication dwork each early earnest eccc ecol edes editor editors eels ermutations etween even evol evolution evolutionary exemplified extensive feedback felsenstein fish focs formulations frieze from gascuel gene genome genomes genomic genomics grant graph graphs gulp hardness hein helfenb helpful however inconsistent inferring information inoue insertions integer iterate iteration jaillon jeff kaplan karyotyp kellis kluwer know kumar lagergren lander large lavrov loss mabrouk marron mathematics mechanisms median methods mexico miklos millip minimum mitochondria mitochondrial miya model molecular moret moritz mtdna mueller multi multiple nadeau naor nature newman nigroviridis nishida nonrandom notice novemb octob ohno oint oints optimization opulation order originated over overall oxford pages petit phylogenetic phylogenies phylogeny pick plethodontid possible press problem problems proc procedure prog proof proto providing publishers random rank ranking rearrangement rearrangements recomb reconstructing reconstruction references relvance result reveals reverals reversals rlid rounding running saccharomyces salamanders sankoff scale schieb section segments septemb sequences sets shamir simply sinauer since sivakumar songbirds sorting springer stangethomann stoc sudan suggest supported swenson syst systematics takes tang tech technical teleost terebratalia tetraodon thank that therefore this time total transversa trcs true tsukamoto under univ used value values verlag vertebrate volume warnow will with within work workshop yeast york
http://doi.acm.org/10.1145/1109557.1109614	56	All-Pairs Shortest Paths for Unweighted Undirected Graphs in o(mn) Time	again ahuja aingworth algorithm algorithmica algorithms allpairs almost alon among application approach apsp arcs arithmetic arlazarov assume automata average between both bound bounds bridging cases chan chekuri claim clearly clique closure comb complexity compression comput computation computer conf consequence constant construction contains contradiction coppersmith correctness cost cubic data decrease decrement degree details deterministic diameter digraphs dinic directed distance distances dobosiewicz dokl dynamic economical edge edges efficient elimination endix entirely estimation european every excluding exponent faradzev fast faster feder finding following follows found fredman from fully galil gaussian graph graphs hagerup halperin handle high ieee improved increment index induced induction indyk inform integer king kronrod languages least lect lemma length lengths lett letting levels like linear maintaining margalit math mathematik matrix mehlhorn more most motwani multiplication must notes notice numerische obtain omit only optimal orlin otherwise overall pages pair pairs paper parallel partitions pass passes path paths pettie pick planar plus positive priority probability problem proc process programming progressions proportional prove queues ramachandran real rectangular recursive recursively references running seidel separators sets shortest shoshan siam single size slightly small smallest some source soviet sparse special speeding spira springer starting statement stay step strassen stronger struct subcubic subgraph subpath surely symbolic sympos takaoka tarjan than that then theoret this thorup through time total transitive traverse ullman unchanged undirected unweighted upper using verlag version vertex vertices weighted weights where winograd with within without word workshop yannakakis yuster zwick
http://doi.acm.org/10.1145/1109557.1109576	18	Facility Location with Hierarchical Facility Costs	aardal algorithm algorithms analysis applications approx approximation arya back charikar chudak combinatorial comput computer computing correlated cost costs data design dialm discrete drezner dual european facility feigenbaum foundations garg gathering greedy guha hayrapetyan heuristic ieee improved information installation ipco jain jaraman joint khandekar khuller korupolu lagrangian levi local location mahdian median methods metric mobile multicast munagala network networks pages pandit papadimitriou plaxton pomc primal problem problems proc proceedings references relaxation rickenbach schema science search sensor service sharing shenker shmoys siam springer strikes survey sviridenko swamy symp symposium syst tardos theory transmissions uncapacitated uncapitated universal using vazirani wattenhofer with workshop zhang
http://doi.acm.org/10.1145/1109557.1109687	129	On k -Median Clustering in High Dimensions	about above adapt afford after agarwal algo algorithm algorithms also amortized analyze annu applications approximate approximating approximation arora arrive arrived arrives artif arya assoc assume author automata badoiu balls based bdoiu bentley better bounds bucket buckets callaghan capacity charikar claim clarkson clustering comments comput computation computations compute conceptually conf confidence constant constructed continue core coreset coresets correct data dealing decision decomposable dimensions discrete disjoint distance done dual dynamic dynamization each easy either empty enough euclidean euro every extent facility factor fail following follows found frahling full garg generalizations generated geom geometric gonzalez guha hand haussler have heuristic however ieee indyk insert insertions instead intel intercluster into invariant itself jain keep khandekar kmeans kmedian kolliopoulos kumar kushal lang large learning least less linear lineartime local location loglog mach made maintain manuscript maximum mazumdar means measures median merge merged metric mettu minimize mishra model most motwani move moved munagala nearly neural newly next note number oblinger observation observe optimal other otherwise over overall pages pandit panigrahy parameter peled pitt plaxton point points polylog positive prespecified primal probability problem problems proc process prog proof raghavan randomized reach recall received referees references related requirement resp respectively result sabharwal saxe scheme schemes search searching sequence sets shmoys shortly siam simple smaller sohler space specified spent stage standard static storage store streaming streams structure sublinear such suppose sympos tardos technique than thanks that their then theorem theoret theoretic theory therefore time total transformation trigger uncertainty until update useful varadara vazirani verify virtual want weight when whenever where will with
http://doi.acm.org/10.1145/1109557.1109641	83	A Semidefinite Programming Approach to Tensegrity Theory and Realizability of Graphs	abdo above absence adding alfakih algorithm algorithms algosensors alizadeh already also analysis anchor andrzej answering anthony applicable applications applied apply approach argued arise armed arnborg around article asano aspnes assign assigning associate associated assume assumed assumption attained axiomatique barvinok based bdoiu before believe benson berlin between biswas boyd bruce cambridge case chapman characterization characterizations charles check chen chet christoph chuan claim classe clearly collinear comb combinatorial combinatorics combine commun complexity component components comput computational computed conclusion concreteness conf configuration conformation conjecture connected connection connelly consider constructive continuation contradicts control convention convex corneil corr corresponding could crippen dability david decompose decompositions demaine dept derek derive design desired determine diestel dimensional dimensions disc disconnect discussion distance distances distanci dividing does doherty donald dual each edge edges edition either embeddability embedding embedwhich endix energy equilibrium erik espace establish established establishes estimation euclidean even everything exactly exploiting extra extracted fact facts farid feasible figure find finding findri finition first following follows forbidden formulated found frameworks free from function further geom geometry ghaoui give gives global goldenberg gordon graduate graph graphs hard have havel helmberg hence hendrickson henry here hilbert homeomorphic homeomorphism hopcroft horn householder however improved induced indyk infeasible infocom information interesting interior into introduced invent inverse ipsn isomorphic issue james ject jective jiaghayi john johnson jorge konrad kristofer labelled lance large laurent length lerton liang lieven like linear lncs localization loss maps maria math mathematics matouek matrices matrix maurice maximize means meth method methods michael mihai minors mohammad molecular molecule morphic most multidimensional multipliers mutual neil network networks notion null number obtain obtained only open optimal optimization origin other otherwise outlined paper partial pathological piotr pister point points ponents posed position pratik preprint presence present press previously primal problem problems proc proceed product programming programs proof proper properties propose proposition proskurowski psychometrika putting quadratic question ready realizability realizable realization realize realized realizing recognition reduce reduces references reinhard remarks removal remove repeat report research rest result resulting review richard rigidity rise robert robertson robin roger rose roth ruml sake satisfied saxe scale scaling schoenberg section semidefinite sensor sequence seymour shang shown siam simple since sloughter socg soda solve solving some sons space spaces span sparse springer stefan stephen steven stress strictly strongly structure strut studied subdivided subdivision subgraph such summarize suppose taghi taining takao tarjan techniques tend tensegrity terms texts that their then theor theorem theories theory there these this thomas those though three thus time timothy together trans tree trees trevor triconnected union university until unyielding using value values vandenberghe variant vectoriellement verlag vertex vertices volume wagner waterloo weighted well what wheeler when where which whiteley wiley will wireless with without wolkowicz would wrong xiong yang yinyu young zentrum zero zhang zhijun zuse
http://doi.acm.org/10.1145/1109557.1109633	75	Approximation Algorithms for Wavelet Transform Coding of Data Streams	able above abridged academic achieve acta adaptive after aggregates algorithms also anna annual approximate approximation arguments barbara based basis both bound bounded bounds callaghan cannot case chakrabarti chakrabati clearly clustering coherence combinatorial communication computation computer conference constant constraint construction correct corresponding cost data databases daubechies dependent deterministic devore dictionaries dimacs dimensionality efficiency equations error estimation euclidean exceed exists fact factors fast find finkelstein fixed focs following form foundations functions garofalakis gibbons gilbert graphics guarantee guess guha haar harb harder histogram histogramming histograms history icalp icdt image indexing indyk interesting introduces ioannidis item jacobs jeev jeffrey kaushik keogh kotidis koudas kumar kyuseok large lectures locally lower maintenance mallat march martin matias maximum mehrotra metric minimizing minos minz mishra model models most motwani much multidimensional multiresolution muthukrishnan need nonlinear nonuniform number numerica observe once optimal optimally over pages pass pazzani personal pods polynomially practice precision press probabilistic problem problems proc proceed proceedings processing properties ptas quantization quantizations query querying range rastogi ratio reasonable reduction redundant references remains representation resolving respecting respects right rule rules salesin santa science scott section selectivity series shim siam sigmod signal similar simply since smallspace smith soda solution solvable solve solved space sparse statistics stoc storing strauss stream streams such summary symposium synopses synopsis system term that their theorem theory this those thresholding time tods tour unclear urieli using verify vitter vldb wang wavelet waveletbased wavelets weighted where which while with workload write
http://doi.acm.org/10.1145/1109557.1109595	37	Extra Unit-Speed Machines are Almost as Powerful as Speedy Machines for Competitive Flow Time Scheduling	above accumulates after against algorithm algorithms also always amount analysis appendix approx approximating assume augmentation average avrahami awerbuch azar baker bansal basically becchetti below bender berman bounded broken busy calculated cally case cases cess chakrabarti chan change chekuri clairvoyance compare comparing competitive completed completes completion computer conclude consider considering constraint contains continuous coulston critical dark deadline decrease decreases define denote density details dhamdhere dispatching distinct does done during each editor edmonds emma endix equivalent even exactly extra faster first flow focs follows formed from future gehrke goel handbook have highest hypothesis immediate immediately implies improved including increasing incurred individually induction information integer interested interval into introduction ized jaraman jobs kalyanasundaram khanna kumar larger lemma length leonardi less leung lifts lower lsjf machine machines machinespeed machiq make marchetti mbers mccullough mean metrics mfcs migration migratory minimize minimizing models more most multi multiple multiprocessor multiprocessors muthukrishnan negative next ngan norm normalized normall normalspeed note notice number numbers observation obvious online only optimal optimally other otherwise outside owerful pages parallel performance perio periods phillips plus positive precisely press priority proc processor processors proof prove pruhs putting qand qincurred random real rearranging references regev release remaining removing resource respectively result rising running scaled schedule schedules scheduling science sequence sequences sequencing sequenr server sgall shaheen sharing show shown similarly since size smaller soda some spaa spaccamela special speed srpt ssimulating stein stems stoc streams stretch such swat swill terms than that then theoretical there these this thus tide ties time times torng total true unaffected unit units unweighted upper using utilizes values versus waiting waits weight weighted wein when where which wiley will with within without wong work york young
http://doi.acm.org/10.1145/1109557.1109585	27	On the Capacity of Information Networks	about achievable achieve achieving acknowledgments acyclic adler advantage agarwal aggarwal ahlswede ahuja algebraic algorithm algorithms alone alphabets also alternatives amin among annual applications applying approximate approximation aranayak authors babai beame benefits between boolean borgs both bound bounds calculations capacity case cell challenging channels characterization characterizing charikar chayes chou christian ciss classification code codes coding combinatorica combining commodity communication communications comparing completion complexity compression computation computational computer computes computing concerning conference conjecture connection consequences constructed construction control cornell cover currently dard david decision defined demand designing determine deterministic dimacs directed discrete discussions distributed dougherty dwork each edge editors efficient effros egner elements entropy eric error even example exists explaining false feige field figure finally fischer flow flows floyd focs focused following foundations freiling from function functions fundamental general generators gideon given goemans graph graphs hall hardness harvey have helpful idealized ieee impossible improving include inequalities infinite infocom information input instance instances insufficiency integrality international isit jaggi jain jennifer jiaghayi jiang joint journal july june karger kleinberg known koetter kramer kunal laci large lehman leighton lerton less level like linear logspace lovasz lower madhu magnanti mahdian manuscript many matrix maximum measures mehta memoryless michel mihai miller mincut minimum minsteiner mohammad montgomery most much multicast multicasting multicommodity multicut multiparty multiple murota neither network networks nisan nonshannon nothing number offs okamura open orlin others otherwise output over packing pages pairs paral past patra people perhaps permuting peter phil pippenger plenum polymatroidal polynomial possible prentice probe problem problems proceedings progressive protocols prove proved pseudorandom questions racke randomized rate rates raymond real recently recursively references related relations remain remains report reports results riis routing saberi saks salavatipour samorodnitsky sanders satisfy savari science sciences section separating sept september sessions setting settle seymour shannon siam societies soda solution some song sorting space spaces sparsest sparsity special steiner stoc storage stronger subject submitted such sudan symposium system systems szegedy talwar technical than thank that thatcher their theorem theorems theory there these thesis they this thomas throughput tighter time timespace tolhuizen trade tradeoff transactions tree trees trivial type undecidable undirected unicast unit university unknown upper using vazirani vector versus vijay vitter were whether which wide wiley with work workshop would yeung yields yuval zeger zero zhang zosin
http://doi.acm.org/10.1145/1109557.1109654	96	Quantum Verification of Matrix Products	above acknowledgments actual additional adversary again algorithm algorithms also always ambainis among amplification amplitude analysis anonymous another application applying arguments arithmetic assume assumption based beals because better binary boolean both bottom bound bounded bounding bounds boyer brassard buhrman cambridge cancel cannot case cases cauchy certificate chain chance chooses chuang claim claimed classical clearly cleve close coin column combinatorial comments commutativity completes complexity computation computed computer conclude condition conditioned consider constant constants contains contemporary coordinates coppersmith csli database decompose definition denote depending descends described detecting direct discrete discussions disjoint distinctness domain done ducts durr earlier easy element elements elimination emarked empty ensure entries entry equal equality equation equivalent error estimation evaluate event every exactly exchange exist exit expected exponential factor fast figure find finding finds finishes first fixed focs following follows formally fortschritte found foundations four fraction freivalds from furthermore gaussian good gorithm group grover half have having heiligman hence high higher holds however icalp ieee ification indeed independent indyk inequality information initialize input inputs instead integral interval into iterated iteration iterations journal just karpinski klauck known knuth kurur larger largest least lecture left lemma length level levels line lncs loop lower lows magniez manuscript marked markov math mathematics mathematik matrices matrix measuring mechanical method methods might millennium mosca most multiplication multiply nayak necessary nielsen nonempty nonzero notes nown number numerische obtain obtained ones only optimal order other otherwise output pages pairs papers parallel physcomp physik pick picked plug poly polynomial polynomially polynomials position present press probabilistic probability problem proc product progressions proof provable prove proved quadrant quadrants quantum random rearrange recognized recompute rectangular recursion referees references register remark repeat repeated rest result return returning returns revealing revisited right ronald rows running same santha satisfied scalar schwarz science sciences search searches searching section selected sensitive separately series sets several show siam sided since size smal small soda solution solutions some space spalek sparse speed spent springer standard stanford step stoc stop strassen strong submatrix subset subsets successful such summation symbolic symp system szegedy takes tapp term testing than thank that their them then theorem theorems theoretical there these this threads three thus tight time times together total tradeoffs triangle troy true uniformly unique university unpublished upper useful using valiant valuable value variables vazirani verification verify verlag version volume walk what when where which winograd with without wolf worst would wrong yuster zwick
http://doi.acm.org/10.1145/1109557.1109560	2	Measure and Conquer: A Simple O(20.288 n ) Independent Set Algorithm	acta adjacent after algorithm algorithms altogether amortized analysis annual appendix applications approximate assume automata backtracking based become beigel between bordeaux bound bounds branch branching byskov case cases challenge chen claimed clique colloquium coloring colouring combinatorial completeness component computation computer computers computing connected conquer consequences consider considering constant constraint constraints contained cornell cover dantsin decreases degree degrees dept deterministic deterministically discarded discrete domination edge edges empty enumerating eppstein eureka even exact exactly extra fact fill finding first focs fold folded folding following fomin foundations four freemann from further garey general generality given goerdt grandoni graph graphs guide happen happens hard hastad have hence hirsch icalp ieee implications implies imposing improved improvement improvements incident independent instances interesting international intractability isaac ithaca iwama jian johnson journal kanj kannan kleinberg kratsch labeled labri languages large least leaves letters lncs local loss lower math maximal maximum measure minimum mirrors most must negative neighbor neighbors nodes observations obtain obtains operations optimal optimization other otherwise papadimitriou possible possibly probabilistic problem problems proceedings programming proof property quasiconvex raghavan recurrences reduction references refine refined remaining remains removing replace report research robson room running satisfaction schoning science search second sets shrink siam simple size small soda solving sparse springer study such suppose surely survey symposium taken tamaki tarjan technical that them theorem theoretical theory there this three thus time times todinca total transactions trees treewidth trivially trojanowski univ universite upper vertex which while will williams with within without woeginger would
http://doi.acm.org/10.1145/1109557.1109617	59	Four Point Conditions and Exponential Neighborhoods for Symmetric TSP	academic ahuja akad algorithm algorithmic algorithms amer among analysis annals applied aspects assignment aurenhammer automation avtomatika backs balas bssr burkard canadian case cases chapter chichester circuits class classes company computers computing congram control convex cybernetics deineko demidenko discr discrete domination dynamic dynasearch edgeconvex empirical engineering english ergun even exponential extreme figure fragments francisco freeman from gabovich games garey gilmore golden gutin hamiltonian heuristics information informs interdisciplinary intractability iterated johnson journal jump kabadi kalmanson kibernetika kluwer large lawler lenstra letters line linear lines ling list lsolved machine math mathematical mathematics mathematyki matrices matrix maximum michalski monge nauk neighborhood neighborhoods okamoto orlin polynomial possible potts problem problems proc processing programming property publishers punnen pyramidal quadratic quintas recursions references relationship relaxed remote representation resolution restricted review rinnooy rubinshtein russian salesman scale scheduling schematic sciences search sequences shmoys siam simonetti single solvable some sorting special sssr steiner stewart study supnick survey symmetric tardiness techn techniques telemekhanika time total tours translated translation travel traveling twisted types variations veen velde very volodarskiy weighted wiley with woeginger zacharin zastosowania zverovich
http://doi.acm.org/10.1145/1109557.1109607	49	Superiority and Complexity of the Spaced Seeds	acid acids algorithm aligning alignment alignments altschul amer amino analysis analytic annual appear appeared appl applicable application applications applied approach balakrishnan basic berlin berman bioengineering bioinf bioinformatics biol biology biotechnology birkhoff blast blastz brejova brown buhler cambridge center choi closest coding combin combinatorial combinatorics common comp comparative complete completeness comput computer concerning conf conjecture consortium database designi designing discrete early edition editor effective efficient estimating event extension fast faster feller final first freeman games gapped garey genbank general generating generation genome genomic germany good gotea greedy growth guibas guide hardness hartmanis highly homogeneous homologous homology human identification identifying identity ieee information initial introduction jacquet jentzsch john johnson jolet journal keich kisman koutras kucherov lecture lipman lncs local lothaire mahaney makalowski mastering matching math matrices method methods miller minc molecular more motif mouse multiple national nature needleman nicod nicolas nonnegative nontransitive notes nucleic nucleotide occurences odlyzko optimal optimizing overlaps overview pattern patternhunter patternhunterii pearson ponty practical preparata press probab probabilistic probability problem problems proc programs properties protein proteins quick rapid rare recomb references regions reinert rivals runs salvy satistics scans schbath schwartz science sciences search searches seed seeds selection sensitive sensitivity sequence sequences sequencing series sets similarities similarity simultaneous single size smith solov soluton sons spaced sparse statistical string subsequences substring symp symposium system szpankowski taiwan theorem theory tool trans tromp veeramachaneni version vina wagner wang waterman wiley with words wunsch yang york zeng zhang
http://doi.acm.org/10.1145/1109557.1109597	39	Distributed Selfish Load Balancing	access algorithms allo allocation allows also analyzed annual approx approximate approximation architectures aspects assigned assignment automata available balanced balancing bound bounds british canada case cation chain change chernov choices chooses colloquium columbia complexity computer computing conclusions concurrent convergence cornell cost crete czumaj discrete disks distributed does dynamic egner eindhoven equilibria equilibrium even expected exponential fact farms fast figure first flow following follows fotakis francisco from function game germany given goldberg greece guided hagerup handbook have http icalp information international john journal kesselman kluwer kontogiannis korst koutsoupias krysta languages lattice least letters load local lower luby malaga mansour many markov matches mavronicolas mexico mint mitzenmacher model montreal moves multiplayer nash netherlands neutral newfoundland observation page papadimitriou papers parallel pardalos perfectly philadelphia planar podc power price princeton principles probability proc process processes processing programming protocol proved proves puerto rajasekaran randall random randomization randomized rate recovery references related rerouting resource resources results richa riley rolim roughgarden round rounds routing rvat sanders scheideler science search second selfish server shown siam sigact sigops simple sinclair sitaraman slow soda spaa spain spirakis stacs state stoc strongly structure structures studying summaries survey symposium tardos tasks techniques that then theorem theoretical theory therefore this tight time timr tour traffic trans trier until upper vallarta vancouver very vocking which with workshop worst
http://doi.acm.org/10.1145/1109557.1109584	26	Overhang	addison ainley algorithms amer amerik archim archimedeans balanced bridge city coffin concrete decreasing discrete drive eureka finely function gazette graham hearnshaw hence html http jenga johnson journal knuth leaning lems line lire longman math mathematical mathematics monthly patashnik paterson phys posium prob problem problems proceedings publishing references siam since society soda solutions symk therefore tower univ wesley york zwick
http://doi.acm.org/10.1145/1109557.1109669	111	Improved lower bounds for embeddings into L1	above acid acknowledgments algorithm algorithmic algorithms also amer amino analogue analysis andoni annual anonymous another applicable applications approxa approximate approximating approximation arora assaf assumption aumann author average based batu because berkeley berlin between binary biology boolean bound bourgain capable cast challenge chawla claim codes collection combinatorica comments completes complexity comput computational computer computing conference conjecture containing contradicts coordinates correcting cuts cyclic deletions designing details determine deza discrete discussion discussions distance distortion distributions dokl donnell ectrum eddability edding eddings edit efficiently elchanan embedding equivai ergun erty euclidean every exact exists expander finally finite first flow flows following follows foundations fourier fraction friedgut from functions furthermore games general generalized generally geometric geometry give graph graphs group gupta hamming hardness hilb however ieee imations imply improved indyk inequality influence influences insertions integrality interesting into intriguing invariance israel james jayram journal june kahn kalai khot kilian krauthgamer kumar large laurent least left leighton lemma lently letting levenshtein like linial lipschitz london lower magen many math method metric metrics molecular monotone mossel moves multicommodity multicut naor nearest needleman negative neighbor nikova noise nonemb normed note notice obtain obvious oleszkiewicz omitted oolean open operations optimality ordinates ostrovsky other ounds ower pages participants partitionings partly physics poincar pointed problems proc proceedings proof prop proteins prover question rabani rabinovich raskhod raskhodnikova reading references related remark research results reversals reviewers round rubinfeld same sami science search section sensitivity sequence several sharp shift siam similarities sivakumar some soviet space spaces sparsest spring springer squared stability still stimulating strings sublinear such symposium technically than thank that their theorem theorems theory there this threshold tight total true ulam unique upper useful variables vazirani verlag version vishnoi weaker weakly weight which while wishes with wunsch yossef
http://doi.acm.org/10.1145/1109557.1109666	108	The Price of Being Near-Sighted	about achievable achieves algorithm algorithms alon anarchy applications approach approximating approximation approximations babai bartal been between bound bounds byers cannot caused characterize combinatorica commodities communication computation computational computed computer computing conclusions connected constant constructing construction context control corollary cover covering decompositions degradation diameter discrete distributed dominating dual dubhashi each efficient elkin environment every everyl fast fich fleischer flow focs following foundations fractional from future global globally graph graphs hold hundreds impossibility independent individual individuals information integer interesting israeli itai jagopalan jaraman journal knowledge kuhn least letters light limited linear linial local locality locally lower luby matching matchings math mathematics matrix maximal measure minimum mixed models more moscibroda multicommodity naor neighborhood nisan number obtain online operations optimal optimization order packing pages pairs panconesi papadimitriou paper parallel peleg plotkin podc polylogarithmic positive pproximation presented price primal principles problem problems proc processing program programming programs proposed quality radhakrishnan randomized ratio ratios recently references remark requires research resources respectively restricted resulting results roughgarden rounding rounds routing ruppert saks same science section selfish sensitive sequential sets setting sheds shmoys siam similar simple size skeletons small soda solution solving spanning specifically spirit srinivasan stoc stockmeyer suboptimality such suel symp symposium tardos that theorem theory there therefore this tight time timeapproximation trade tradeoffs tree unconditional upper using vazirani view wattenhofer weakly what wider with without yannakakis young
http://doi.acm.org/10.1145/1109557.1109590	32	Constraint Solving via Fractional Edge Covers	acyclic acyclicity adler algorithm algorithms alon always annual another answer answering appear applications approximate approximates approximating army artificial bailey bases berge beyond bounded bulatov called cambridge cases characterization characterizations chen chung class closest closure clustering coding cohen color combinatorial combinatorics comparison complexity computational computer computing concepts conclusions conference conjunctive connectivity conservative considered constraint constraints constructs containment copies corresponding cover dalmau data database datalog dean dechter decomposition decompositions definition degrees design determines dichotomy distances edge editor element european evaluation fagin families feder finite foundations fractional frank freuder friedgut from game general given gottlob graham graph graphs grohe group guards gyssens have having help hentenryck holland homomorphism hypergraph hypergraphs hypertree identified ieee important instance instances intelligence international intersection invariants israel jeavons joint journal kahn kaufmann kolaitis krokhin laid languages large lecture leone logic logical logics make marshals marx mathematics maximal measure methods might minmax monadic monotone morgan most much musliu national networks north note notes number open ordered other pages paper parameterized pearl polynomial polynomialtime possible practice press previously principles problem problems proceedings processing programming properties property prove provided queries query question raised reed references related relational remains result robber robbers samer satisfaction satisfiability scarcello schaefer schemes schwentick science sciences searching seen segoufin series sets seymour shearer siam side similarly sixteenth small smaller solvable some spread springer structural structure structured study substring such suggests surveys symposium system systems tangles that then theorem theorems theoretic theory there this thomas three through time together tractability tractable tree treewidth turns unbounded unified university using vardi variable verlag very volume when whether which width with without workshop yannakakis yuster zwick
http://doi.acm.org/10.1145/1109557.1109637	79	Streaming and Sublinear Approximation of Entropy and Information Distances	abstract adam alejandro algorithm algorithms allerton alon also amari andrew annual another applications approach approximate approximating approximation available axiomatic babcock babu balachander band banerjee batu berkeley bernard bialek bottleneck bounds bregman brian california cencov charikar chazelle checking chen class classification close clustering coefficients colloquium communication complexity comput computational computations computer computing conference control convex cormode corr count counting cover csiszar dana dasgupta data databases datar decision demaine dhillon difference differential discrete discrimination distances distinct distribution distributions divergence divergences divisive dynamic eccc electronic elements entropy erik estimation extended facility farachcolton fast feature feigenbaum finding flemming focs fortnow frequency frequent from general geometric geometrical ghosh gilbert graham guha handbook harsha histogram hring icalp ieee improved indyk inequalities inference information informationtheoretic international internet inverse issues items jayram jeev jennifer jmlr joan john kannan kearns kevin kotadis krishnamurthy kumar lance latin learnability least lecture leipzig lens liese limited linda linear location lower luca madhyastha mahesh maintanance mallela mansour martin massive math mathematik matias maximum mayur mcgregor measurements measures meets merugu method methods meyerson michael minimum models moments monographs moses motwani munro muthu muthukrishnan netdb networking notes online optimal ortiz over packet paterson patrick pereira piotr pods problems proc proceedings property providence raman random randomization ravi references related request research robert rolf ronitt royal rubinfeld rules sampath sampling sanjoy schapire science selection sellie series shivnath siam silvey sivakumar sketch smal smith society soda some sons sorting space spanning spot springer squares stationarity statist statistical statistics stoc storage strauss stream streaming streams sublinear sudipto summary suresh survey syst systems szegedy telecommunications testing teubner text texte that theor theoretic theoretical theory thesis thomas through time tishby tops transactions transl tree trevisan tugkan tutorial university venkatasubramanian verlag viswanathan warren weight white widom wiley with workshop yishay york yossef
http://doi.acm.org/10.1145/1109557.1109628	70	Improved Lower and Upper Bounds for Universal TSP in Planar Metrics	above academic acknowledgments adaptivity algorithms alon along already among amortized analysis annual appear approach approximate approximating approximation approximations arbitrary architectures area argument arora assume assumptions automata azar bartal bartholdi because been before belong benefit benefits berlin bertsimas best between black block boosted borodin both bound boundary brebner building calif call cambridge carter case cases centered changes check checkerboard choose chosen christofides circuits classes cohen colloquium color colored coloring column combinatorial combinatorica combining comm communication competitive complement completely completes complexity comput computation computational computer computers computing conclusion conclusions confirmed congestion conjecturally conjectured conquer consequence consists constant construction contained containing contains contexts contiguous continues convex corner corners corresponding costs cover covers current curve curves dean decomposition defines deleting demands denote derived diagonal diameter directed directions discrete discussions disjoint distance distances distinct distortion divide divideand divided does done each earlier easier edge efficiency eight eighth either embeddings endpoints enlarge enlarging entire equal euclidean even every examples excluded exercise exists factors fewer fiat fifteenth fifth first flow focs followed following follows forbidden foundations fractional francisco free freeman from fruitful functions garey general generality geometric geometry global goemans graph graphs grid grids grigni guide guided guil guolong gupta hajiaghayi halfspace halfspaces halfway handled harrelson hash have hence henceforth here heuristic hildrum hold holds icalp ieee immorlica implies imply improved incomplete increases indices inside instance international intersec intersect intersecting intersection intersects interval intervals into intractability jaraman jmohan john johnson joining journal kaplan karger klein kleinberg kmst knapsack know known koutsoupias languages later lawler least lecture lectures ledge left leighton lemma length lenstra lett line linear lines ling list loss lotine lower math matousek measure metrices metrics middle minimize minimizing minkoff minor minors mirrokni mitchell monochromatic monochromatically monotonic monotonicity more most multicommodity must naor network networks nine ninth nodecapacitated note noted notes noubir npcompleteness number numbers oblivious obtain obtained online oper optimal optimization ordering other otherwise packing paging papadimitriou paral parallel pattern perhaps philadelphia planar plane platzman plotkin points polygonal polynomial polynomialtime possible preserving press problem problems proceedings procrastination programming proof properties property prove quadrilateral quadrilaterals quite racke rajaraman random ratio ravi reader recent rectangle rectangular references related remaining respectively rest results richa right routing rows rules salesman same sampling satisfied satisfies satisfying scheme schemes schieber science secaucus second segment segments seventh seymour shmoys siam similar similarly simple since sinha sleator smal society soda some sons spaa spacefil spreading springer square squares statement steiner still stoc stochastic strip strips subdivisions subinterval subintervals such sundaram suppose symposium system tarjan techniques than thank that then theory there these they third thirteenth thirtieth thirty thirtysixth this three tight time tion together tour travel traveling tree trees trivial twenty union unit universal university update upper used useful using valiant various verlag versa vertices vice volume vondrak washington wegman weighted what when where which white whose width wiley will with within without woeginger woloszyn worst yaniv yannakakis york
http://doi.acm.org/10.1145/1109557.1109563	5	Local versus Global Properties of Metric Spaces	above additive algorithm algorithmic algorithms also althoefer american annals appear appeared applications approximate approximating approximation arbitrary arora asymptotic attention august aumann back banach bartal belongs berkeley bollobas bound bounded bounds bring california call carolinae chawla check chekuri clearly colton combinatorica comment communication complexity computational computer computing conference consider construct construction continue convenient converges corresponding cube cuts define defined denote desired deza dimacs dimensional discrete discussion dist distortion dobkin dominates dominating each easy embedding embeddings employ equipped equivalent euclidean every exists expander fakcharoenphol farach finally finite first flow flows following follows foundations fully games gaps generating geometric geometry given grality graph graphs gupta hardness have hence holds ieee implies improved incurred indeed infinite infinitum instead intea integer into invariant james january johnson joseph journal june just khot knowing krauthgamer kumar latter laurent lemma like limit limr linear linial lipschitz london lower maehara manner manuscript mappings math mathematic mathematical mathematics matousek mendel metric metrics milman monotone more moreover multicut naor natural nearly newman next nonincreasing norm observation observe obtain only optimal order outerplanar pages particular partitionings phenomena point pointwise power preliminary previous princeton private proc procedure program properties prove prover proving rabani rabinovich ramsey realm references required respect respectively restrict round same scalability scalable schechtman science second sequence shall shifted siam similar simpler since sinclair sivakumar soares society some spaces spanners sparse sparsest speak speaking springer springerverlag square standard statement stoc stretch subsequence such supremum symmetry symp taking talwar than that theorem theory therefore thesis this tight transactions transform translation translationinvariance tree trees type ultrametric uniformly unique univ university value vazirani vectors verlag version weighted what which will with without workshop
http://doi.acm.org/10.1145/1109557.1109658	100	New Lower Bounds for Oblivious Routing in Undirected Graphs	according acmsiam admission adversarial algorithm algorithms allor along also among another appendix approach approximization architectures assign assume balancing bandwidth between bipartite bound bounds broder call capacitated capacities cardinality case centralized class classes client column columns combinatorica communication comparably complete computer computing concurrente congestion consider constant constitutes constructed constructing construction contains control correspondence corresponding decomposition define defined definition demand demands denote desirable directed discrete disjoint distributed distribution dmax dropping each edge edges effective elements ence endpoints equal every exceeding exist existence exists expander expanders exploiting factor feasible finally finding flow focs formally formulate foundations fraction frieze from further general given global graph graphs grid have hence ieee implies improve indeed information instructive interesting international intersects into joining journal known least left less limited load locality lower lubotzkyphillips main matchings matrices matrix maximum mincut minimize minimizing minimum more most multicommodity namely network networks node note nothing notion oblivious ombining online only open optimal optimization ordering otherwise packets parallel parallelism partial partition partitioned paths perfect pieces polynomial possible practical preconditioners problem problems proceedings proof proved proven question quite ramanujan random randomization ratio received rectangular references result right route routes routing sarnak satisfies scheme schemes science section selectively send sent server sets shared short showing shows siam since size soda solved source sources spaa sparsest specifying standpoint still stoc stricter strong stronger such support suppose survey symposium target targets techniques than that then theorem theory there therefore this throughput thus tight time tree under understand undirected units universal upfal upper vertex walks whether which while whose with without work workshop would
http://doi.acm.org/10.1145/1109557.1109670	112	2 Spreading Metrics For Vertex Ordering Problems 2 (Extended Abstract)	agarwal agrawal algorithmica algorithms andconquer another application applications approach approximate approximated approximates approximating approximation area argument arora arrangement assuming attention available best bhatt cambridge case challenging circuits combinatorica commodity completion complexity computable computer computing cone construct could dealing deletion designing directed direction distance distribution divide domination dual efficient embedding embeddings even exchange expander extending fact factor fast feedback feige finally find flow flows focs following fractionally framework full geometric given goes good graph graphs hansen have http icalp important improve improved information instance integrality interesting interval into investigate issues jacm journal klein known layout layouts lead leighton leiserson letters line linear lipton makarychev manuscript maximum means metric metrics minimum multi multicuts naor networks note open optimal ordered ordering other packing pairs pandu parallel partitioning permutation planar plane press primal princeton probability problem problems proc processing processor produce ramalingam rangan ratio ravi received recently references relaxations remains replace richa same scales scheduling schieber sciences separator sets seymour shuffle siam single soda solution solve solving some spreading stoc such sudan symmetric system tarjan techniques that their then theorem theorems there therem these this through tree twice uncut undirected unified unordered used using value variant variety vazirani version vlsi weights whether which with would
http://doi.acm.org/10.1145/1109557.1109620	62	Reducing Tile Complexity for Self-Assembly Through Temperature Programming	acmsiam adleman aggarwal algorithms analysis annual applications applied assembled assembly august based biochemistry biomolecular chem cheng complexes complexities complexity computation computers computing construction crossover crystals design dimacs dimensional discrete double edition espanes experiments fifteenth generalized goel goldwasser huang industrial international introduction journal june komogorov kopatsch labean lagoudakis ligation local mathematics meeting models molecules nature pages parallel pattern proceedings program proving recognition references reif rothemund running satisfiability schweller second seeman self selfassembly siam size society some springer squares symposium system technical theorems theory time triple universal verlag vitanyi wang wenzler winfree workshop yang york
http://doi.acm.org/10.1145/1109557.1109571	13	A deterministic subexponential algorithm for solving parity games	abstract again aided alfaro algorithm algorithmica algorithms american analysed annals applications applied argue argument aspects automata aviv because between binary bjorklund bound bounded calculus ceed chatterjee checking child children clarke coloured complexity computation computer computing concluding condon conference consider current deciding decrease decreases define degree descriptive determinacy determined deterministic dimacs discrete does domized down dralek each east easy editors emerson every exceeding extend extended fast finite finitely first focs follows fossacs foundations fragments from function game games general gives graphs grumberg guide halman have hence henzinger ieee immerman improvement incurred infinite information international journal jumdar jurdzinski jutla kalai king kolaitis kupferman label labelled labels leaf least left lemma length letters lexicographic linear lncs logic logics long ludwig mathematical mathematics matouek mcnaughton mean measures model models moning more most need next note novemb numben number observe obtained obvious omega onential only otherwise ound ounded pages parity paterson path pathdown payoff peled played positions positive press problem problems processing programming progress proof prove pure quantitative randomized rannumber recurrence references regular relation relations remarks research right rklund root running sandberg satisfies science sciences seem series sharir show siam similar similarly simple simplex sistla small smaller society soda software solution solving springer stacs starting stoc stochastic strategy structures subexponential such symposium system technical than that their then theorem theorems theoretical theory there therefore thesis thomas tighter time tree trees type uniquely university upper vardi verification visins visited visiting volume vorobyov welzl when where which whose width wilke winner with word zielonka zwick
http://doi.acm.org/10.1145/1109557.1109561	3	A polynomial algorithm to find an independent set of maximum weight in a fork-free graph	acad academy addison akadmiai alekseev algorithm algorithme algorithms amsterdam applied berge bound brandstadt budapest bull canadian cardinalit carolinae chair chapter classes claw cliques coloring combinatorial combinatorics comment complement corneil dans decomposition discrete edmonds efficiency efficient extensions farber finding flowers fork four free graph graphe graphs harary hoang holland house hujter hungarian independent information japan kiad largest lerchs letters lovasz matching math mathematics maximal maximum mcconnell minimal minty modular nakamura networks north note number oper optimization orientation path plummer poljak polyhedra polyhedron polynomial prime problem proc processing publishing reading recherche reducible references revision revisited ridder robust sans sassano sbihi schrijver sciences sect series sets simone spinrad springer stability stable standards stewartburlingham structure tamura theorems theory toile transitive trees tuza univ upper vanherpe vertex vertices weight wesley with xxvii
http://doi.acm.org/10.1145/1109557.1109661	103	On the Competitive Ratio of Evaluating Priced Functions (Extended Abstract)	abstract affects algorithm algorithms always american analogous annual appear application argument aspects assignment associated assume attribute baltimore before below better books boolean business called calling carmo case charikar check cicalese comparison competitive completes computation computer computing conjunctive consequence consider constitutes construct constructed contain contains costs database databases define determining deterministic dictionary discrete does dynamic each easily editor european evaluating evasive even every exists extended fagin feasible fepi finally find finding finds following follows forced forthcoming foundations fourteenth function functions game give given gupta guruswami hand have hence ieee impact implementation indirect informatics information input instance international internet isaac jcss journal kannan kaplan khanna kleinberg known kohayakawa kumar kushilevitz laber latin leads leaf learning lecture linpr lower maheshwari mansour markets maxterm minterm model monotone monotonicity most note notes numbers observation ones only optimal oracle other ound pages policy polynomial positive possible present press price priced pricing principles procedure proceedings proof properties public query querying quorum raghavan randomized ratio reals references remaining represented research restriction return sahai science sciences selection services show siam since situation smid soda solution sorting speed spend springer stacs stahl straightforward strategies strategy structured such symposium system systems that then theorem theoretical theory there this thix thus time times tree trees ultra uncertainty uniform value variable variables vector verify volume where whether which while whinston with witness worst
http://doi.acm.org/10.1145/1109557.1109674	116	Single-Value Combinatorial Auctions and Implementation in Undominated Strategies	aaai academic according acknowledgments agents akcoglu alem algorithm algorithmic algorithms also among applied approximate approximately approximation archer auctions awerbuch azar babaioff bartal behavior belong blumrosen both briest bundle bundles callaghan chaitanya characterization choice claim clarke combinatorial comments communication comp compatible complexity computational computer conclude contain cost countersp covering cramton daniel dasgupta decision design disjoint domains each econometrica economic economics eculation edge edith editors efficient elkind enter ersonationbased etitive exists finance first focs follows from games gonen goods grateful groves guruswami hardness hartline have help helpful highest holds icalp implementation incentive incentives intersect invaluable iterative jackson jaraman jason journal khanna kluwer kontoghiorghes krysta lavi least lehmann lemma liad linear look loser making many mapped mapping maximal mechanism mechanisms methods meyerson most multi multipart near nisan noam online optimal optimization ortunity ounded ower packing pages parameter parkes paths pavlov player players press pricing problems programming proof property public receive received receives reducing references related remains restricted results revelation review ronen rustem sciences sealed second shepherd shoham show silent simply since single siokos size steinb stoc strategies studies such swamy system tardos tark teams techniques telling tenders thank that there therefore these this thus towards truth truthful undominated unit utilitarian value vickrey vocking were with working yannakakis
http://doi.acm.org/10.1145/1109557.1109625	67	Approximating the k -Multicut Problem	acknowledgements acmlemma addressed algorithm algorithmica algorithms allows alon also although analysis ancestor appear application applications approach approximate approximation approximations aravind architectures argument asaf assigned assume assumption augmentating augmentation automata awerbuch azar baruch best binder bound bruce buchmulticuts called canadian capacitated case chandra chekuri chris claim claimed clearly clifford cmax combinatorial comments commodity common communication complete comput computer computing conclusions conges congestion connected conquer consider consists constant constrained constraints construct constructed cost costs covering create crossing danny date david decomposition decompositions define degreebounded delbert demand denote designing discrete discussions distinct divide dorit dual dummy each edge efficient either else epsilon essentially every example examples existence exists experimental expression extend facility factor feasibility feasible first flow following follows ford former foundations frederickson from fulkerson gandhi gaps garg general generate george given goemans graph graphs gree greg guarantees half harald hard harrelson hassin have hence henceforth here hierarchical highest hildrum hochbaum ieee improved include instance instances instant integer integral integrality interesting international intricate issue jain jochen joseph journal kamal khuller kirsten known kolliopoulos lagrange languages larger last laurence least leighton lemma lester levin like linear location logarithmic loquium loses made marcelo mathematics matrices matter maxflow maximal median metric michel mihalis minimize minimizing minimum more most multi multicommodity multicut multicuts multiplier mydlarz naor naveen necessary nemann nemhauser network noga noncrossing none notions numbe obtain online only optimal optimization optimum optlp other page pages pair pairs paper paral partial particular path personal poly polynomial primal problem problems proc program programming proof proving pruned racke ravi real recall recognition reduce reduction refael references relax relaxation rooted rounding same samir satisfied satisfy satish saving scandinavian scheme science section seen seffi segev selected separate separated separates separating several shepherd shmoys show showed showing shows siam similar simulate since single small solution solutions some source spanning srinivasan stavros stein subtrees such suffices suppose symposium take target than thank that their then theorem theorems theory there this three through thus tight time tion total totally tree trees true ularity undirected unimod unimodular unimodularity unsplittable used useful using value vazirani vijay well where which will with wolsey works workshop would yannakakis yossi
http://doi.acm.org/10.1145/1109557.1109588	30	Cake Cutting Really is Not a Piece of Cake	accumulates achieving after algorithms allows almost annual applied approximate approximating approximation area aspects because bound bounds brams busch cake cakecutting cambridge change combinatorial comments complexity comput computer conquer constant contradiction cuts cutting discrete dispute divide division doing duces each econometrica error european even exact expected fails fair fairly fairness fewer final find finding finish from game gives hence however inequality intro involves ismail ives journal krishnamoorthy krumke leaf least lecture lemma levels limited linear lipmann lncs lower magdon makes markov mathematics most multiplicatively note notes number only open outstanding paepe path peters piece pieces plugging poensgen press probability problem proc proceedings proof proto protocol proves queries question rambau recursion references replaced required requires resolution returns rich robertson same scheme science series setting sgall siam soda some springer stacs steinhaus step stougie symp symposium taylor term than that then theoretical theory therefore this tight tightness time triangle university value verlag webb with woeginger
http://doi.acm.org/10.1145/1109557.1109627	69	8/7-Approximation Algorithm for (1,2)-TSP	algorithm among analysis approximability approximation arcs arora asymmetric because berman blacks bounded carnegie case christofides cknowledgments combinatorial computing covers cycle cycles dense direct discussions distances each edge edges ends engebretsen euclid euclidean extensions fernandez focs from geometric good gsia hamming hannenhalli hardness hardvigsen have heuristic hits icalp ieee improved improvement information inserting jcss johan journal karp karpinski lars letters ling lncs matching math meets mellon merge merges metrics miller other papadimitriou paper path plenum polynomial problem problems proc processing proximation reducibility references related removing resulting reversals salesman schemes seifert shankar short sorting springer stad stimulating stoc such technical thank thatcher theory thesis they this thus time topic total travel traveling trevisan university using vega version vishwanathan when white with without worst yannakakis york
http://doi.acm.org/10.1145/1109557.1109562	4	The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity	able acta adding aggarwal algebraic algorithm algorithmica algorithms allows alok alphabet alphabetic alsways amir amotz analysis annual applications applied apply arborescence architectures arrays atallah baruch bettina between binary borchers brought burkard calculating case coding complexity compression computer computing concave concavity conditions conference constructing convexity could data demand depend derived deriving difference discrete donald dynamic efficient encodings entropy even extended extending fact first form formerly foundations frances frank galil generalized geometric gilbert given gupta height holds hwang index inequalities inequality informatica information inside integer james journal klawe klinz knuth kosara kunsoo ladner larmore lattices lawrence least left lemma length letters maria mathematics matrix maximal media merging methods miller monge monotone monotonicity moore moran multidimensional note notes online optimal optimization optimum pages paper paral parallel park particular partitioning permitted perspectives perstep peter point points prediction problem problems proceedings processing programming properties property prosenjit quadrangle quence quite rainer rectilinear recurrence references restricted result results revisited richard right robert rsma rudiger rudolf russell sadayappan said sailesh satisfies satisfy schieber science search searching secondary shlomo shor show showed siam slide solved sparsity speed speedup splitting steiner still straightforward stream structure subse sufficed symposium system technical teng that then theoretical theory they this though thus time trees twelfth upon using variable versions weight were wessner when where wilber with work worst yields
http://doi.acm.org/10.1145/1109557.1109610	52	Finding Large Sticks and Potatoes in Polygons	accelerated acknowledgements advances agarwal aggarwal algorithm algorithmica algorithms although amenta american ames among annu appl application applications arithmetic aronov automata aviation axis barber bern bernardini binational bischoff boyce brunet cell center certain chang chapter chazelle chew chin chrysanthou clearance cohen combinatorial commun comput computational computer computing conf conservative contained containment contemporary control convex coppersmith could cover crust culling curve curves data decomposition dedicata depano dimension dimensions directional discrete discretized dobkin drysdale editors efficient ellipsoid envelopes eppstein equilateral erickson eurographics even exponential extremal fast finding fortune forum found foundation four frankel from fyap general generalize generalized geom geometric geometry goodman grant grants graphical graphics guibas help hershberger high higher hoops huhdanpaa hulls ieee image inner inscribed inside intermediate internat international israel karol katz kedem klawe klosowski kobbelt koltun kumar lang largest lecture lerton leven linear linearization location lynn mathematical mathematics matrix matrixsearching maximizing medial melissaratos method metron minimizing mitchell models moran motion multiplication nasa national navazo notes obstacles occluders occlusion optimal optimization pages parametric partially path paths peel peeling placement planar point pollack polygon polygonal polygons polynomial potato practical problem problems proc proceedings processing program progressions queries quickhull randomized range reconstruction references regions relatives rendering representation rossignac rourke running sampled sana saonavzquez science sciences searching seems shapes sharir shor shortest siam simple sityon skeleton slow smooth snoeyink snyder society software solution solve some souvaine springer squares step supported symbolic sympos symposium syst tarjan techniques that theory this time toledo transactions translation transmission triangles triangulated triangulating verlag virtual visibility visualization volume wang well wilber william winograd with workshop would yehudi
http://doi.acm.org/10.1145/1109557.1109690	132	Efficient Algorithms for Substring Near Neighbor Problem	algorithm algorithms alphabets american amir andoni annual approximate arrays arya based bases bender bioinformatics biology biosequence block blocks bound buhler cambridge cares cole collide colton comparison computation computational compute computer computing conference consecutive constant construct constructed constructing construction contains convolution curse data databases datar datasets definition denote described development dictionary differ difference diim dimensional dimensionality dimensions discrete distance distributions dominates each easy efficient eficient efrat embeddings engineering errors event exactly fail failure farach faster fifth figures find finding fingerprint fingerprinting first focs follows foundations from functions generators geometry gionis given gottlieb happens hashing have having high identifying ieee immorlica indexing indyk informatics information institute international introduction jections jones journal june karp kleinberg koudas kushilevitz large latin leaves lemma length lewenstein line list lnllog locality manber martin massachusetts massive master matching method michael mirrokni molecular more most motifs motwani mount muthukrishnan myers nearest need neighbor neighbors netanyahu obtain obtained operations optimal order ostrovsky page pages pattern pevzner points position practical preprocessing press probability problem problems proceedings proof provably pseudorandom pstable rabani rabin random randomized recall recomb rectangular redesigned references removing representative research revisited sahinalp same scale scheme science search searches searching section segments sensitive sequence series sets show siam silverman similarity similarly simple since sizes sketches society some sorted spaces springer stable straightforward strategies stream string strings suffix symposium takes technology than that then theoretical theory thesis thirtieth this thus time tompa towards tree trends trie tries twentyninth using venkatasubramanian verlag very vldb well when where will with
http://doi.acm.org/10.1145/1109557.1109659	101	Anytime Algorithms for Multi-Armed Bandit Problems	aaai ability acmsiam action adaptive advances adversary against algorithm algorithms annual anytime appear application approaches armed artificial assuming assumption auctions auer awerbuch bandit bianchi blum boddy boosting bottou bounds cambridge case cesa claim claimed colt competitive compilation complement computation computer computing conditional conference continuous continuum contradicting convergence convex cope cost curve decisiontheoretic demand denote descent design discrete distributed dynamic event exists experiments feedback flaxman focs foundations freund generalization geometric gittins gradient hartline have hence ieee immediate implies index information intelligence jones journal kalai kleinberg knowing kumar laborative large learning least lecture leighton letting line littlestone location majority manuscript mcmahan moreover multiarmed national near nearly neural nonstochastic northholland note notes online operational optimal optimization posted press price prob probes problem proceedings processing programming progress provided putting rationality references regret reinforcement reward rout rudra saul schapire science sciences sequential setting siam soda solving spaces springer statistics stoc strategy such sufficiently symposium system systems that theoretical theory there thert this through thus tight time together uniformly unpublished using value verlag warmuth weighted weiss which with without zilberstein
http://doi.acm.org/10.1145/1109557.1109587	29	Self-Improving Algorithms	abound abuse acknowledgments adaptive additive adjusting adversary advice against agnostic albers algorithm algorithmica algorithms allen alon among amortized analyses analysis annual applications applying approximate approximation attractors attributes automata average badoiu bandit based behavior bentley bianchi binary bitner blum borodin bound case castro center cesa chawla chazelle chernoff clarkson classification clustering colloquium colt comments comp competitive comput computation computational compute computer computing consecutive consists convex coordinate core cube customized data deal decision declare decreased dependency descent detecting detection diagrams differs dimension dimensional discrete distribution does duda dynamic dynamical eatcs economic edition efficiency efficient ensures estivill every exactly exegesis expected expert exponential facility factor fail files flaxman focs foundations fredman freund from game games generalized geom geometric geometry georgiadis gonnet good gradient graphs hamming hart haussler helmbold helpful hester heuristics high hill hirschberg icalp ieee imai inaba individual indyk information international introduction irrelevant john journal kalai karpinski katoh kearns kenyon kleinberg kumar kushal kushilevitz languages learning lecture limiting line linear lision list lists littlestone living location loukas machine majority mator mazumdar mccabe mcgeoch mcgraw mcmahan means median mehlhorn method minc minv mishra mitchell mitzenmacher monographs motion multiplicative munro nearest neighbor notation note notes number oblinger observe obtained ones online operations optimality optimization organize organizing ostrovsky over pages paging pair papadimitriou parnas pattern peled piotr pitt playing points poly polynomial prabhakar press probabilistic probability problem problems proc proceedings programming quick quickly rabani randomization records references relocatable renato requires research rivest rules running sabharwal sariel schapire schemes science search searching segmentation self sellie sequential serial sets setting shows siam simple sleator smal socg soda solved sons sorting spaces sparse spencer springer state static still stoc storage stork strange structures sublinear sudakov summary surv survey surveys suwanda symposium systems takens tarjan testing thank that their theoretical theory these think this thorup threshold time towards trees turbulence update using variance variances vazirani vectors vega vempala volume voronoi warmuth weighted weights werneck westbrook when where wildcards wiley will wish with without wood work worst yaniv zeroing
http://doi.acm.org/10.1145/1109557.1109578	20	Computing Steiner Minimum Trees in Hamming Metric	academic actually advances after algorithm algorithms alignment allocated along also analysis appl applicability application applied approach approximation arenaviridae author avian based being benefit bioinformatics biology biosci biosciences borna bornaviridae both bound bounds bovine bradford branch briefings bunyaviridae call canine cannot carlo certain change chare clearly column columns combinatorial comparison complete complexity comput computation computational computing congo connected consumed cormen corresponding course crimean crosse current data defining depends determine discrepancy disease distance distemper distributed dobrava dominates drake dynamic efficiency efficiently elephant entries evolution evolutionary exact exceeded exclude experiments fact family fast felsenstein fever finding fitch foulds from further gascuel gbyte gene genetics gould graham grassly guaranteeing hamming hantaan have heavily hematopoietic hemorrhagic hence hendy holland holmes homologous hougardy hours html http huber human improve improved improvement improving indiana infectious inference influenza information instance integrated interrupted introduction junin kluwer kumar lassa leiserson less letters life limits lirmm lower mark matching mathematical mathematics measles mega methods mini minimal minimum minmax models molecular monte more most moulton mumps negative networks newcastle nombre optimization optimizations oropouche orthomyxoviridae other outperforms oxford package parainfluenza paramyxoviridae parsimonious parsimony part partial paup penny phylip phylogenetic phylogenetics phylogeny plane pneumovirus polyhedra polzin population preliminary preprocessing presented press previous problem problems process processing program programs progress properties pruning publishers purdom puumala quartet quickly rambaut ranwez rate real recombination references respiratory reveals rhabdoviridae rice rift rivest root running saarlandes schrijver sendai sense septicaemia sequence should show sign simple simulation single software solving spanned species specified spotted springer squeeze stated steel steiner still stomatitis stripe study swofford syncytial systematic table tamura terminals terminated tested than that their these thesis threshold tight tighter time times tomato topologies topology toward tree trees trends triples trying unclassified unfortunately universit university used using various version vesicular viral virol virus viruses warme washington ways weighted when wilt winter with work zachariasen zoology
http://doi.acm.org/10.1145/1109557.1109693	135	Squeezing Succinct Data Structures into Entropy Bounds	above achieved acknowledgments acmsiam adam adapted adaptive algorithms almost alphabets also analyzing ancestor andrej ankur anna appear application applications applied approach april array arrays asymptotical attention august author balanced based beame because been below bender benoit bentley beyond binary bits blandford blelloch block blocks bound bounded bounds brodnik burrow cannot case cases cell claim cocoon code codes coding colton coma comm compact complementary complexity compressed compressing compression computer computing concluding confined conreferences consecutive consider constant converges corresponding cover crete dagstuhl daniel data dataaware david debt decode decompressing define degree demaine dense describe design designed dictionaries dictionary discuswe divide does duced dynamic each easily edge efficient elements elias empirical encoded encoding enlightening entropy equals equation ergodic erik examples exists experiments extended farach ferragina fich finally first focs from fsttcs function functionalities functions geary general generated getting giovanni gnavarro golynski graphs grossi gupta have hich high higher highman holds icalp idea ieee implies important improve improvement improvements increases independent indexable indexes indexing individual inform information integers interscience interval into intro introduction jacobson jeev jeff journal june kash kindly kinen kolmogorov kosara kunihiko labeled labels large lempel length level like line lncs locally lower luccio made manuscript many manzini match matching measure measures membership mentioned methods miltersen minimum most multiplicative multisets munro muthukrishnan namely navarro needed novel number numbering obtain october only operation operations opportunistic optimal order ordered ordinal other others otherwise ours over overlap pagh paolo parentheses permutations peter phrases plexity pointing poon position positions predecessor presented preserving previous previously probe problem proc prof proof propose proposed provided queries query rahman raman range rank rasmus raspace rate recency recently reducing redundancy regions related remarks reobserving representation representations representing results richard sadakane scheme schemes science second secont section select selection seminar separable separately september sequence sequences sets shah siam simple simplified since sions size sleator soda source space springer squeeze srinivasa static stationlary stoc store stored storing storm string strings structure structures structuring subsequent substring succinct succinctly succinctness such suffix suite support supported tables tarjan terms text thank that their them theorem theoretical theory there therefore these they this thomas though time tool trans transform trees trie uchile until upper users using values variable variation venkatesh verlag vitanyi vitter wads well wheeler when where which while whose wiley with word work would yielding
http://doi.acm.org/10.1145/1109557.1109635	77	Trading Off Space for Passes in Graph Streaming Problems	above achieve adapted aggarwal alalthough algorithm algorithms alice alon already also analysis annual appear application applications approach approx approximate approximating approximation arguments athos augmented automata available babu back based between biconnectivity birkh bits bound bounds buchsbaum california cambridge cessed classical closure cock combinatorial communication complete complexity computational computer computing conference connectivity consider considerations considered containing content context continues contradiction copying cormen corresponding counting creates data database databases datar dealing department depth designing determine difference dimacs discrete disjointness distances distinct distinctness does ducing duplicates dynamic each easy edition efficient electrical element elements ello engineering even exactly example except exemplify external factor fast feigenbaum find finding first focs folklore following fork foundations francisco free frequency from fully functional geffert gilb give given golab gorithmica graph graphs greene grigni guha half halve hardness have help henzinger here heyb high histogram http icalp ieee image impossible increasing indeed indices indyk information input instance institute intermediate international interof introduction issues items jagopalan journal just kannan king know known knuth kotidis kumar kushilevitz languages large leiserson letters limited logarithmic loquium lower maintains maintenance makes making management managing many massachusetts massive matchings mathematics matias mcgregor mediate mehlhorn memory model models moments monotone more motwani much munro muthu muthukrishnan network nisan nondeterministic notheorem number numbers observed only optimal optimization other ound over overall ozsu pages parallel particular pass passes paterson paths pods possibly powerful press previous price primitive principles probability problem problems proc proceedings processed processes processing produced producing product programming proof proves provide proving quick quicksand raghavan reading received recognition reduced reductions references regardless remark requires respect respectively results rivest ruhl runs rutgers same school science sciences second section selection semi sends sent separation series shortest show siam similar simplifying simulated simulation since sipser sivakumar size small soda solution solved solves some sorting space starting starts stein stoc storage strauss stream streaming streams structures such sullivan summary suri survey surveys symposium system systems szegedy take taking task technical technique technology than that then theorem theoretical theory there thesis thirteenth this thus tice total traffic transitive triangles trib ullman undirected uninteresting university unuseful used usenix user uses using value vector vectorother vectors violate viswanathan vitter want waterloo well westbrook when whether which widom will with working workshop would yannakakis yields yossef zhang
http://doi.acm.org/10.1145/1109557.1109645	87	Spanners and emulators with sublinear distance errors	able additive aingworth algorithm algorithms almost also alth always announced another approximate awerbuch baswana berger bollob chekuri cohen combine communication compact complexity computational computing constant constructed constructing construction constructions copp covers cowen deterministic diameter discrete distance dobkin edges efficiency eilam either elkin erin error ersmith estimation etween every exists fact factor fast ffer form from gavoille general geometry graph graphs halp have here however icalp ideas indyk into intriguing involved jective joseph journal kavitha linear main mathematics matrix mehlhorn minimum more motwani multiplication multiplicative near needed neighb network number obtain obtained olynomial open oracles orhood original pages pair pairs paper particular paths peleg pettie podc porceedings possible present preservers previous private problem proc properties purely quite recently references roditty routing schemes seems seth shortest showed siam significantly simple simplest size slightly smaller soares soda some source spaa space spanner spanners sparse still stoc stretch subgraph such synchronization tables techniques terms that then theory there these this thorup time trade turn undirected unweighted upfal vertices weighted were whether which will wise with without zwick
http://doi.acm.org/10.1145/1109557.1109575	17	An Asymptotic Approximation Algorithm for 3D-Strip Packing	algorithm algorithms annual approximability bansal bins bounds caprara computer computing csirik dimensional discrete foundations garey harmony ieee inapproximability johnson journal letters level line multidimensional operations oriented packing performance proceedings references research results science siam sviridenko symposium tarjan vliet
http://doi.acm.org/10.1145/1109557.1109596	38	Improved approximation algorithms for Broadcast Scheduling	acknowledgments acmsiam additional ageev airmedia algorithms analysis annual approximating approximation arbitrary average bansal bartal baruch batching bipartite broadcast broadcasts cambridge charikar chazelle combinatorial combined complexity computer conference consider constructing cost dead defined dependent desired direcpc disc discrepancy discrete discussions during edition editor edmonds equivalence erlebach european exists fairness feasible fine first flow focs following forty found foundations func function gailis gandhi graph graphs grzegorz guarantee guha hall handbook hardness helpful http ieee inapproximability integer integral intel intercast interval ipco joseph journal kalyanasundaram katz khanna khuller kimbrel kirk least lemma lemmata letters leung linear lines longest maiden manuscript maximization maximum method minimizing models moses most muthukrishnan naor networks nowicki omitted online operations optimal optimization page pages parthasarathy performance pipage polynomial preliminary press proc program programming proof properties property proven pruhs publication randomness realtime references relaxations research response result rounding sanjeev scheduling schieber science seffi sgall shachnai siam single slot soda solu solution source srinivasan submitted such sviridenko swirszcz symp symposium thank that then theorem there third throughput time tion tomasz torng tracy transmitted university unpublished unsplittable value velauthapillai version wait website weight when wireless with yield
http://doi.acm.org/10.1145/1109557.1109673	115	A Tight Upper Bound on the Probabilistic Embedding of Series-Parallel Graphs	algorithm algorithmic algorithms alon analysis application applications approximating approximation approximations arbitrary august automata bafna bartal bound bounds california case chao charikar chekuri choices choosing circle communication competitive complexity comput computational compute computer computing conditioned contribution contributions cost cuts decomposition design deterministic digraphs discr discrete distg distortion edge efficiently elkin embedding embeddings emek every excluded expected fakcharoenphol finite flow foundations francisco game geometry goel graph graphs guarantee guha gupta help heuristics ieee international january johnson journal karp klein konjevod kserver lancia languages lawler lenstra lett loquium lower manuscript math mathematics method metric metrics minimizes minimum minors most multicommodity network networks newman number optimum pages parallel peleg physics planar plotkin points polylog polynomial previous probabilistic problem proc process programming rabinovich randomized ravi really recognition references remove reshef rinnooykan riordan routing salman scheme science series shannon siam sinclair small solution spaces spanning spencer spielman steiner stretch such symp talwar tang tarjan teng that theoretic theory therefore these tight time tree trees twoterminal ucost valdes value west which wiley wong worst
http://doi.acm.org/10.1145/1109557.1109631	73	The Complexity of Quantitative Concurrent Parity Games	acad alfaro algebra algorithms alternating alur angeles annals applications applied atabases automata automatic basu berkeley blackwell buchi calculus california chatterjee class classical closed competitive complexity computation computer concurrent conditions condon constraint contributions control deciding decision descriptive determinacy discrete editor elementary elimination elsevier emerson equilibria event everett expressions fields filar finite focs form formal game games geometry graphs handbook henzinger ieee infinite information international jects journal jumdar jurdzinski jutla kechris kupferman landweber languages large leeuwen letters lics lipton lncs logic lpar markakis markov martin mathematical mciver mcnaughton mehta mertens method methods models module morgan mostowski mucalculus nash neyman omega omegaregular operations optimization over pages parity played playing pnueli popl press probabilistic probability proc processes processing pure quantifier quantitative raghavan ramadge reactive real recursive references regular research results rosner science sciences sequential shapley siam simple society soda solution solving springer standard state stochastic strategies studies supervisory survey symbolic symposium synthesis system systems tarski temporal theoretical theory thomas time transactions tree trees university using vardi verification volume vrieze winner wonham
http://doi.acm.org/10.1145/1109557.1109649	91	Max-Tolerance Graphs as Intersection Graphs: Cliques, Cycles, and Recognition 	addison advanced algorithmic algorithms alignment altschul annals appendix arci balls basic bent berkeley berlin biol blast bogart bold booth cambridge case chain chains clause combinatorics comparability completeness complexity component comput computer computers connected consecutive crossing crossover discrete disks drawing either false figure fishburn freeman from fulkerson gadget garey general gish golumbic graph graphs gross guide heidelberg hlinny horizontal http illustration implementing incidence intersection interval intractability invariance isaak jacobson john johnson kratochv ladder ladders laison lecture left lipman local lueker math mathematica mathematics matrices miller morris myers ncbi noncrossing north notes ones order ordered orders other pacific part partially perfect placed planarity plane positions possible press proceedings property reach reached recognition references representation representations representing results right scheinermann schematic science search semi september sets show showing shows skiena sons springer square starting studies study survey testing that theory three tolerance tool touching tree trenk true university using variable verlag vertical wesley wiley with without york
http://doi.acm.org/10.1145/1109557.1109643	85	Weighted Isotonic Regression under the L1 Norm	acad additive afshari ahuja algorithm algorithmic algorithmica algorithms ames amir analysis annals another appl application approach approx approximating approximation arithmetic astin avis ayer banerjee barlow benichou benny biased binary binks bioinformatics biology biomarkers biometrics biostatistics biswas bootstrap boyarshinov brunk brunswichk bulletin calculate cancer central chain chen chor chung clarice class clinical clustering coin comparison comput computation computational computer confidence consistent constraints construction convex coppersmith cormen course curve cynthia data david debashis department dept design dickinson diggle dilleen dimensional direction discovering discrete distribution doratha dose dosefinding doseresponse down drake dual edmonds edward efficiency efficient empirical endpoints epidemiological epidemiology ernst establishing estimating estimators ewing existence experiments expression fast finally find finding flournoy flow fris function functions gene geng ghosh gothenburg guoliang heimann heuristics hirsch hougardy improved improvements incomplete inference information interesting intervals introduction iowa ismail isotonic isotornic ivanova jack james jewell john jones joseph journal karp korean leiserson leping lett leuraud linear lobenhofer local locating magdon malik mancuso matching matchings math mathematical matrix maximum maxwell median methods michigan microarray minimizing models monotone monotonic morton moulinath muckstadt multiplication mureika network networks nonparametric norm norms oper operations optimal optimization optimizing order ordered orderings orderrestricted orlin panos paper parameters parametric pardalos parker partial peddada pehrsson pinaki preserving press problem problems procedure procedures production progressions quentin random ravindra realistic references regression reid related relationship relationships reorder report research response restricted richard rivest robertson sampling scaling science selection separable series several shmuel short shyamal silverman society stat statist statistician statistics stefan stein stout structure studies stylianou subject submatrix survey symb systems tariff tech test tests theoretical theory thesis time trend trials turner ubhaya umbach umbrel under unfit unimodal univ university uregr using victor waltman wang weighted weights weinberg william winograd with wollan working yakhini yong zohar
http://doi.acm.org/10.1145/1109557.1109565	7	Improved Embeddings of Graph Metrics into Random Trees	algorithm algorithmic algorithms alon also application applications approximating approximation approximations arbitrary aspects awerbuch azar bartal bound bulk calinescu centers charikar chekuri circuits classification combinatorica components computer computing condition considered cuts decomposition design deterministic directed discrete distance edge elkin embedding embeddings emek extension fakcharoenphol fields finite focs foundations fractional game garg geometric given goel graph graphs group guha gupta hand ieee indyk into journal karloff karp kleinberg konjevod labeling lower markov median metric metrics necessary network newman nodes note number obtain only order osium other outerplanar packing pages pairwise peleg permutation plotkin polylogarithmic portal probabilistic problem problems proc proceedings rabani rabinovich random ravi references relationships root rounding save saved science server seymour siam sideways sinclair smal soda spaces spanning spielman star steiner still stoc stretch symp symposium talwar tardos teng that then theoretic theory this thus tight tree trees vertices west while with
http://doi.acm.org/10.1145/1109557.1109613	55	On the Number of Plane Graphs	abstract accin acciones acknowledgments aichholzer ajtai algorithms amer analytic annual applications april ares aurenhammer austria austrian barcelona base better between boca both bound bounds brass cambridge canada canadian cardinality central certain chain challenging chvatal close combin combinatorics combining communication complete complexity comput computational concerning conference configurations construction constructions convex convexity counting course crossing crossings cycles data discrete does double dumitrescu edition editors enormous entries enumerating equivalent erdos espaa especially european even example examples exist extension factors ferran fill find following fonds forderung forschung free from further gaps garc geom geometry gives goal goodman grant graph graphs hackl handbook have here html http hurtado improve industrial integrada integradas interesting isomorphic issues italy ject jects joint jolet known krasser least lection leighton linkages locked lower made mapping matchings math mathematics maximizing mcyt minimizes missing monthly moser most narrow newborn noncrossing number numi obtained obviously ontario orden order oswin other pach page part partially partitions personal pisa planar point polytope possible press problems proc progress pseudo question randall raton recently rectilinear references required research resulting results ribo rote rourke same santos second seidel selftouching sets several sevilla sharir shows siam simplified smal snoeyink spain speckmann springer subgraphs such supported symposium szemer table tables tejel that thelog theory there thesis thomas thus total triangulations tugraz type types under unified unlocked upper verlag vlsi waterloo well welzl wheels which while wissenschaftlichen with work works workshop ximum york
http://doi.acm.org/10.1145/1109557.1109567	9	Metric Cotype	acta advances alamitos aleatoires algorithmic algorithms almost alon amer american amir anal analysis annual appear appendices appl application applications approximating approximations arbitrary arora assume ball banach band bartal based basel bates benyamini berlin between birkhauser birthday bodies boston bound bourgain carolin chains chapter characterizations choose cknowledgments coarse coarsely coefficients colloquium combinatorica combinatorics comment comments comput computer computing conditions connection constants contiennent convex convexity corollary cotype courant cuts define definition denote deza differentiable dimension dimensional discrete discussions distortion does ecole edition embed embedding embeddings embeds enflo ergebnisse espaces essays euclidean every exist exists expose extensions extremum fact fakcharoenphol figiel finite first following follows foundations french from full funct functional game geom geometric geometrie geometriques geometry girth global graduate graph graphs grateful grenzgebiete gromov groups gupta hand helped hilbert homeomorphisms hyperbolic ibid ieee ihrer improving independantes indyk inequalities infinite infinitely inner integers interpretation interscience into isomorphic israel january john johnson karp katz keith known kwapien larger laurent lecture lectures lemma like lindenstrauss linear linial lipschitz local london lovasz magen manuscript many mappings maps markov math mathematical mathematics mathematik matousek maurey mendel methods metric metrical metrics michael milman multiplication naor newman nonexistence nonlinear nonriemannian notes operator original orthogonal other pages palaiseau pansu paper peleg peres phenomena pisier pointing polytech preprint presentation presented press probabilistic probability problem problems proceedings product progress proof properties proprietes prove providence publications publishers quotients rabani rabinovich radonif ramsey randrianarivony referees references required riemannian riesz roots saks scand schramm schwartz science sean second sections semin seminaire semmes series server several sheffield siam side since sinclair smooth society soda some space spaces spherical springer springerverlag square strengthening structures studia studies subsidiary such superreflexivity symposium talwar texts than thank that then theorem theoretic theory there this tight topological trans transforms translated tree trees type uniform uniformement uniformly univ using valuable valued varenna variables vector vectorielles vempala verlag version versus volume well wells west when which williams with wolfson york yuri
http://doi.acm.org/10.1145/1109557.1109685	127	The Space Complexity of Pass-Efficient Algorithms for Clustering	algorithm algorithms alon annual approach approximate approximating approximations arbitrary arora asymmetric based bases better callaghan charikar chaudhuri chekuri clustering communication complexity comput computation computer computing conference constant construction dasgupta data dimension dimensions discrete distances distributions drineas dynamic eddings efficient enough extensions external fast feder feigenbaum flexible foundations fourteenth frequency gaussian gaussians generators gibb gilb graph guarantees guha henzinger histogram histograms ieee include incremental indyk information international jagadish jagopalan jayram kannan kotidis koudas kumar large learning limited maintenance matias matrices mcgregor memory miltersen mixtures model moments more motwani much munro muthukrishnan narasayya nisan optimal pages panigrahy pass paterson poosala possible problem problems proceedings pseudorandom quality raghavan random references retrieval safra sampling science selection sevcik shim siam sigmod sivakumar small sorting space stable statistics storage strauss stream streaming streams structures suel suri symposium syst szegedy theoretical theory three uniform value very vitter wang wavelet wigderson with woodruff yossef
http://doi.acm.org/10.1145/1109557.1109677	119	Knapsack Auctions	aaai abrams adwords agents alem algorithms annual approximation artificial auction auctions available balcan behavior bidders blum borgs budget budgets chayes choice clarke collusion combinatorial commerce competitive computer computing conference constrained counterspeculation design digital discrete earlier econometrica economic electronic envy expected fact fiat finance foundations free games generalized goldberg goods groves guruswami hartline have ieee immorlica incentives inequality intelligence intertrust karlin kempe kenyon learning least machine mahdian mansour matching mathematics maximization maximizing mcsherry mechanism mechanisms mehta multi multipart myerson national near nisan online operations optimal pages parameter pricing proc proceedings profit public publication putting references report research resistant restricted revenue saberi saks science sealed setting siam single star submitted symp symposium teams technical tenders that theorem theory truthful unit used using value vazirani version vickrey when with wright
http://doi.acm.org/10.1145/1109557.1109651	93	Critical chromatic number and the complexity of perfect packings in graphs	adjacency after algorithm algorithmic algorithms alon also appear application applications approximation argument aspects baker berman blow bollob bolyai bounded budapest case colouring comb combin combinatorica combinatorics como complete complexity computer computing conjecture considering constant copies degree dense described diestel disc discrete duke each ects edition eighty erds every exceptional factor factors finds follows found foundations from general generalized graduate graph graphs greedy guaranteed have hell heuristics hurkens ieee incorporate information interscience into johnson just kann kawarabayashi kirkpatrick koml kuhn large lefmann leighton lemma letters loquia matching math mathematical mathematics matrix maximum method mikl minimum modern nontrivial note npcomplete order osthus packing packings paragraph partition parts paul perfect planar point preparation probab probabilistic problems proc processing proof random ratio reduced references referred regularity remove runs scheduling schrijver science section sets shokoufandeh shor siam simonovits size snyder society spencer springer struct studies subgraphs submitted symp systems szemer sznyi takes taraz texts that theorem theorems theory this those thresh tiling time translation using verlag version vertex vertices where which wiley with worst yuster zhao
http://doi.acm.org/10.1145/1109557.1109662	104	Randomized Online Algorithms for Minimum Metric Bipartite Matching	algorithm algorithmic algorithms also applications appropriate approximating approximation arbitrary arrives arriving bartal bipartite bounded call chstattler competitive computer computing conjecture consider consist construct continue cost could discrete duce each ecause ected eliminate endence enphol entire exceed expected fakcharo find follows formed foundations from fuchs functions given gives graph greedy hand here ieee immediate implies improve inequality initial innite journal kalyanasundaram karp kern khuller koutsoupias left line lower marriages match matching mathematics metho metric metrics might mitchell most must nanavati nearest nite nodes numb number observe online only optimal optimum original ortation ound ounds papadimitriou particular particularly petitive points previous problem proof pruhs random randomized randomly ratio references required restricting result right science section select selected server soda spaces stable symposium talwar that then theorem theoretical theory there this thus tied tight times trans transferred tree triangle uniformly unmatched useful using vazirani weighted when whenever will with workshop would
http://doi.acm.org/10.1145/1109557.1109623	65	A Computational Study of External-Memory BFS Algorithms	accesses acmsiam aggarwal ajwani alenex algorithm algorithmic algorithmica algorithms almost alof alvolume amortized annual appear applications architectures arge balance barracuda based better between bounded breadth brodal buchsbaum cache case chiang choose cluster clusters coarse coarsegrained comcould communicafor communication complexity computations compute computer computing conference consequently considered cormen crawler crawling data dealing dehne demaine dementiev design detail diameter difin diglib digraph discrete discsales disk distributed dittrich documentation duke duration edelkamp edge efficient endent engeneering engineering european even expected experimental experiments external fagerberg fakult fewer first foundations frigo from general gerth goldberg goldwasser goodrich gorithms grained graph graphs grid grove gustedt have hierarchical hierarchies high hill homepage html http hutchinson iccsa icde ieee implementation implementations implementing informatik information input intern internal international introduction isaac jabbar january ject jork karlsruhe kettner knowing ladner lamarca larger lecture leiserson less letters level levels library lnai lncs loading longer maheshwari making marketing massive masters mathworld mcgraw mehlhorn memories memory meyer multi munagala need nodes notes oblivious only optimal optimized order outerplanar output pages paradigm paral parallel partitioning paths performance permutations personal phase phases planar plexity point pointto pool preferable press problem problems proc processing procopiuc products prokop quality ramachandran ranade random realistic references reif related report resource rivest running runs saarland sanders scand scandinavian school schr science seagate search separation separators sequential sets shkapenyuk short shortest should show shriver siam sibeyn simulating since single small society soda sorting source sourceforge spaa space specification spider spirakis springer sssp standard stanford stays structure structures study stxxl sublinear suel summer surveys swat symp symposium table tamasia technical technology template terrains testbed than that theferent them theory there thereby therefore thesis this time tions toma towards tpie traversal traversals treewidth tutorial ulrich undirected university using value vengroff venkatasubramanian very vinther vitter volume wait ways webbase webgraph weisstein werneck westbrook when where wide wiener with wolfram workshop world yields
http://doi.acm.org/10.1145/1109557.1109683	125	The Hunting of the Bump: On Maximizing Statistical Discrepancy	additive advances analysis annals applications approximation april aumann balakrishnan because bichromatic birkhauser boston bump calculation clusters communications computational computed computer computing const constant constants containing copy cormode corresponding cressie data detecting detection diamond dimensional discrepancy disease dobkin dwass dynamically each ective edition efficient eppstein eriodic fast finding fisher fixed frequent friedman gamma geographical geometry glaz good graphics guide gunopulos heavy hence hierarchical high hitters hunting hypotheses ignoring information interval items iyengar john journal korn kulldorff learning least linial lipson maass machine march mathematical maximization maximizing maximum measure method methods modified moore most multi multiresolution muthukrishnan naus nctr neill neural neurocolt nonparametric numb otheses over paramper permutation pods practical processing prosp prospective randomization rapid recomb rectangles references report resampling respect rough royal scan scores series shape sigmod significant society space spatial springer springerverlag srivastava statistic statistical statistics surveillance symposium systems takes technical testing tests theorem theory thus time tracking using verlag wallenstein what wiley windows with yakhini york
http://doi.acm.org/10.1145/1109557.1109626	68	The Prize-Collecting Generalized Steiner Tree Problem Via A New Approach Of Primal-Dual Schema	abstract according acknowledgement active adjacent algorithm algorithmica algorithms allocations also altogether always among analysis annual another appear appendix applicable application applied approx approxi approximate approximating approximation arbitrary area authors average awerbuch back bartal baruch based before berlin best better between bipartite bisection bought bound building bulk call case charging choose claim clique collecting collide combinatorial commerce complexity component components comput computer computing conference connected consider considering constant constrained constraint control convex cooperative corresponding cost costs could cover current deactivated degree dense densest design designing desired different directly discrete discussion discussions distribute distribution doubly dual each early easily easy edge edges efficient efficiently eisenberg elastic electronic eliminate embedding endpoints equilibrium equitable equivalent european even except exponential extended facility factor fakcharoenphol family farkas feasible finally find first fixed flow focs following follows forest form foundations fractional framework from fruitful full function furthermore gale game games general generalized getting give global goemans goemanswilliamsoen graph graphs hall hand hard hardness have having help here holds idea ideally ieee illustrative imagine immediate immediately important impossible improved improvement improves inactive incomplete increase indeed induced induction inequality input installation instance instead instrumental integer interesting international interval into introduction invariant ipco isolated issues iteration iterations iteratvon itself john knowledge ksubgraph laci lagrangean lagrangian later leaf least leaves left lemma lems like linear link location logarithmic london loop lovasz machinery mahdian main makes manuscript marked market matching math mation maximum means mechanisms mechansims median mentioned mentioning method methods metric metrices metrics michel minimum mirrokni mohamorems more most msts multicommodity must naturally need network networks node nodes note number numerous observe obtain obtained obtaining once only open optimization optimum original other otherwise outage pair pairs paper papers parameter particular partition path pcgst penalties penalty perfect phase play polynomial power powerset practical prentice preparation presented press price primal primaldual prize prob probabilistically problem problems procedure proceedings programming programs proof propose proposed prove ptas raise random range rate ratio ratios ready really recovery reduce references relations relaxation remove rent resource result results rewriting right river role round rounding ruling saddle salesman schema science section seems selected sets setting shared sharing should show shown shows siam side similar simple simpler since single sink slight society soda solution solve solved solving some sometimes sons special springer stars steiner stoc straightforward strategy strategyproof subgraph submitted such symposium systematic tackled technique telecommunications terms thank thanks that then theorem theory there therefore these this thought thus tight time total traffic transactions traveling tree trees type understanding uniformly unique unmarked upper used useful user users using vahab variable verlag versa version vertex vertices very visa weight weighted when where whether which while whose wide wiley will williamson with within work worth would write york zero
http://doi.acm.org/10.1145/1109557.1109657	99	Query-Efficient Algorithms for Polynomial Interpolation over Composites	acknowledgments adic agrawal algebra algebraic algorithms alon american anders annals annual anonymous applications approaches approximations aubrey available avrim babai barrington based basu beigel bernstein better between bhatnagar biswas bjorner blum boolean bound bounds bshouty cahen capacity case certain chabert chinese christino combinatorial combinatorica combinatorics comments communication commutative complexity composite composites computation computational computer computers conference connections consequences constructing constructions coprimes croot daniel david degree detecting discrete discussions efficient ernie essentially european every explicit factoring following foundations frankl freeman frisch from function functions further gabor garey gatech geometric give given goldreich gopalan graph graphs greatly greedoids grolmusz gunter have helpful highly http identity ieee igor improved integer integervalued interpolation intersection intersections into intractability introduction jayram jean johnson journal kale karpinski kayal kearns kempner kumar kutin laszlo learning lecture line linear lipton lower machine madhu manindra many mappings marek mathematical mathematics matrix matroid methods modular modulo monographs monthly motivates nader narkiewicz nayantara neera nitin noga noisy notes numbers oded online open over pages paper parik parikshit paul perfect peter point polynomial polynomials poorten powers preliminary presentation press primality prime primes problem problems proceedings properties protocols queries query ramsey ravi referee references remaindering representations representing residue restricted results richard rings robert ronitt rubinfeld rudich samuel satyen saugata saxena science shannon show shparlinski siam simultaneous size smallest some somenath sophie spira springer stefankovic steven submitted such sudan superpolynomial surveys symmetric symposium systems tamon tardos terms testing thank that their theorems theoretical theory there this time transactions union useful vazirani version vince which will wilson with wladyslaw would york zero ziegler
http://doi.acm.org/10.1145/1109557.1109639	81	Linear Programming and Unique Sink Orientations	abstract academic according acknowledgment advances algorithm algorithmica algorithmically algorithms also annu anonymous arising aware axioms bardtyp been breaking case chosen combinatorial combinatorica coming complementarity complementary comput computer computing condition conference consider corrections cottle crossp dantzig details develin digraph dimensional discrete discussion disjoint distinguishing distribution does early edge employed ercub existence exploited extensions face facets fibonacci finding focs follows foundations freeman from full function geom geometry given going graduate grids guarantee have help helpful high holds holt idea ieee improved improvements induced integer interesting ipco jective jumping just kalai khachiyan klee leading lecture lectures lexicographic linear lower makes manuscript many math mathematical mathematics matouek matrix means metho models morris nential nonlinear notes numb obvious olytop onential operations optimization order orientations ound pages pang paper particular paths peressini perturbing phys pivot plcp plcpinduced pleasing point pointing polynomial polytopes possible press principal probability probably problem problems proc programming programs property question random randomized randomly recently referee references research resolved rtner rust satisfy schurr science section seesaw sharir shown simplex since sink small soda solution some source sources springer stickney stone stract subclass suggestions suitable sullivan symp szab takes terms texts thank that theorem theory this through ties time todd under undergraduate underlying unfortunately unique vector verlag vertex very view volume watson welzl whether will with york ziegler
http://doi.acm.org/10.1145/1109557.1109616	58	A simple GAP-canceling algorithm for the generalized maximum flow problem	absorbing achieve acknowledgements addison additional algo algorithm algorithmic algorithms along also angewandte appears approach appropriately approximation arcs area arises aspvall associated assume assumption augmenting author away because being bellman bertsekas bixby bounds boyd cancel canceling cannot carolo case causes certain change checking circulation circulations claims class clear cleverness closed cohen combinatorial come communications computations computer computing conclude conclusion conserved considers consisting constant contains contracting contradicts converge converged convergence conversations convex cormen correct corresponding cost costs could counterexample cplex cycle cycles dash deficit defines department design detection determine determining different directed discussions distributivity does dual each early edges editors edmonds efficiency efficient either element elements empty equivalent even example exists extension fact fail failure familiarity fast faster figure finally finding first fixed fleischer flow flows ford foundations fractional franklin from gain gains gaps garg general generalised generalization generalized generating give given goemans goldberg goldfarb gondran graph graphs have here highest hochbaum however identity ieee illustrates ilog improved improvements improving inequalities inequality information input institut institute integer introduction invocation invoke invokes iterations journal karp kind kleinberg konemann label labels lead lecture left leiserson lemma length less light linear made mathematical mathematics mathematik maximum mean megiddo mercado method michel minimality minimum minimumcost minoux modified multicommodity must naor needed negative negativecost network networks never notation note notes number observation observes obtained oldham onaga only open operations operator optimal optimization optimum orlin other outstanding packing pages pair paragraph particular path plotkin polynomial positive possible possibly practical precisely press previous problem problems proceedings programming programs question quite radzik reach reciprocals reduced references relaxation report research reserve reuse reversed rithms rivest routine rule running satisfiability says schemes science second section seem seems selection semirings separable sergei shiloach shortest siam simple simpler simplex since sink smaller smallest solving some springer stancs stanford strongly such summaries summary symposium systems tardos tarjan technical technische terminate than thank that their then theorem theoretical there thesis this throw throws thus time truemper tseng type unfortunately unit universitat university update useful variables vassilvitskii vertex vertices walk wallacher wayne wesley western where whether which wiley wilhelmina will wishes with would xpress york zero
http://doi.acm.org/10.1145/1109557.1109660	102	Robbing the bandit: Less regret in online geometric optimization against an adaptive adversary.	acknowledgements actual adam adaptive adat adversarial adversaries adversary advice against algorithm algorithms alized also always american annual anonymous application approaches approximation armed ascent aspects assuming auer averaging avrim away awerbuch azuma bandit bayes beating because becomes best bianchi bias black blum boosting brief bulletin cases casino cesa chakraborty chooses chosen clear coin coincides comments computation computer computing conditional conditioning conference constant contributions conversations convex cost dani dated decision denote design distributed does done dresher editors efficient encouraget endix entire expected experiments exploit exploits explore explores extended favorite feedback flipper following foundations fraction freund from gambling games gener generalization geometric gradient grateful hannan have hayes hedging helpful hence history hoeffding however ieee improved include independence independently inequality infinitesimal information international into journal june kalai kleinberg learning learno less like littlestone loss machine majority make manuscript martingales mathematical mcmahan ment much multi multiarmed negative next notation note number observed online only onsidering operates optimal optimization otherwise over play press princeton prior problem proceedings produces programming proof purposes random referees reference references regret repeated rigged risk robbins round rounds routing schapire science sciences sequential setting siam since society some sourav step steps stimulating stochastic summing symposium system thank that theorem theoretic theory there these this through time title total translated tucker university vectorvalued vempala versary version warmuth weighted when where which whichever with wolfe working would wrong zinkevich
http://doi.acm.org/10.1145/1109557.1109615	57	An O(n log n) algorithm for maximum st-flow in a directed planar graph	acar adjusting after algorithm algorithmica algorithms along also alstrup ambivalent analysis applications applies arxiv august becomes been biedl blelloch branislav brejova canadian capacities carrying case changing comput computer computers computing connectivity data definition determine dimensions disc disjoint dover dynamic dynamizing edge edges editors efficient endence eppstein eration extends fakcharoenphol faster flow flows focs follows ford forest foundations frederickson from fulkerson fully fund geometry goldb graph graphs harp hassin have henzinger history holm http indep information introduction itai italiano jcss johnson journal khuller king klein lattice lecture lichtenb linear lipa maintaining maintenance math mathematical mathematics maximal maximum menger mfcs miller minimum mogens multiple multiplesource must naor natural near negative network networks next nielsen nodes notes novemb observation olylogarithmic order pages paral path paths planar planarity point preserved problem pushed randomized reduction references reif residual reverse ripphausen rovan saturated science self sequential shiloach shortest siam simplifying simply single sink sinks sleator smallest soda sommerville source sources spanning sparse springer static step structure structures subramanian tamassia tarjan that therefore thesis thorup through time traditional trees undirected unusable vertex vinar vittes volume wagner weight weihe werneck westbrook when whether whitney with yung
http://doi.acm.org/10.1145/1109557.1109601	43	The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree Distributed Data Structure	acmsiam algorithms alon alternative applications architectures area arge aspnes awerbuch balakrishnan balanced balancing bawa beigel berkeley better castro cheater chord code commun communication computational computer computing conference congestion constant data decentralized degree design detection deterministic diagnosis dictionary discrete distributed druschel efficient elining eppstein erasure erties estry event family fault flash focs foundations ganesan goodrich graphs grids group harvey hash hashing hurwood ieee information infrastructure internet ject jones joseph kaashoek kahale karger kermarrec kirsch know koorde krishnamurthy kubiatowicz large largescale lecture leware linear lists lncs load locality location lookahead lookup luby manku margulis midd morris multidimensional munro naor nearly neighb network networked networks notes notification numb optimal ordered overlay ower page pages paral parallel pastry peer podc practical prefix priciples principles probabilistic proc proceedings prop pugh queriable raghavan randomized range recovery references resilient rounds routing rowstron saroiu scalable scale scheideler science scribe search second service sets shah siam sigcomm simple skip skipnet skipwebs small soda spaa spielman stoc stoica structures submission symp symphony symposium systems table technical technologies testing theimer theory time tolerant transactions trees twenty under usenix wide wieder with wolman workshop world worlds zatloukal zhao
http://doi.acm.org/10.1145/1109557.1109675	117	An Improved Approximation Algorithm for Combinatorial Auctions with Submodular Bidders	acknowledgements adwords alexander algorithm algorithmica algorithms allocations alon amin amit analysis andelman annual appear applications applied approx approximating approximation aranyak arie auctions available bachem balance bartal baruch based benny bidders bipartite blumrosen boaz bounds bruce budget buffer chaitanya chandra chekuri chin chrobak clearer comb combinatorial comments commerce communication competitive complement complexity computational computing conference constraints convexity costs cover coverage daniel danny decreasing demand discrete discussions dobzinski does duplicates economic efficiency efficient electronic evangelos feige fleischer focs formulations francis free frequency from fujishige full functions fung generalized george graphs grotschel group help helpful herv holland hoppe http huji ilya improved inapproximability interesting iterative iwata jawor jciech jobs journal karp kesselman khot korte kumar laurence lavi lehmann liad like line lipton lisa location lotker lower management mansour manuscript many marek marginal mario markakis matching mathematical mathematics matias maxim maximizing maximum mehta michael minimizing model moments moulin nemhauser nisan noam noga north online optimal overflow pages paper partial particular patt polynomial power preliminary press prices private problem proc proceedings programming proof properties queries quickest random randomization references requirements results richard saberi satoru schapira scheduling schieber schrijver scott segal segev seventh sgall shahar shahard shamir sharing shenker showing soda space springer stacs stanley state stoc strategyproof strongly studies subadditive subhash submodular submodularity supporting sviridenko swamy swat switches symp symposium szegedy szlo tamir tardos thank theorem theory thirty threshold throughput tichy time timesharing transshipment tree umesh unifying unit upper uriel utilities utility values vazirani version versus vijay weighted welfare where wine with wolsey working would yair yishay york yossi
http://doi.acm.org/10.1145/1109557.1109583	25	Morphing Orthogonal Planar Graph Drawings	adjustment algorithm algorithms american amsterdam angles annual applications applied approximation area aronov atallah barequet behaved bend between biedl branke bridgeman cairns canadian cccg class close combinatorial compatible complexes comput computation computational computer computers computing conference controllable costa cycles darsa deformations devise difference dimensional directions discrete drawing drawings dynamic eades ecne edge edges editor editors efficient eiglsperger elsevier embeddings erten fekete first floater foundations free friedrich geometric geometry getting gomes gotsman graph graphical graphics graphs grid guaranteed guibas handbook have holland houle image implemented injectively interactive intermediate interpolation intersection jorge journal junger kaufmann klau kobourov lang lapaugh layout lecture leipert lengths linear liotta lubiw maintaining matching math mathematical mathematics mental methods metrics mfcs misue models monthly morgan morgana morph morphing morphs motion mutzel north notes objects open orthogonal orthogonality pages parallel piecewise pitta planar planarity plane polygon polygonal polygons polyhedra presented preserving press problem proc publishers reconfigurations rectilinear references remains rudiger sack satisfying sciecne science seen seidel sense series shapes sharir siam signifiant simeone simple slices small souvaine spriggs springer submitted such sugiyama surazhsky symposium tamassia that their theory this thomassen tilings together tors transactions trees triangulations underst urrutia velho vertices vijayan visual visually vlsi wagner warping well whether while wigderson without
http://doi.acm.org/10.1145/1109557.1109602	44	Design of Data Structures for Mergeable Trees	able acar achieve acknow actually adjacent adjusting agarwal algorithm algorithms allowed also alstrup always amortized analysis ancestors another applications appropriate arbitrary arcs argument arxiv assume balanced basic beat because become becomes believe belong below bent between biased binary blelloch block boas boolean both bottom bound bounded bounds brodal brown case cases cell center change child cole combine combines common comp completely complexity computational computer computing conjecture connectivity consider consisting constant counting created current dashed data defined definition deletemin deletions demaine dept descendent described design devising diameter dichromatic dictioa dietz different direction disc discrete does down during dynamic dynamizing each easily edelsbrunner efficient element elements elevation emde endix ensure entering erik ever every execute exists explains explicitly exponential extreme fast fastest fields find finding finger first following forest former foundations framwork frederickson fredman from fully function furthermore future gabow gain geometry given good guibas handle happens harel harer harper hashing have heap heaps herbert higher history holm however http implementation implemented implicitly including independence information insert insertion insertions interesting into involved isolated issue iterated journal kaas kaplan keep known label labels lagogiannis leaf least ledgement leeuwen length lengths less letters levels lichtenberg line linear link linking list lists logarithmic longest lower lowest machine maintain maintaining makes makris manifold manuscript mapped matching mathematical measures median mehlhorn meldable merge mergeable merges meth mihai minimum mishra models modify more moving must naries nearest necessary need needs network next node nodes note number offline only open operation operations optimal order ordered ordinary original other over pages parallelization parent part partition partitioned path paths perfect performed performing philadelphia pointer pointers polygon polynomial posing position potential powerful predecessor preliminary preprocessing preserving press priority probe problem proc processing proof ptra queries question queue queues raman rams rank rather recall references remain remains removal removals removed replacement report represent representing require restricted retrieved rooted saks schieber schmidt science sciences search section sedgewick self sense sequence sequences several shafrir sharing shortest should shows siam siegel simple simplicity simplification size sizes sleator small smaller solid solve sorted sorting space spanning special specifically splay square standard start starting static step structure structures subtree such support symp system systems tables taken tarjan technical than thank that their theory there these they third this thorup three thus time topmost total tree trees triangulating tsakalides tsakalidis tsichlas turn unchanged undefined union universe unpublished unrelated until update upper using utrecht valid values variants version vertex vertices vishkin vittes wang weighted werneck when whenever where whether which will with within words work worst would zijlstra
http://doi.acm.org/10.1145/1109557.1109652	94	On the Number of Crossing-Free Matchings, (Cycles, and Partitions)	acad acknowledgment aichholzer ajtai algorithms almostconvex amer andreas annals annual appl applications becker belgique borgelt brass cambridge canad circuit clustering codes collection comb combinat combinatorial combinatorica combinatorics comments comput computation computational computer computing conf conference constructions correcting counting cross crossing crossingfree crossings cutting cycle cycles database deineko demaine deneen denny discrete draft drawing drawings drawn dumitrescu eatcs edelsbrunner edemaine edge encoding enumerative ermanent ermutation errera error ersurface etter etween europ every formula free fuchs garc generation geom geometric geometry grantson graphs hackl hamiltonian have hayward helpful hoffmann holland http huemer hurtado inner international isfies january journal krasser kriegel lecture levcop library lower macwilliams math mathematical maximum mber mccab mesh minimum monographs moser motivated motzkin must newb nonassociative north notes numb oint oints okamoto olygon olygonizations olygons onderance optimal order oulos ound ounds oyleas pach partitions planar plane points poly polygonization polygonizations prep press princeton probab problem problems proc products ratios razen reading rectilinear references relations research results rhyme rote salesman santos satu schemes science seidel sets several shute siam simple sloane smith sohler springer stanley straight studies subgraphs symp szemer tejel thank then theorem theoretical theory thesis traveling triangles triangulation triangulations university verlag version vogtenhub weight with woeginger workshop york
http://doi.acm.org/10.1145/1109557.1109668	110	Deterministic boundary recognition and topology extraction for large sensor networks	algorithms algosensors allow analysis anchor angle appl applied approach approximation aspnes assumptions balakrishnan barri based boundary breu bruck buschmann bypassing canadian capkun combinatorial communications comp complex complexity computational computer computing conf conference connectivitybased convex coordinates correct currently dasd dealing dell demaine described design deterministic dialm direction disk distributed distribution doherty duce estimation ewusstsein extending fang faster fekete first fischer flowers fraigniaud framework free geom geometric geometry ghaoui globecom goldenb graph guaranteed guibas guiding hamdi hard have hicss holes hubaux ideas ieee industrial infocom information integrated jiang kaufmann kirkpatrick koordinatenfreies kuhn langendoen large lecture lehmann ller local locality localization locating location lokationsb makes mathematics mobihoc mobile moscibroda narayanan neighb network networking networks nition notes obviously ology oratory organization orhood osition ositioning oundary page pages paper papers peleg pfisterer philadelphia pister pomc press price priyantha probabilistic proc proceedings properties rabaey ramanathan ranges recog recognition references relatively results robust routing savarese scheme science seen self sensitive sensor shawn simpler simulating simulation society springer step stronger structure structures such sundaram swarm symposium systems tech technical technology teller theory this towards tracking transmission unit unstable usenix verlag very virtual volume wattenhofer wireless with working yang york
http://doi.acm.org/10.1145/1109557.1109586	28	Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding	aaron adaptive adler algorithms allowed already angelos annual applies approach approaches appropriate approximate arbitrarily argue argument assignments assume assumed asymmetric averaging balakrishnan balazinska because been bell bicriterion binary bits bose both bound bounds cambridge cannot censorship chakrabarti channel channels cheng chosen chou circumventing claim clearly client clients code codes coding coleman colloquium communication communications complexity compression computational computer computing concatenated concluding condition conditioning conference consider constant constraint construction constructions consumption consuumption conventional convolutional correlated correlation cover data decoder dedicated dense dependent design desired discrete distributed distribution done doubles each effros elements encodings energy enough entire entropy establishes event expectation expected factor faith feamster feeney fich finally finish finishes finishing first focs focus foundations frias from garcia georghiades ghazizadeh ghodsi girod globecom good harfst have heights hence hidden holanda hotlink huffman hypothesis ieee improved increases indeed independently induction infocom information infranet inputs inspired interface international intl investigating iranica issue ixth jcsy john joint journal july karger know krizanc kushilevitz kusuma laber lance langerman large layers ldpc least lecting lemma less letters lggg light liveris lower magazine maggs markov master mathematical medard method micah microsensor miltersen minimum mitran model morin most multiclient multiple multiterminal must narayanan nearest needs neighbour network networks nilsson nisan noiseless nonuniformity nonuniformly note number obtain optimal other otherwise paragraph paral partitioning petrovic practical pradhan predecessor press previous probability probably probe problem proc processing proof protocol protocols prove proves ramchandran random randomised rate reaching receives reducing redundancy references regev region related rounds saberi safra sample samuel scenario schonberg science sciences scientia searching section security sends sensor sent serial server sett setting shannon show siam side signal simulate simultaneously singleclient sirocco slepian slepianwolf small soda some source sources special stankovic structural structures sufficiently surveil symp symposium system systems technical than that then theorem theory there thesis this thomas three thus ting topics toronto total trans turbo university usenix using verify want watkinson when which wigderson wiley wireless with without wolf xiong zhao zhong zixiang
http://doi.acm.org/10.1145/1109557.1109650	92	Subgraph characterization of Red/Blue-Split Graph and Konig Egerv´ry Graphs a	akad among anna annals appear aspects basis baton bicritical bourjolly budapest center characterization chudnovsky colored combinatorial combinatorica combinatorics complexity computational computations computer computing conf conjecture courbes covered coverings cuts decompositions deming dept discrete disjoint dual ebene efficient egervary eigenschaft eine equals erties eugene extension faigle finite fizikai flowers foldes fractional fuchs fund gauches gavril geometry grap graph graphok graphs hammer hoffmann homotopic hungarian independence information integrality israel jean jeno journal karp kiado knig kombinatorius komplexe konig korach kuratowski lajdonsagairol lapok letters louisiana lousiana lovasz many marie matching matchings matematikai math mathematics matrices matrixok miai miller minors number numbers optimal optimization other packing partition paths peis perfect planar plenum plummer problem probleme problems proc processing prop pulleyblank reducibility reducible references report roberston robertson rouge schrijver scientific series sets seymour solvable southeastern split springer stable state sterboul strong submitted technical thatcher theorem theory thesis thomas topologie transversal trees uber univ verlag wagner waterloo which william york
http://doi.acm.org/10.1145/1109557.1109688	130	Entropy based Nearest Neighbor Search in High Dimensions	ability acmsiam addison after again agarwal algorithm algorithms also american amount analysis annu appl applied appropriate approximate approxitry argument around arrangements arya ashley automatic available based better bits boro bounds brown butter calculation cality case cation ceedings cell centrated cessing chapter chervonenkis choose ciety clas clearly close color column comfurnas comput computation computational compute computer computing conditioned conference consider conso constant content convergence cover curse danny database databases datar deerwester denote density dept deriving deviation devroye diagrams dictionary dimenputing dimension dimensional discrete discrimination distance distribn distribu distributed distribution distributions dobkin dolev dumais each edition editors efficient either embeddings endix enough entries equal equations euclidean even events examined except expansive expect factor fagin fast february finding flickner follows foundations fraction frechet frequencies from function fuzzy geomeman geometry given goodman gorkani hafner handbo handbook harari harshman hart hash hashing have high holland http huang hypern hyperplanes iccv ieee image immorlica indeed indexing indyk information instance israel itsional jacob jayram jection jections joseph journal kanal khot kingdom kleinberg krishnaiah kumar kushilevitz landauer large latent least linear linial lipton locality london look lower main manipulation mantic many match mate mathematical matousek mean meiser memory methsympos metrics michael million mirrokni monographs most motwani mount multidimensification multidimensional multimedia near nearest neighbor neighborho neighbors netanyahu niblack nitin norma north note observe obtained only optimal ostrovsky oting over pages parametric parnas partial pattern peled pentland petkovic photoai picard piotr planes point points posium practice presented preserving press principles prob probab probabilities probability probe probform problems proc proceedings product providence qbic queries query quired rabani raghavan random randomly reading really references related relative removing reon replacement reproblems require required results retrieval rijsbergen rourke rows salton same sasson sawhney scaled scheme science sclaroff search searching section sensitive separate separates seput show siam silver since sionality sium size small solving space spaces special spie stable stanford statistical statistics steele stoc storage such symp sympo sympos symposium system systems table talk term text thaper that their then theories theory thick this thprobability tiny tion total towards trans translations trieval under unique united univ uted vapnik variable variables vector vectors vempala very video vision volume voronoi wagner well wesley when where which will with workshop worths yanker yuval zolotarev
http://doi.acm.org/10.1145/1109557.1109589	31	Testing Triangle-Freeness in General Graphs	academy algorithmica algorithms alon also arithmetic arithmetical assumption available average behrend being between bipartiteness bolyai both bound carrying cayley characterization chebyshev clique combinatorica combinatorics combinators communication computing constant contain containing convexity corollary counting degree dense depend derive detected diameter directed discrete disjoint dmax does each easily eated edge efficient ematics encer enough erty estimate etween every exactly expanders expected fact falls family fischer five follows form free freeness from general goldreich graph graphs green http ieee implies imply improved induced inequality information integers interscience into janson jcss journal kaufman keszthely krivelev krivelevich large latter least lemma lower luczak math mathenough maximum most must national numb number observe obviously oints ontains optimization orlitsky ound ounded ounds over pair pairs pairwise parnas performing possible possin probability proc proceedings progression proof prop prove quantities queries ramsey random rather ratio recall references relatively required roichman rucinski ruzsa salem sample sciences selected series sets shallnshow shapira should siam since size small soda spanned spans structures subgraphs such sufficiently sumset systems szegedy szemer take taking terms test testable testing that then theory this three thus tight transactions triangle triangles triple triples ueries unfortunately uniform uniformly union using variable vertex vertices where which wiley will with york
http://doi.acm.org/10.1145/1109557.1109629	71	Leontief Economies Encode Nonzero Sum Two-Player Games	about aggregation algorithm algorithms american amman annals appear approx approximating april argument arrow association auction auctionbased author available behavior bimatrix bounded brouwer case center certain chapter cobb codenotti colell commerce communication community competitive complexity computation computational computer computing conf conitzer considerations contributions control correlated debreu demand deng department devanur diego discussion douglas dual eaves econom econometrica economic economics economies economy edited editors efficient eigenvector eisenberg electronic elsevier ence engineering equilbrium equilibria equilibrium excess exchange existence fairness finding finite first fixed focs freedom from frontiers fsttcs full function functions gale games garg gilboa gjerstad green gross handbook hoeffding holland homothetic icalp identical ijcai imitation implications inefficient inequalities information issue jain journal kakutani kapoor kelly kendrick kibernetica kuhn langville large leads leontief letters line linear lipton mahdian management mantel manuscript march markakis market markets mathematical maulloo mccune mckelvey mclennan mehta methods meyer microeconomic microsoft minnesota model multiple multiplicity nash nearly nenakov networks north note operational other oxford pages papadimitriou paper parity path pemmara penumatcha playing point polynomial prefer press prices pricing primak primal probability proc processing programming proofs proportional pure quantitative quart random rate rationality references research results retrieval review revisions rust saberi safra sandholm science sciences seattle separable shadow siam simple society soda solution solutions some stability stanford statistical stefankovic stoc strategies studies study substitutability sums survey symmetric system theorem theory time tourky trade tucker type university using utilities utility uzawa varadara variables vazirani version volume walras webpage whinston with working zemel
http://doi.acm.org/10.1145/1109557.1109599	41	Rank/Select Operations on Large Alphabets: a Tool for Text Indexing	acmsiam algorithms alphab ankur annual applica applications april arrays august automata case categorization chile clark compressed computer computing constant data department dept dictionaries discrete efficient eled encoding entropy ermutations erto eyond ferragina fmindex foundations friendly giovanni gonzalo graphs grossi gupta helsinki high ieee indexable indexes information international into jacobson jeev jeffrey journal kinen kunihiko languages letters logarithmic loquium luccio manzini meng multisets munro muthukrishnan navarro optimal order ortunistic ossible ounds pages pagh paolo proceedings processing programming queries query raman range rasmus redundancy references representation representations retrieval sadakane science scott search secondary sequences siam space squeezing srinivasa static storage string structures structuring succinct succinctness suffix symposium technical text theorem theta time tions tradeoffs trees univ university veli venkatesh vitter willard with worst
http://doi.acm.org/10.1145/1109557.1109621	63	Cache-Oblivious String Dictionaries	abello above academic acknowledgements aggarwal algorithm algorithms alphabets alphanumeric analogues anonymous appear applications arge array arxiv assumption automata bender bentley binary biology block bound brodal cache cacheobliviousness calculated cambridge case character coded colton combinatorics communications complexity compressed computation computational computer computing conclusion conference construction data dealing demaine demonstrated dictionary discrete distributed distributing distribution edges editors entries euler expanded external externalmemory fagerberg farach fast ferragina finally find foundations frandsen fredkin frigo full geometric giraffe given graph grossi gudmund gusfield handbook have height hierarchies hierarchy holland hutchinson iacono ieee improved inen information input institute international jacob journal june kluwer knuth langerman languages large layout leaves lecture leiserson limits linear logb loquium maheshwari massachusetts massive master matching mehta memory meyer minkley model morris morrison munro muthukrishnan name nonrelevant notes number oblivious open optimal output pages pardalos path patricia pattern performing practical pratt prefix presentation press priority problem problems proc programming prokop provides pruned publishers queries query queue ramachandran referee references related relevancy remains report repository required resende retrieve sahni sanders scandinavian school science search searches searching sedgewick sept sequences sets shortest siam sibeyn simple size small sorting spatial springer string strings structure structures suffix suggesting suggestions summer surveys sweeping switching symposium tall technical technology thanks then theory thesis this tour tree trees trie tries unbounded university using verlag vitter volume wanted weiner where whether which with work workshop worst
http://doi.acm.org/10.1145/1109557.1109604	46	Sampling Binary Contingency Tables with a Greedy Start	absorbed accelerating acminitial activities aldous algorithm algorithms algosium alones althe american analysis annealing annealmath annual appear appl application approximate approximately approximation approximations arrays assoc assume available besag bezakova bhatnagar binary binatorial biometrika bipartite boosted boot bounding bounds breakup carlo carus case chain chains chen clifford cobb combinatorial combinatorics comdescribed community comp complete computation compute computing computo construct contingency cooper count counting dealt decrease decreasing degree desired diaconis different discrete distance distribu distribution dmax doubles dyer each ecological ecology edge edges entries estimate estimation fast final first fixed flow flows from gale gangolli gatech generalized generate generating generation geometric give given gorithms graph graphs greedy greenhill hence high holmes however http ideal improved including increased inieigenvalues initially intermediate jerrum kannan lemma level margins marked markov markovchain math mathematical mathematics matrix median methods mitted mixing monograph monte monthly multicommodity need negative networks next nmdmax notice number only order outputs outputting pacific patterns perform permanent phase polynomial present previous previously probab probability proceedings process quantity quential random rates rect rectangular reduction references regular remain resulting results rithm running ryser same sample samples sampling sanderson scientific scientist second sections seof sequence siam significance simple simulated sinclair soda spend springer stage stages start starting stat states stationary statistical stefankovi steps stoc strapping strategies stroock structures subgraph subgraphs symporunning symposium tables takes temperature temperatures testing tests tetali than that theor theorem theory therefore this thus tial time times tion tournaments uniform valiant values variation various vazirani vempala verlag vertices vigoda weight weights were when which whose wiley will with within york
http://doi.acm.org/10.1145/1109557.1109655	97	Counting without sampling. New algorithms for enumeration problems using statistical physics	achlioptas acknowledge acknowledgement after again aldous algorithm algorithms already american annals annealing annual appear apper applications applied approach approximate approximately approximating approximation arbitrary arxiv assignment association assumptions bandyopadhyay before begin below berkeley berlin bethe beyond bezakova biroli bivariate bodies bollobas bolyai boston brightwell bsvv cancelation carlo case cavity cayley chain coloring colorings colourings combinatorial combinatorics combined common communication company complexity computation compute computer computing cond conditional connected consider constant constraint contemporary convergence conversations convex core countcolor counting criteria dark degree department details dfhv dimacs dimitris discrete distance distributional distributions dobrushin does dyer dynamics editors endogeny entries enumeration equal equation equations every exact exhaustive exists exponential expression fields find fixed flow follows formula foundations four frieze from fruitful function functional gamarnik georgii gibbs girth given glass gnsa gnsb goldberg graph graphs gratefully gruyter hard have hayes help high hochbaum holds http ieee improved independent information input integration interest janson jerrum john jonasson journal kannan kelly kesten ksat large lattice lattices least lecture lemma lemmas letters limit limiting linear local logistic lovasz lowing luby luczak machinery main marc markov martin matchings math mathematical mathematics matrix maximum measures method mezard model models monte morphisms mossel negative neighbor neighbors nestril node nodes notes nowicki objective obtained omit omitted ompute operation optimization otherwise output pair pairs parameter parisi partition performed permanent phase phys physics physiscs point polynomial preparation prescribing probabilistic probability problem problems proc proceedings processes proof proposition publishing random randomly rbmm recursive references regular regularity relate related relates relation rely report results rewire rewiring richardo rivoire rucinski same sampling satisfaction science scientific second series sets several siam similar simonovits simulated sinclair singapore size society sons space sparse spinglass springer statist statistical statistics steele stefankovic step steps stoc stochastic structures studies submitted such sufficiently survey swirscsz swirszcz symposium system systems talagrand technical temperature that theorem theoretical theory there they threshold time tool transition transitions tree trees type underlying uniform uniqueness using valiant variables vazirani vempala verlag very vigoda virasoro volume walks walter warren weak weight weitz where wiley winkler with world zard zecchina zero
http://doi.acm.org/10.1145/1109557.1109689	131	A Dynamic Data Structure for 3-d Convex Hulls and 2-d Nearest Neighbor Queries	actually agarwal algorithmica algorithmics algorithms also amortized appl applications bentley berg berlin biconnectivity binary bound bounds brodal chan chazelle clarkson cliffs closest clustering comput computational configurations connectivity constraints construction constructions convex data decomposable decremental delaunay described detection deterministic devillers dimension dimensional dimensions discrete dobkin dynamic easy edge englewood envelopes eppstein euclidean even exceeds expected experimental extrema factors fast finally fixed found four fully functions geom geometric geometry germany half halfspace halfspaces hall heidelberg here hierarchical higher holm hull ieee improved incremental inform intersection introduction jacob kirkpatrick kreveld layers leeuwen level levels lichtenberg linear logarithmic lower made maintenance matouek measures mehlhorn meiser method minimum much mulmuley multi near online operation operations optima optimization orsa other overmars pages pairs planar plane point points polyhedral polylogarithmic polytopes prentice preparata problems proc programming queries ramos random randomized range references replaced reporting results sampling saxe schwarzkopf searching seem seidel semi sets shamos sharir shooting shor siam smorodinsky some soon space spanning springer static still structures suri sympos tardos teillaud that their theoret theory thorup three through time trans transformation tree trees triangulation verlag violated violations whether width with worse yield york
http://doi.acm.org/10.1145/1109557.1109671	113	Trees and Markov convexity	above absorbing accruing acmm acmsiam agarwal algorithmic algorithms alon ammn amount anal annual anupam apart appear applications approximating approximation arora assumimg avner ball banach below between binary bound bounded bourgain branch chains charikar chawla children claim combinatorica complete comput compute computer computing conclude contain convex decides define deletion descent directed discrete distance distortion down drift each embedding embeddings encounters estimate euclidean expander feige finite flows form forms forward foundations fractals fraction from funct geom geometric geometries geometry graph graphs grothendieck gupta hajiaghayi half height help improved inequality interpretation into israel james klmn krauthgamer least leaves left length linial lipschitz london magen makarychev maps markov math matousek measured mendel method metrical metrics michael minimum naor nathan need norm note observe occurs order pages partitionings philadelphia point points probability problems proceedings proof quadratic rabinovich racke random reaching really recall references riesz right robert root saks sanjeev satish science segments separators siam since sketch some spaces sparsest starting states steadily steiner steps stoc suffices sums superreflexivity symposium taken that then theory this time times transforms tree trees true twelfth umesh uncut uniformly upon vancouver vazirani verify vertex walk walks washington weight which will with
http://doi.acm.org/10.1145/1109557.1109664	106	Analyzing BitTorrent and Related Peer-to-Peer Networks	about above accounts active actually addison algorithms although always among analysis annual applications approximately approximation arise arrive assumptions attempting avoid bailey bandwidth bandwidths become bharamb biersack bittorrent bittorrentsp blocks bollob bound cambridge capacity case cases client clients coding combinatorica complete computational computing conditions content corollary correct could crowd currently cused data database deconstructing degree delft demers dense derstanding diameter dification disbittorrent dissecting distribute distributed distribution download downloaded downloading each eases ecification edition ediwe effect either electrical engineering epidemic erice expect fairly feasible felb file finally find first five flash fortat found further future garbacki garc garcia general geometry gkantsidis graph graphs greene guaranteed guarantees hafner hall hamra hand hauser have herley hold however http implies improve improved incorporate independent individual infectious inferior infocom interested interesting into introduction intuitively irish issues izal keller large larson last least left leon lifetime like maintenance make mance mathematical maximum measurement measurements microsoft might minimum model modeling months more most motwani mulmuley must neighbors netherlands network networks nice notably often open order oses other padmanabhan pages parameters particularly passive peer perforbounds perform performance perhaps policies policy possibility possible pouwelse practical prentice press primarily principles probability problematic problems proceedings processes protocol raghavan random randomized rare references regular relatively remain replicated required research resolve result results rodriguez routing scale second secondly seems service settings several share sharing shenker show showed shtml sigcomm simple sips sixth slashdot smaller some sometimes srikant stated states still strained streamed streaming study sturgis support swinehart switched symposium system technical technology terms terry that theory these they this through tight tightest time tion topeer torrent tracks traffic under universal university unmost upload upper urvoy uses variety varying veciana vega very weak well wesley what where which wiki will with work would yang
http://doi.acm.org/10.1145/1109557.1109558	0	Confronting Hardness Using a Hybrid Approach	absence abstract acknowledgements advances advantage advisor after algebraic algorithm algorithmica algorithms algothe allows alon already also although among analogous andrew annals anonymous appear appearing application applications applied appreciated approach approx approximable approximate approximating approximation april arora assignment assignments assuming author authors baker bandwidth because before bellman below benefited better beyond blum bodlaender boosting bounds brown cannot carnegie case cases caterpillars cersimplest certain chen choosing chose chosen claim classes clique coding color comments comp complete completeness completes complexity comput computable computational computer computers computing conclusion confronting conhave consider consideration constant constraint constraints constructions containment contains coping correlated counterintuitive counterpart cover csps cycles dantsin decomp definite degenerate degening department depends depth descent design deterministic diametrically diassignment different directions discr disjoint donnell downey ductive dyksen dynamic each ected edding efforts eilems either electronic elimto elusive encouragement enthusiasm equation equations eracy ermanent even every exact exactly example examples excluded existence existing expandis expert exploits exponential exponentially extended extending extension eyond fact fast faster feige fellows find finding finite first focus focused follow follows formulas found foundations from full future gavrilovich general gestions goemans gomes gonzalez good graph graphs greatly gritter group gupta hallett hard hardness have held helpful hence here hierarchy highly hirsch hitter homeomorphism huang hybrid hybrids ideas igpl impagliazzo impos improved inapproximability inated incompatible independent independently individuals industrial input insatisfied instance instances intel interesting intriguing jerrum jour juedes just kanj karger karp khot kind kindler konev konjevod krauthgamer large larly lead least length leyton likely limits linear lingas local logic longest loquium lower lund manuel many mathematics maximal maximum maxk mcfadden means measured mellon mendel metaphor method methods metrics might mildly minimum minor minors more mossel most motwani multiproblems naor nishimura note notion npcomplete nudelman observe obtain offer offs olylogarithmic olynomial onential only optimal ordering ortfolios ositions other otherwise ounded ounds over pages pairs paper parallel parameterized partial particularly past path paths paturi picks planar plotkin polynomial practice preliminary presence prime principles probability probhowever problem problems produces programming promising proof prove proved proven pure quick ramkumar random ravi recognizing rection reductions references relatively relaxations remaining replaced resisted result results returns revealed reviewers rice rithm sahni salesman satisfaction satisfiability satisfied satisfy satisfying saxe scandinavian science sciences scientific scott search second seemingly selection selector selects selman semi semidefinite sense separator sequencing sequential sets several shallow shoham showing siam sible side sights simi sipser size smal small smith society solely solution solve solved some sometimes sorkin sparse special springer stad stepped straightforward straints strategies strong strongly structures studied study subgraph such sudan sufficiently sugodd surprisingly symp syst systems szegedy tain talwar task technical tests thank thanks that them then theor theorem theory ther there therefore they think this threshold thus time trade travelling treatment trees trivially uniformly unify university uriel using variable variables vassilevska vazirani vempala venkatesh verification version vertex very wahlen well were what which whose width williams williamson with work workshop worst yielding yuster zane zwick
http://doi.acm.org/10.1145/1109557.1109686	128	Correlation Clustering with a Fixed Numb er of Clusters	above acknowledgments admits agarwal aggregating agreements ailon algorithm algorithms alon annual anonymous approx approximability approximated approximation arbitrary arora bansal berger best biol blum bound cannot center charikar chawla clauses cluster clustering colorable coloring common comp computer computing connection correlation csps deleted deletion demaine description determine determining directed disagreements donnell edges ellipsoids emanuel error even expression extending factor fernandez fiat finite focs follows form forms foundations from gene general given goldreich goldwasser graph graphs grothendieck guarantee guruswami hard hardness have hazan ieee immorlica inapproximability inconsistent indyk inequality information instance intersection issue journal july karpinski kenyon khot kindler latter learning light likely machine makarychev make mathematical maxagree maximization maximizing metric mindisagree minimizing minimum modification mossel naor negative nemirovski newman note number observation october only optimal optimum other over pages partial patterns pointing polynomial positive possible problem problems proc proceedings programming programs proof property ptas quadratic qualitative rabani randomized ranking recent reduces reduction referee references result results roos safra satisfiable scheme schemes science sciences semidefinite shamir sharan simple soda spaces special stoc sublinear swamy symposium system tell terlaky testing thank that theorem theory there thus time tsur uncut variable vega weighted when wirth with within workshop yakhini zero
http://doi.acm.org/10.1145/1109557.1109564	6	Directed Metrics and Directed Graph Partitioning Problems	acknowledgements adjacent agarwal algorithm algorithmic algorithms along also amer amit annual anupam appendix applications applied apply approxi approximate approximating approximation arora assume average balanced below between bipartite bound bounded bourgain capacities cape case ceed chapter charikar chawla cheriyan class classes clearly clique closed combinatorica complete complexity computational computer computing concludes condition cone cones conjecture consequence consider constant convex corresponding counterpart define defined definition deletion demands demi denote department depending depends dimension dimensions ding directed discrete distance distort distortab distortion done dual each easily easy eddability edding eddings edge edges edition editors embed embeddability embeddable embedding embedleast embeds entries equal equals estimate etween euclidean every exactly exists expander factor families feasible feige finally finite fixed flow flows focs following follows forbidden form foundations frankl from function games gapa general generalized generated geometric geometry given goodman graduate graph graphs gupta handb harald hardness have hence here hilb holds howard identity implies improved indeed indyk inequality inner instance institute integrality interpret intersections interval into introduce isfy israel istit jective jiaghayi joseph karloff khot kogan konstantin large least lectures leighton lemma less like likewise lines linial lipschitz london makarychev mapping mated math mathematics matousek maxflow maximal maximum metric metrics minimization minimum minx mohammad moses most multicommodity multicut multicuts naor negative notion number observe obviously only optimum original osium other over pages paolo partitioning pick pointing points portant positive presented press problem problems proc product proof prove quantity quasimetric rabani rabinovich random ratio ready references regular relations relaxation remark rend represent representation result results rodl rourke same scale science section semimetric semimetrics semix sets shimon showed shown siam similar similarly since size soda solution some space spaces sparsest springer ssuming state statement stoc subgraph sufficiently summations suppose symp tech technical texts than thank that then theorem theorems theory there therefore this trans trieste uncut undirected uniform unique univ uriel value values variables vazirani vectors verlag vertices vishnoi vitolo weak weakly weight weighted weizmann where which will with would yields yury yuval
http://doi.acm.org/10.1145/1109557.1109580	22	Tightening Non-Simple Paths and Cycles on Surfaces	acknowledgments acmsiam acta actually algebraic algorithm algorithms also annu appear appl application applications argument arose authors bespamyatnikh cabello cambridge canonical class classical colin combinatorial comments complexity comput computational compute computer computing contractibility contractible cornell courbes cover curve curves cutting cycles cylindric decomposition decompositions dehn detection determining discrete discussions disk does drawing dynamic each efficiently efrat embedded eppstein epstein erickson european fast faster finding flachen francis frederickson fundamental generators geom given graph graphs greedy group guha hatcher helpful hence henzinger hershberger homology homotopic homotopy html http increase independent initiated into invitation isotopies iteration iterations jeff klein kobourov kurven lazarus lecture length like loops lubiw manifolds mantler math mathematica michel minimum mohar much network nonseparating notably notes null number optimal optimally orientable pants papers paris part path paths peled planar plane pocchiola polygonal press previous proc proof raccourcissement references reif results running schema schipper several shortening shortest shows siam snoeyink springer stillwell subramanian surface surfaces sympos syst system technique testing textes thank that theorem theory these thesis this time topologically topology transformation transforming triangulated undirected university vegter verdiere verlag verroust visit when where whittlesey with work would writing york zweiseitigen
http://doi.acm.org/10.1145/1109557.1109636	78	Maintaining Significant Stream Statistics over Sliding Windows	abello accounting aggregate algorithm algorithms annual answers appeared approximate arasu architectures aspects automata babcock bags based bases callaghan charikar chen cikm colton computation computer computing conf conference cormode counts data database datar demaine dhamdhere difference dimacs directions discrete distributed distributions dynamically editors elements embeddings engineering estan estimating estimation european external farach finding focs fong foundations frequency frequent from functions generators gibbons gilbert gionis guha head histograms icalp icde ieee improving indyk information international internet items karp know kotidis koudas languages large ledge lelism level limited linked list lopez loquium maintaining management manjhi manku massive mathematics matias maximum measurement medians memory most motwani moving munro muthukrishnan number olston ortiz otherwise over packet page pages papadimitriou paper paral pass pods principles proc programming pseudorandom qian quantiles queries query rarity reaches recently references remove same sampling science series sets shenker shim shkapenyuk short siam sigcomm sigmod similarity simple size sliding soda spaa space stable stacs statistics stoc strauss stream streaming streams structures summaries summary surfing symp symposium synopsis systems tail theoretical theory thus time tirthapura tods tracking traffic transactions union varghese variance very vitter vldb wavelets what window windows with zhou
http://doi.acm.org/10.1145/1109557.1109570	12	Computing sequential equilibria for two-player games	aaron about acad acalpulco acknowledgements action alex algorithm algorithms also amman andrew annals annual anonymous applications approximating archduke arguably aritificial armed artificial assessments august aumann available avoids azhar basic behavior behaviour bernhard between billings bimatrix bjerre bromille burch carnegie chapter charnes checked christos classes combinatorica comments communication complementarity complete complexity computable computation computational computer computers computing concept conference conitzer consistent contributions curtis daimi damme dantzig daphne darse david davidson degeneracy demon discussion discussions doklady duane duke easily easy eaves econometrica economic economics econweb edition editor editors efficient efficiently ehavior elon elsevier elzen endence equal equilibria equilibrium equlibria erative erfect erfectness eric erson etween even examples experimental extensive fast federal figure finding finite focs forces form found foundations francois freeman from full further gambit game games general generalized gets gilpin given graph handbook harsanyi hart heads helpful hence himself holdem holland holte however html http ieee ijcai imitation immediately indep index inequality information insensible insisting intel intelligence interesting international intriguing intuitively jean johnson joint jonathan journal july kakutani karmarkar kendrick khachiyan kohlb koller kreps kuhn large later latter lead leads leave lemmata ligence like limit linear local louis make makes making management manuscript many mathematical mathematics matrix mckelvey mclennan megiddo mellon memory mertens method mexico mihalis miltersen minimizing mistake more morgenstern move munich must myerson nash neil neumann next nimrod noncoop normal normalform north octob oints oker olynomial onentially only onse open opponent optimal optimality orden output pacific pages palfrey papadimitriou paper particularly payoff perfect perfection person personal perturbed peter pfeffer philip pittsburgh player playing point points polynomial possibility possible preflop press previous princeton probability problem problems proc proceedings programming programs prop proper quantal quasiperfection question randomized recal recent reduction reexamination references refinements reif reinhard relation relative rensen reny representation representations resp restraints results reviewer richard risky robert romanovskii rule ruled rust safe same sandholm savani scale schaeffer schauenb science sciences search selby selection selten sense sequential simplex simplified simply size society soda software solutions some soviet spaces springer stability stable stengel steps strategic strategies strategy studies symposium system szafron taken taking talman tamu technical terence thank that theodore theoretic theoretical theory this thus time tools tourky trees troels tucker tuomas turo turocy under unique university value verlag version versions very vincent volume webpage which will wilson with wolfe workshop worry would yannakakis zero
http://doi.acm.org/10.1145/1109557.1109579	21	Robust Shape Fitting via Peeling and Grating Coresets	acknowledgments agarwal algorithm algorithmic algorithms also andconquer annu annuli annulus anonymous appl application approximate approximating approximation archive arge aronov arrangements assoc authors barequet basch both bounding cambridge chan chazelle cole combinatorial comments comput computational computer computing conclude constraints constructions core coreset coresets cutting cylinder cylindrical data depth diameter dimensional dimensions discrete discussions divide duality efficient efficiently enclosing erickson even exact exploited extent faster fitting fixed found franciosa gatech geom geometric geometry georgia goodman guibas halfspace helpful hershberger http hulls hyperplanes ieee improved incremental independent inst internat iterations iterative jects journal kernel kinetic large lated lectures levels like line linear mach maintaining many math matouek measures methods minimum mobile models moving number obvious open optimization outliers pach paper peled point points poreddy power practical practice preparata presented problems proc programming prove questions range referees references related research running sciences search searching sets shape shapes sharir shells siam simple size slab smallest springer stream structures surprisingly sympos system tech thank that this three through time useful using varadara varadarajan various veach violations vios vitter volume wang well welzl width with work would yusu
http://doi.acm.org/10.1145/1109557.1109622	64	Cache-Oblivious Dynamic Programming 	acknowledgement acta addison aggarwal akhter algorithm algorithms analyses analysis annual applications architectures austin ayele based beckstrom bellman benjamin bevan beyond biology blakesley blanchette blumofe bouffard brinkley brooks browne brudno bruen cache cacheoblivious cambridge cariaga cftr chakravarti chapman cherng chowdhury class common communications comp comparative complexity computation computational computations compute computed computer computing conf conference consistent context core cormen cubic cutler dags data decomp decomposed decomposition dekker dept design diagonal dietrich distributed dynamic each ebble ecies eeding efficient elnitski endency entries erformance erimental esulting evaluation fast floyd forward foundations free freeman frigo from galil game general genomic gepn giancarlo given granite graph green greenb guan guerra gupta haghihi hall hansen haussler hirschb hong horizontal horowitz huang idol ieee improved informatica input international into introduction involves jacm jasekaran jersey joerg jong journal june karlins karolchik kent kleinb kumar kung ladner language largest laric larmore lawrence least legaspi leiserson less linear linearspace locality london longest maduro making marcel margulies masiello maskeri massachusetts mastrian matrices matrix maximal mccloskey mcdowell memory mike miller molecular more multi multiplication nature oblivious oolean optimizing osition osoegawa ostolico output pages paral parallel park partial path pearson penner pivoting plus portnoy practical prasad prasanna press princeton problem problems proc program programming programs prokop providing publishing ramachandran randall rangan reading recognition recurrences redblue reference references regions related riesen rivest runs sahni schwartz science sciences sequence sequences shared shortest siam siep simple smit sniedovich sorting sotlved space stantrip starting stein stencil sternb strip strips strump subsequence subsequences summers supercomputing symp symposium system systems tardos targeted tech technique texas than thank that theorem theoretical theory this thomas time tiongson toledo touchman tran transactions transform triangular tsurgeon university upper using valiant vitter vogt walker warshall waterman weight wesely wetherby wheat width wiggins with womble york young zhang zhao
http://doi.acm.org/10.1145/1109557.1109679	121	The Complexity of Matrix Completion	acknowledgments addison akademie algebra algebraic algorithm algorithms also analysis annual anonymous applica applications applied approach appropriate arithmetic assign assigned authors berdan berlin best bijection block bondy bounds braz brualdi budach bureau buss cambridge chou chromatic circuit classes classification closure code codes coding color coloring colors combinatorial combinatorica combinatorics comments communicated complete completeness completion complexity computation computational computer connect consider constant construction coppersmith dard data david decomposition deltamatroid derandomizing design desirable determinantal determinants deterministic discrete discriminants distinct dynamic each easy edge edgechromatic editor editors edmonds effros egner elements elimination elsevier encyclopedia euler even example existing fields fifteenth find finding floudas flow focs following follows found foundations frandsen friedland from fundamentals furthermore gaussian geelen geometry gorithms graph gurvits hard hardness harvey helpful hopcroft however identity ieee impagliazzo implies information institute interesting international inverse inversion irreducibility isit iwata jaggi jain journal june kabanets karger kazuo klee kluwer known koetter kopparty laurent lecture lehman lemma length less like linear loci lovasz lower many master matching matchings mathematical mathematics matrices matrix matroid matroids maximum means mfcs missing mixed mucha mulmuley multicast multiplication murota murty national network networking notes numb number observe optimization over overhead pages pardalos parity perspective polynomial press previously problem problems proceedings progressions proof proving random rank receives references refined related relates representatives require research result results reviewers ring room routers sanders sankowski satisfiability science sciences series shallit short show siam simplified since singular sixteenth size skew small soda some spaces springer standards stoc storage structure suggestions suppose swastik symbolic symmetric symposium system systems tests thank that their then theoretic theory thesis they this time tions tolhuizen tovey transactions transitive transmission ullman university unused used valiant vazirani verlag vertex vertices volume volumes waterloo well wesley whose winograd with woodruff would yields
http://doi.acm.org/10.1145/1109557.1109624	66	Tight Approximation Algorithms for Maximum General Assignment Problems	ageev agents algorithm algorithms analysis andelman annual appear application applications applied approx approximating approximation approximations arbitrary assignment auctions baev benefits beniaminy budget carr chekuri combinatorial communication competitive complexity computational computer computing constrained constraint constraints constructing content convergence cover covering data dimensional discrete distributed distribution distributions domatic easy equilibria equilibrium extension facility fast faster feige fisher fixed flow focs foundations fractional function functions games garg generalized goemans gomes guarantee halldorsson hard hardness ieee improved international jain jansen johnson journal khanna knapsack konemann kortsarz kumar latin letters level linear local location mahdian mansour market mathematical mathematics maximizing maximum meta method mirrokni mixed mobihoc mobile multicommodity multiple nash nemhauser networking networks note number nutov operations optimization other packing pages pandit papadimitriou parallel partial performance person personal petrank pipage placement plotkin points problem problems proceedings profit profits program programming proven ptas rajaraman random randomized rectangle references regis research rounding routing salavatipour satisfiability schaffer schemes science sciences search selfish sequential sets shachnai sharing shmoys siam simple simpler sink societies soda solve solving square srinivasan stiner stoc structure study subject submodular sviridenko swamy swat symp symposium system tamir tardos that theory thesis thottan threshold traffic trees unpublished vector vempala vetta williamson with without wolsey workshop yannakakis young yuster zhang
http://doi.acm.org/10.1145/1109557.1109678	120	Single-Minded Unlimited Supply Pricing on Sparse Instances	about above abstract achieve acknowledgments agents aggarwal algorithm algorithmic algorithms appear appeared approach approximate approximately approximation archer argue argued assigned assignment assuming auctions ausiello balcan bartal before bernholt berthold better between blum bouhtou bound bounding bridges briest callaghan cannot cases claim clearly closely combinatorial compatible competitive completeness complexity computers computes conflicts crescenzi cross denote derandomized design determine deterministic digital discussion does edges efficient envy expect expectation extended factor feder fiat finally finishing following follows free freeman from gambosi garey general generalized gives glynn goldberg gonen good goods grigoriev guide guruswami hartline have hoesel hold holds icalp incentive incorporating independently individual inequality initial initially insightful instance interesting into intractability item johnson kann karlin kempe kenyon koltun kraaij krysta lead lehmann lemmas like lose lower made marchettispaccamela maximizing mcsherry mechanism most motwani multi must near nearlinear network niques nisan nonparametric objective observe obtain obtainable open operations optimal opts ours papadimitriou parameter presented price prices pricing problem proc product prof profit profits profs proof proposing protasi randomization randomized ratio ratios recently references related relation relies report research result results returned revelation river ronen rusmevichientong same sausp separately sets shoham since single size soda solution some spieksma springer ssusp stoc submitted subset such susp talwar tardos tark tech technical technique than thank that theory there this thorsten though thus time times topic truth truthful uetz under unit upper uses using utilitarian value view vocking wads waoa were with would wright yields
http://doi.acm.org/10.1145/1109557.1109665	107	Oblivious Network Design	above achieve acknowledgments adaptivity after aggregation algorithm algorithmic algorithms algosituations allowed along also another appear applications approach approximability approximating approximation approximations arbitrary attention average bandwidth been being benefit benefits best better boosted both bound bounded bounds building bulk buyat case challenging changing choosing combinatorial communication competitive comput comratio concave conference congestion considered considering constant constantfactor constructing contained convex corresponds cost costdistance costs course cover daniel decomposition definition degree demands design designing different dimension direct directed direction discrete discussed discussions distortion domain doubling dynamic each edge edges effective embeddings even exist exploiting factor final finally find finding flow flows focs follows formulation fractals from fruitful function functions fundamental further game general generally geometries global going golovin graph graphs hajiaghayi hardness have hierarchical however icalp imase improve improved improves incomplete independently installation integrality interest interesting intra ipco kleinberg knapsack knowledge large latency leighton lemma like limited line linear link links load loads locality lower making math metric metrics minimize minimizing mission model more most multicommodity natural network networks norms oblivious obtained obvious ones online open optical optimal optimization original ornothing other paper parallel particular petitive placement planar polynomial polynomials practical preconditioners probabilistic problem problems proc procrastination proof proved quadratic ratio ratios rected references rent rentor research restrictive result results rithm robert robust routing same sampling scenario scenarios scheme schemes selfish setting sharing show siam sigcomm simple simpler simultaneous single sink situtations small soda source spaa spaces square steiner stoc stochastic subadditive such support task than thank that theor theorem theoretic there these this through tight till time total tradeoffs traffic tree trees uncertain underlying understanding undi undirected uniform universal upper using version waxman when where whether which with would
http://doi.acm.org/10.1145/1109557.1109634	76	Simpler algorithm for estimating frequency moments of data streams	alan algorithm algorithms alon amit annual appear applications approach approximating approximation approximations aravind automata bounded bounds chakrabarti chandan charikar chen chernoff combinations communication complexity computation computational computer computing conference coppersmith data database david deepanjan discrete disjointness distance distributions embeddings estimating farachcolton fifteenth finding foundations frequency frequent fsttcs ganguly generators hoeffding hybrid ieee improved independence indyk information international items jayram jeanette join journal july kesh kevin khot kumar languages limited linear loquium lower manuscript mario martin matias model moments moses multi near nisan noam noga optimal over pages party piotr practical proceedings programming pseudo random randomized ravi references saha saks schmidt science sciences siam siegel sivakumar sizes software space srinivasan stable statistics stoc stream streams subhash sumit symposium systems szegedy technique technology theoretical theory tracking update using with woodruff workshop xiaodong yossef yossi
http://doi.acm.org/10.1145/1109557.1109598	40	Scheduling Unit Tasks to Minimize the Number of Idle Periods: A Polynomial Time Algorithm for Offline Dynamic Power Management	acknowledgments adaptation algorithm algorithmic algorithms anna annual applied approximation author baptiste bounded chapter chretienne company complete computation conference consider discrete during equal gupta identical introduced irani jesh jobs june karlin kirk length like machine machines management mathematics maxim models more online pages parallel philippe planing planning point polynomial polynomially power press problem problems proceeding proceedings pruhs publishing references sandeep sandy savings scheduling seems shukla siam siena single soda solved straightforward strongly sviridenko symposium thank this time unlikely volume wait workshop would york
http://doi.acm.org/10.1145/1109557.1109667	109	Scalable Leader Election	advances adversary against agreement ajtai algorithm algorithms alon annual aspects authentication based below best biased bits bolyai boolean boppana bounded bounds bracha byzantine called coalitions coin collective combinatorica combinatorics communicated computation computer computers computing conclusion conjecture constant control cooper course degree discrete doing dolev down dwork each editor efficient election elects ensures entire expected exponents fast fault feige finally first fischer flipping flood focs following foundations fowler fraction full functions gabriel game games generals good handle handled have hebrew heuristics however identified ieee immune immunity imperfect including increases influence information involving jagoplan janos jason jerusalem journal kahn kalai know knowledge large layer leader linear linial load logarithms logn lower lynch manuscript math mathematics message messages micali michael model models monitoring most must naor narayanan nathan needed network networks node noncryptographic note number oblivious only open optimal ostrovsky other over pages paper peleg perfect perfectinformation pippenger play polylogarithmic potential potentially practical presented press probability problem problems proceedings processed processes processor processors processsors protocol protocols prove random randomized randomness randomoness reduce references relatively remain report reports requests required requires research results robust rounds russell saks sampled samplers sampling scalable scale science second selection send sends sense sent sets several siam silvio simple simplified since single sixth sized some still stoc strong structures sublinear symposium syposium technical that their then theoretic theory these this times tolerance tree twenty university upfal uriel used variables vazirani version weaker when which with without zuckerman
http://doi.acm.org/10.1145/1109557.1109593	35	On The Chromatic Number of Some Geometric Hypergraphs	abbildung acknowledgements agarwal akad algorithms alon already also always amidst annu annual another appel applications apply aronov assignment author aviv axis balls better boris bound bounded boxes cambridge cannot cardinality cellular cfcol cfcoloring chromatic clarkson collision color colorable coloring colorings colors combinatorial comments communication complexity comput computational computer concerning conflict congruent conjecture consisting could crete davenport degree description detailed developed directly discharging discrdete discrete discs discussed discussions disks diso dissertation drawing easily element enough even every extended festschrift fewer fiat focs follows found free frequency geom geometric geometry goodmanpol graph haken halfplanes have heidelberg helpful here however hyperedge hyperedges hypergraph ieee illinois imply improvement induced intervals janos jected jordan journal kaplan kedem koebe konformen kontaktprobleme lack least leipzig lemma lems levy like livne logd lotker manuscript math mathematics matouek maximum methods might minimum moss motion needed networks nonmonochromatic notion number obstacles omit online onto open over pach paper parallel particular peled personal phys planar plane pointing points polygonal preliminary press probcc problem problems proc quadratic radoii rados random rectangles reducibility references regions relates relation relax requirements sampling sariel schinzel school science seen sequences shallow sharir shor siam simple since smorodinsky soda springer studied such suffice sympos symposium tardos thank thanks that their therefore this translational unfortunately uniform union university verlag version wagner welzl what when wishes wiss with would york
http://doi.acm.org/10.1145/1109557.1109648	90	On the diameter of Eulerian orientations of graphs	aaai abss acmsiam aldous algebra algorithms almost amer annals annealing applications approximate arora artificial arxiv assoc asymp asymptotic babai beals bhkls bound bounds cayley chain chains codes combinatorial combinatorics communications complexity comput computer computing conf coordinating cube databases diameter discrete distributions dixon elements engineering equations erdos europ even expansion finding finite focs generating generation generator goldreich graphs group groups growth hard hardness hayes helfgott hetyei http ieee independence inequality information intel intelligence jerrum kantor korf kornhauser laci lattices lecture length ligence linear local lubotsky markov math method miller minimum motion near notes optima optimal pattern pebble people permutation permutations polynomial practice preliminary press probability proc products random references representation rosa rubik sabidussi science sciences sequence sequences seress short siam simulated simulation society solutions spirakis stern stoc subgroup sure sweedyk symmetric symmetrical symposium systems szegedy theoretical theory transitive turgeon uchicago uniform using version vertex
http://doi.acm.org/10.1145/1109557.1109642	84	Ordering by weighted number of wins gives a good ranking for weighted tournaments	acad according acyclic aggregating aggregation ailon algorithm algorithmic algorithmica algorithms alon always among annual appear applications approximating approximation approximations arora arrangement assignment available bang bartholdi being berger biased borda candidates case cases charikar choice circuits classes clustering clusterings combinatorial combinatorica complexity computations computer computing conference conitzer consider construct construction cornel dense deterministic diaconis difficult dinur directed disarray discrete dwork election equality even except exits fagin feedback finally first focs follows footrule foundations fractionally frieze from graham graph graphs hassin histoire holds http identity ieee importance inconsistent indegrees induction information international jensen journal kaplan karp kumar last lections lemma letters mahdian manuscript math maximum measure methods minimum moire multicuts naor negative newman next optimization ordering orie packing pages papadimitriou path perspective polynomial problem problems procedure proceedings processing proof rank ranking rankings reducibility references report rest rounding royal royale rubinstein safra same schemes schieber science sciences scrutin second semicomplete series sets seymour shor show siam similarities simple sivakumar slater social society soda sorts spearman statement statistical stoc subgraph such sudan swapped symposium system tech tell term that their then theory there thomassen three tournaments tovey trick trivially unpublished using verified vertices voting welfare when where which while wide with world yannakakis zuylen
http://doi.acm.org/10.1145/1109557.1109600	42	O(log log n)-Competitive Dynamic Binary Search Trees	adam avrim blum chawla comments dynamic feedback gary kalai miller optimality references search shuchi static thanks
http://doi.acm.org/10.1145/1109557.1109559	1	A New Approach to Proving Upper Bounds for MAX-2-SAT	aachen accurate acknowledgments after algorithm algorithms allow also alto analysis annual anonymous appear application applications applied apply approach april asirelli assumption automata automated bansal based believe better bipartite bound bounds case cases chen chosen clauses comments complete complexity complicated computer computing concepts conference consider constraint constraints course cubic cuts databases decision deductive department design different dimacs discrete does doing done during easy edward eighth eliminate eliminated equal estimate estimating estimation exact exactly example exceed except expected exponential fedin focs fomin formula foundations from further gallaire generation give gramm graph graphs hard have help helpful hirsch icalp ideas implications improve improved improvement informal information input integer integrity interesting international isaac journal june kanj kneis know kulikov kullmann languages largest latin least letters like lncs logic loquium luckhardt made martelli mathematics maximum maxsat measure measures methods minker more most nauchnykh needs neighbors nicolas niedermeier november number only optimal other pages palo paper pathwidth paturi point poljak pomi positive possible precise preprint presented probability problem problems proceedings processing programming proof proofs prove proved proven pudl raman randomly ravikumar referees references report required richter rossmanith rules running rwth saks santis satisfaction satisfiability science seems select seminarov series several showing simplification simplified split splits splitting springer srinivasa stronger subgraphs such supervisor surveys symposium taut technical testing thank that them theoretic theoretical theory this thus time tuza university upper uses variable variables various verlag volume weight when where which will williams with work workshop worst would writing zane zapiski
http://doi.acm.org/10.1145/1109557.1109566	8	Small Hop-diameter Sparse Spanners for Doubling Metrics	abraham adaptive algorithm algorithmica algorithms almost alon alth analysis andrew annual answering anupam appl applications arya assoc assouad barun belding berlin bernard bhagwat blackbox body bounded bruce bypassing callahan chan chandra charles chazelle clarkson compact complete completes complexity comput computational computer computers computing constructing construction corson dahlia dans david deborah decomposition demand destination dimensional dimensions discrete distance distortion distributed dobkin doubling dsdv dynamic efficiency eighth elizabeth embedding embeddings euclidean euclidian fast fields finding foundations fractals france free gautam geom geometries geometry giri good graph graphs growth gupta heinonen hierarchical highly hubert icalp ieee infocom ingo internat ittai james jeffrey joseph journal karger kosara krauthgamer kunal lanky lectures line linear lipschitziens mach maggs malkhi manor mappings math matthias mendel metric metrics michiel mobile mount multidimensional narasimhan navigating nearest neighbor neighbors ners nets networks optimal pages park patrice paul peled peleg perkins plongements podc point points potential pravin preprocessing preserving proceedings product proof proximity queries range references report restricted results robert routing royer ruhl salowe sariel schaffer schieber science scott search sequenced sets short shuheng siam sigcomm simple smid soares space spaces spane spanner spanners sparse sparseness springer stoc sunil symposium talwar tarjan tech their theory thin time tradeoff tree union universitext vaidya vector verlag vincent weighted which wireless with wmcsa york zhou
http://doi.acm.org/10.1145/1109557.1109577	19	Combination Can Be Hard: Approximability of the Unique Coverage Problem	about absolute abstract abusch access acknowledgments acmsiam agents algorithm algorithms allen allow also annual appears application approach approximate approximately approximating approximation arbitrary architecture artificial aspects assignment asymmetric auctions august author authors automata avat average back bansal base bbis because bell between bipartite boston bound bounded breathing broadcast broadcasting budgeted bundle buyer cambridge case cases cell center centralized certain characterization choices claim claimed classes colloq combinatorial commerce communication communications complexity computer computing concerning conditional conference consequence consider constant constants constrained constraints contexts cost cover coverage covering cubic currently curves cycles david deadline decentralized degree deployability derandomize described desires despite determinism deterministic difficult directed discrete discussions disjoint distinguish distributed domatic dual easy economic economics edge efficient electronic elements empirical energy envy envyfree equal equilibria equilibrium error evaluation exact expansion expectation expected exponential extended extensive facility factor faster february fixing following foundations free from fruitful future general generalize given graph graphs greedy gross guruswami hard hardness hartline helpful hypothesis ieee improved improvements inapproximability independent information initial instance integer integrality intelligence interesting international italian item items jain jason journal just kamal karger knowledge known kowa kunal labs languages lans large larger latter lead least lecture lemma letters local location logarithmic lower magder major making manuscript market maximum mechanism mechanisms merely method minded minimization minimized modified multi national natural near necessary needed networks nhard nikhil node notes number observation obtain optimal optimization other otherwise packing parameter paths placement plausible point polylogarithmic polynomial poster press price prices pricing primal principles probability problem problems proc processing product profit profitmaximizing profits programming proof prove publishing pure quantity radio randomization randomized ratio real reduction references refutation refute related relations restricted result results revelation rewritten robustness round rounding routing same satisfaction satisfiability scandinavian schemes science sciences section selection seller semidefinite september sets setting show siam sigact sigcomm sigops simplification single size solution some standard station steiner strikes substitutes such sufficiently supply suppose suspect sympos system talwar telephone test than thank thanks that thei then theorem theoretical theory there third this though threshold thus time times topology total transactions tree truth truthful type undirected unique university unlimited unwin uses using valuations value vehicle venkatesan vertex walrasian wave weighted when where which whose will windows wireless with within without work workshop world would
http://doi.acm.org/10.1145/1109557.1109609	51	Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem	above abstract according acknowledgements acmpasses added addition additional after again agarwal algo algocontradiction algonote algorithm algorithmica algorithmics algorithms along also alter among analogs analysis angle anle annual anonymous apalgorithm appear appendix appl applied approximate approximating approximation arcsin argue argument arguments around assume authors away axes axis badoiu ball balls based basic basically basis before better between both bound boundary bounded boyd bridge broken called cambridge camthe careful case ceedings center centered centers certain chooses chosen claim claims clarkson closed closest clustering collection combinatorial combir comments common complement completely comput computation computational compute computing conclude concludes conditions consider constant constraints contained containing contains continuously contradiction contradicts contribution convex convexity core coreset coresets corner correct corresponding could couple cover covering covers cube current cylinder cylinders data decreased decreasing define defined definition denote denoted described detailed details dethe deutsch different dimension dimensional dimensionat dimensions discrete discussions distance distances dius does doesnot done each eighteenth either eleventh ellipsoids empty enclosed enclosing encounter endpoints entirely equals essentially european every exact example existence exists expected exploring extended extent fact factor fall falls figure final finally find finding finds finite first fitting flat focus follow following follows fore form formulate found four fourteenth fourth framework freely from full function further furthermore furthest gemeinschaftlichen general generality generic geom geometric geometry given gives goes greater half halt hand happen hard have helly helpful here high hold however hyperplane iddle idea ideas ievery igure implied implies include included includes including increase increasing indeed independent industrial indyk inequality infinitesimally inner inside interior intersect intersecting intersection intersects interval intervals involved iscylinder iteration jahresbericht john know known konvexer korper kumar least lemma lemmas length less lexicographic lies like line linear linearly lines little locality london loss main math mathematics matousek matrices maxi maximal mazumdar means measures median mengen method minimal minimize minimum minith missing mitchell monotonically monotonicity more most move moves must natorial need next ngle nodes nondecreasing normal notation note notice noticed notion number observe omitted once only onto ontradiction optimization order origin orthogonal other otherwise outliers outlined output outside pages pairs paper parallel passes peled perpendicular philadelphia plane plied point points poly polytope portion pproximate precision present press previous problem problems proceed proceedings procopiuc programming projecting projection projections projective proof proofs prothe prove proving punkten raan radius randomized reader reasons recall referee references reflection regarding regularity remaining remark represented respect respectively resulting return returning returns rithms roughly roximate rubin running same satisfy scalar section segment segments sets several shape sharir should show shown shows siam side sides significantly similar similarly simple since size sketch slab small smaller society soda solution solved solving some sons space spanned speaking specified springer square standard start state stated statistical stays step steps still stoc strictly study subexponential subset subsets such suffices sufficient suppose sure symposium take technical terminate test than thank that their them then theo theorem theory there therefore therethus these thirtysixth thiryif this through throughout thus ties tihe time total towards trends triangle true tuple tuples type uber unit university upcoming used useful uses using value vandenberghe varadarajan variables various vector vectors verein verified verify verlag version vertex very viewed violation volume wang welzl what when where whic which whose width wiley will with without would xiao yildirim york zero
http://doi.acm.org/10.1145/1109557.1109569	11	Approximating Unique Games	acknowledgments added agarwal algorithm algorithms alon also annual appear approx approximate approximating approximation april arbitrary assoc attached berlin better bound bringing case charikar chawla combinatorial comment completes complexity comput computational computer computing conclusions conference conjecture consistent constraints cover csps cycle deletion dhamdhere directed directions discussions donnell during eccc edge edges embeddability equation equations extend fakcharoenphol feige fifth final focs foundations future games gave general geometric give giving goemans grotschel guarantee hard hardness helpful ieee improved inapproximability indeed integrality interscience into isust july kedar khot kindler krauthgamer kumar lecture like linear lovasz mach makarychev maximum method metrics might minuniqgame moses mossel most multicut negative note notes notice open optimal optimization other paper possibly power press probabilistic probability problem problems proceedings programming proof prover rabani references regev reichman relaxation remains report results round rounding satisfiability schrijver science seen semidefinite seventh showed shuchi sivakumar sparsest spencer springer springerverlag symposium systems talwar tech that theory there think thirty this thus tight tree trevisan type uncut uniqgame unique using variable variables vazirani verlag vertex very violated vishnoi which wiley williamson with within would york
http://doi.acm.org/10.1145/1109557.1109591	33	Testing graph isomorphism	according adaptive advance against algorithm algorithms alon also analysis another appear appeared applications applies appropriate approximation arangement arora assignment association back batu between binary bipartite blum both bound bounds branching certain chapter characterization chosen clear clearly close combinatorica complexity computation computer computing concluding conditioning conditions connection considered constant cornell correcting currently decisions dense depends deviation difficulty distance distribution distributions edition efficient error estimation european event every exponential fact finally first fischer focs form fortnow frieze from functions general give given goes goldreich goldwasser graph graphs handbook have here however identity ieee impossible increased indeed independence inequality input interesting interscience isomorphism issue jasekaran jnal john journal kaplan kluwer krivelevich kumar large learning least lemma length letin like little lower luby many martingale mathematical measure method monotone more natural necessarily need newman next number numerical order over packing pairs pardalos pass polynomial polynomials power preliminary presented press primer probabilistic probability problem problems proc procedure proceedings program programming programs properties property prove proves quasi quasipolynomial queried queries question random randomized read reduce references regarding reif remaining remarks replace report require restricted results robust rolim rounding rubinfeld running same satisfies satisfy science sciences seems selftesting setting sgall shapira show siam sided situation small some sons spencer step stoc strings structures sudan system szegedy technical test testable tested testers testing that theorems theoretical there three tighter time towards trevisan tutorial twice unable unified uniform uninformed university used variables variation version versus vertex view well whether which while white width wiley will with would york
http://doi.acm.org/10.1145/1109557.1109582	24	Simultaneous Diagonal Flips in Plane Triangulations	above adding adjacent algorithms ando anna arxiv atsuhiro bemerkung biedl binary bitrary bose bound bounds caseanalysis chem close closed colour combin comput connected construct constructed convex corresponding czyzowicz daniel david degree demaine deutsch diagonal discrete distance distributions does each edge edges efficient erik estimating every face faces ferran figure flip flippable flipping flips follows four from full generalization geom graphs hamiltonian hassler have hideo http hurtado improve inform inside internal jber jean jorge jurek katsuhiro kiyoshi klaus komuro least lett lower lubiw marc matching math minimum mori morin nakamigawa nakamoto negami neil number obtained obvious open outer pallo paper paul petersen phys plane polygon problem process proof prosenjit pseudo references results robertson robin rotation rutia ryuichi sanders sect seiya seven seymour shows simul size specified sphere straightforward surfaces survey takahiro taneous that theorem theoret theory therese thomas tomoki transformations trees triangle triangulation triangulations tween univ upper verein vertex vierfarbenproblem wagner watanabe which whitney with without wood yokohama zhicheng
http://doi.acm.org/10.1145/1109557.1109681	123	Matrix Approximation and Pro jective Clustering via Volume Sampling	achlioptas agarwal aggarwal algebra algorithm algorithms alon alto analysis annual applications approximate approximating approximation approximations artin automatic bdoiu bounds carlo center clusa clustering complexity computation computational computations computer computing concept contemp core coresets data decentralized deterministic digital dimensional dimensions discrete drineas eccc edition efficient effros erations europ exponent facilities fast feigenbaum finding foundations frequency frieze gehrke geometric geometry golub goreinov graph graphs guha gunopulos hall henzinger high histograms hopkins http icalp ieee improve indyk information iterative jagopalan john jones journal kannan karpinski kemp kenyon koudas kumar large letters line linear loan locating lower maloney manuscript march mathematics matias matouek matrices matrix maximalvolume mazumdar mcgregor mcsherry means median megiddo might mining model moments monte murali mustafa nets note orary osium ostrovsky palo papers park pass peled plane pods polynomial possible prentice press problems proceedings procopiuc projected projective ptas rabani rademacher raghavan rank references research running sabharwal sampling sariel schemes schulman science sciences semi sets shim sigmod simple soda space spectral streaming streams subspace suggests suri survey symp system systems szegedy tamir technical tering that their theory third time tyrtyshnikov uiuc university using valis varada varadara vega vempala vinay wang with wolf yale yaleu yosseff zhang
http://doi.acm.org/10.1145/1109557.1109656	98	Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems	activity algorithm algorithmica algorithms allow analysis annealing annual appear application approximating approximation arrangements artificial association better bezakova bhatnagar binary bodies bound bounds broder bubley chains colorings combinatorial combinatorics complexity computer computing conference congestion contingency convex coupling degree density dimer dimers discrete distribution dyer each entries erratum estimating estimation exponential fewer flow focs foundations frieze from gelatt generation graph greedy hard hayes hold ideal ieee ijcai improved inequalities infer intel intermediate international jects jerrum joint journal kalai kannan kasteleyn kirkpatrick lattice lemma ligence lovasz machinery many markov markovian marry matrix mccullagh mildly mixing multicommodity needed negative number optimization ostland over pasula path perhaps permanent physica polynomial polynomialtime possible prediction preprint probability proceedings proving quadratic random randomly rapid rates references relations ritov russell samples sampling satisfy science sensors siam simple simply simulated sinclair sixteenth slack soda some start stated statistics stoc struct structures symposium tables technique than that their them theoretical theory time tracking uniform valiant vazirani vecchi vempala very vigoda volume weights whereas which with
http://doi.acm.org/10.1145/1109557.1109676	118	Revenue Maximization When Bidders Have Budgets	aaai acknowledgments aggarwal alem alpha analysis applied approaches approximation assuming asymptotically auction auctions balance behavior bidders borgs bound budget buyer buyers chayes combinatorial comments commerce commission communications comp competitive composability constrained constraints costs design development digital discussions economic economics ected efficiency efficient electronic etitive europ exactly extract federal fiat figure finally financially first function gale games generalized goldb goods hartline helpful http immorlica inverse items jason journal karlin knapsack known laffont letters like liquidity mahdian main maskin masking mcgrew mechanism mechanisms model most moulin mubc multi nisan notion obtain optimal optimization parameterized partition partitition plotkin price private privatization problem profit properties ratio references restricted revenue review roughgarden saks sealed section selling sells serge sharing shenker soda stoc strategyproof submodular table thank theorem theory thesis this three tion truthful unit using value where wireless with would wright
http://doi.acm.org/10.1145/1109557.1109632	74	Equilibria for Economies with Production: Constant-Returns Technologies and Production Planning Constraints	acknowledgements again aggregation alan algorithm algorithmic algorithms analysis anda annals appear applications applied applying approach approx approximating approximation arrow arrowdebreu auction auctionbased author barnett basil blackwell block bruno cambridge case center certain chen circumscribed class codenotti colell collecting column competitive complementary complexity computation computational computing concave consensus constraint converging conversely convex cornet daspremont debreu december demand deng devanur discussion discussions dual dualtype econometrica economic economical economics economies economy editor efficient eisenberg elements ellipsoid engineering equilbrium equilibria equilibrium excess exchange existence extended ferris finding fisher focs framework fsttcs function functions gabszewicz gale gams garg general generalized gjerstad green gross hill homothetic hurwicz icalp identical improved inscribed integer jain jective jiaghayi john journal kapoor kehoe kibernetica kibernetika kirman leontief linear mahdian management mangasarian market markets matekon mathematical mathematics mccune mcgraw method methods microeconomic minnesota model modeling models mpsge multiple multiplicity mutuel nearly nenakov newman news nonlinear once optimum overview oxford pang papadimitriou paper pari path pemmara penumatcha planning polterovich polynomial preference press price prices primak primal prize probabilities problem problems proc production program programming quasi references research results review russian rutherford saberi scale schema scheme schrijver sciences second separable several shoven siam sigact soda solution solutions solving sons spending stability statistics steiner stoc substitutibility sybsystem syntax thanks theory time tree uniqueness university utilities utility valuable varadara vazirani vector whalley whinston wiley with york
http://doi.acm.org/10.1145/1109557.1109572	14	Finding Nucleolus of Flow Game	aarts acmsiam affirmative algorithm algorithmic algorithms allocation also alternative anald analysis annual answer application applied approach aspects assignment associated astin aumann balanced bankruptcy based basis been belongs berlin between both branzei bulletin canadian capacity carried center characteristic characterization characterize cially claims cleolus clusion coalitions column combinatorial come company comparisons completeness complexity computable computation computational compute computer computers computing concept concepts conclusion conjecture conjectured constructed construction convex cooperative core cores corollary cost cover dealt define defined definition deng denote dept difficult direct directly discrete discussion dual duality economic edmonds efficient efficiently effort entails espefigure essays essential estate exact exponenuj facility faculteit faigle fair fang feature featurecolumn finding flow flowers following fore formulation francisco freeman from full function furthermore game games garey general generalized geometric given goemans granot group guide hard hardness have hebre hence hierarchical however html http huberman ibaraki independent index instance interest international intractability itriou itself jean jerusalem johnson journal kalai kern kernel kernels kind kopelowitz kuipers least lecture lemaire lemma length linear little locate location lovasz main makes malkevitch march maschler matching math mathematical mathematics maximum measure megiddo membership memorandum monthly moreover mulation nagamochi network notes nucleolus obtain obviously only operations optimal optimization optimizations other owen papadim papadimitriou paper partition paths paulusma peer person polynomial possesses powerful practia prices problem problems proceedings production program programming proof proposed proven provide raghavan rational rationality real recently recognizing references referred remarks research resolving result same schmeidler schrijver science section seen sense serve sets shapley should show shubik siam simple since size skutella solution solymosi some spanning springer springerverlag standard strongly structured study symposium systems talmud technique that their theorem theoretic theoretical theory there therefore they this tial tijs time toegepaste tool topics total tree trees tschel twente universiteit university used using vectors version very were wiskunde with work yielding ysis zemel
http://doi.acm.org/10.1145/1109557.1109568	10	On Nash Equilibria for a Network Creation Game	agents algorithms allo allocation anarchy annals annual anshelevich appear applications approx approximation bala based behavior behaviour bilateral blokhuis bounds brouwer capacitated case cation clubs coalitions codes complexity computer computing contract cooperative corbo correa cost creation czumaj dasgupta dedicata demange design diameter directed discrete distel distributed econometrica economic economics editors efficiency equi equilibria errorcorrecting fabrikant fair farms formation fotakis foundations game games geodetic geometricae goyal graduate graph graphs group gupta haller heterogeneous holland icalp ieee jackson jain johari journal kleinberg kontogiannis koutsoupias krysta libria luthra maneva mannor mathematics mavronicolas mechanisms model models moses nash nearoptimal network networks north operations pages papadimitriou parkes price primaldual principles proc proceedings proof publishing references research roughgarden routing sarangi schulz science selfish server sharing shenker siam sloane spirakis springer srinivasan stability stacs stier strategy structure survey symp tardos texts theory tight traffic tsitsiklis vazirani vocking wexler williams with wooders worse worst
http://doi.acm.org/10.1145/1109557.1109692	134	Pattern Matching with Address Errors: Rearrangement Distances	abrahamson added address algebra algorithm algorithms amir annual applications approximate approximately arad aumann bafna baker beigel berman binary biology bits block bound bounded capable cares carpara christie classes codes cole combinatorial communicated communication comp complexity computation computational compute computer computing conf conjugacy convolution convolutions correcting correction counting covering deletions dictionary difficult discrete distributed dokl dvir dynamic each editing editor efficient equality errors eurosam extension farach fast faster ferragina fischer fixed focs function furthermore galil general generalized giancarlo gottlieb grossi group groups hannenhalli hariharan herzog hirschberg however icalp identities improved incremental indexing information insertions interchanges intl journal karloff karp known labeling landau lecture letters levenshtein levy lewenstein lncs location lower lowrance manuscript matching mathematics mismatches mixing muthukrishnan myers need news notes only other overlap paradigm parameterized part partial paterson pattern patterns permutation pevzner phys player polynomial polynomials porat press probabilistic problem proc proceedings processing products properties questions ramesh recomb references related relation renaming research result results reversal reversals sahinalp schemes schwartz science second separately siam sigact simpler since sixth soda some sorting soviet sparse springer stoc string strings symmetric symposium takes text that then theoretical theory thirty thus total transpositions under using values verification vishkin vishne wagner with word zippel
http://doi.acm.org/10.1145/1109557.1109611	53	Randomized Incremental Constructions of Three-Dimensional Convex Hulls and Planar Voronoi Diagrams, and Approximate Range Counting	above according afford agarwal algo algopoints algorithm algorithmica algorithms also anal annu appl applications applied approximate approximating arise aronov arrangements assoc associated assuming berg binary biof black brute cambridge case cedure ceed challenge chan chazelle clarkson closure cohen collect combinatorial complexity comput computation computational computing conditional conditioned construct construction correctly count counting cuttings cylindrical data delaunay delb depth design diagrams dimensions disc discrepancy discrete disks disr each edelsbrunner edition efficient efficiently element elements empty epsilon equally erickson ermutations error estimation etry exactly example expectation expected fast find finding first fixed follows force framework general geom geomand geometric geometry given guibas half halfspace halfspaces haussler have heidelb heiexists hierarchis high hold houle however ieee implies incremental inserting intel interesting intersecting into introduction joint kind kinetic knuth kreveld least level levels lies likely line mach machinery main matouek mentioned method minimum moreover mulmuley murali nary nets normal number obtain oints only open optimal order orting other otherwise over overlay overmars parameters partition partitions pattern peled performance permutation permutations planar plane pling point points prefix preparation preproce press probability problem problems proc processed queries query ramos random randomized range rank reachability references related relative remark repeating report reported reporting reports requires resulting rithm same sample samples sampling schwarzkopf searching segments seidel sharir shooting shor siam simplex since size solutions some space springer static storage structure structures subset such suggested summary suppose symbolic sympos syst taining that their then theorem theory there this three thus time total toussaint trans transitive triangles unconditional university uses using value verlag vitter voronoi weights welzl where which width with within xpected
http://doi.acm.org/10.1145/1109557.1109605	47	Asymmetric Balanced Allocation with Simple Hash Functions	allo annual applications approximation arithmetic aspects asymmetry azar balanced balanco balls bins broder buchmann carter cation cations cking classes cole computer computing constant deletions dictionaries dietzfelbinger dynamic focs foundations frieze functions ganziger geburtstag gunter hash hashing heide helps hotz ieee improve independent infocom informatikfestschrift integer interna international journal karlin lecture load maggs meyer mitzenmacher multiple notes okups packed paul primes proceedings random randomization real references richa science siam sitaraman size stacs symposium techniques teubner theoretical tightly time universal upfal using variables volume wegman weidling wise with without workshop
http://doi.acm.org/10.1145/1109557.1109691	133	Many distances in planar graphs	algebraic algorithm algorithmical algorithms among appl applications approximate approximating arbitrary arikati authors available baltimore being best bounded cambridge carleton chan chapter chen chew closed compact comput computational computer computing concepts connected consider constant contractible cornell corollary correspond currently curves cutting cycle cycles decomp difficult digraphs discrete disk distance distances djidjev edded edges editors efficient ello elsevier embedded eppstein erickson euclidean exact factor fakcharoenphol fast faster find finding focs following frederickson from genus geom geometric geometry graph graphs gudmundsson handbook hatcher have henzinger homologous hopkins http interesting into johns journal klein know kowalik kurowski levcop linear lipton lncs many math miller mohar multiple narasimhan near negative nonseparating obstacles obtain ologically optimally oracles osition oulos pages pairs path paths peled planar plane preliminary press problems properties quadratic queries question reachability real recently reduces references remains result rises roughly sack school science sciences sense separating separator separators settle short shortest shown siam simple size small smid soda solved solving source space spanners spanning springer stoc stretch subramanian such surface surfaces survey syst system takes tarjan technical that theorem therefore this thomassen thorup time together topological topology trees university urrutia version vertices volume wads walk walks webpages weight weights with would zaroliagis zero zwick
http://doi.acm.org/10.1145/1109557.1109630	72	Bottleneck Links, Variable Demand, and the Tragedy of the Commons	addison affirmative agents akella algorithms allocation analysis analyze anarchy andpoptimal annual anshelevich answer appear application applications approach approximation arbitrary aspects aspnes assignment asymmetric athena atomic auctions banerjee banner beckmann behavior bertsekas bottleneck bounding braess capacitated case ccit chang chapter chau chawla civil class combinatorial combined commodity commons communcations communications company competitive computation computer computing condition conference congestion conserving cornell correa cost costs course creation czuma dafermos dasgupta december definition demands design designing discrete distributed does economic economics edition editor efficiency elastic energy engineering engineers environments equilibria equilibrium examples existence explicit fabrikant facility fair final flow flows focs foundations framework functions game games gartner goemans halldorsson halpern handbook hard hardin hochbaum hold iccn ieee illustrate including incomplete independent inefficiency inequalities inequality infocom inoculation instance instances institute integer international internet investigate ipco johari journal keshav kleinberg kluwer know koutsoupias least lecture letters leung lids like link links location logical loss luthra maneva manuscript maps mathematics maximum mcguire method methods minimizing mirrokni models moses much nagurney nash near network networking networks nonatomic noncooperative nonlinear norm norms notes nphard numerical only operations optimal optimization orda osition packet pages papadimitriou paradox paradoxon paral parallel part particular partition path peering perakis performance physics podc points positive possessing prenticehall press price primaldual principles problem problems proceedings programming prop publishing purestrategy realistic references related report research resource respectively results review road rosenthal roughgarden routing satisfy scheduling schmeidler schulz science sciences scientific second section sections selfish sends separable seshan sharing shenker show siam sigcomm simple single smith societies soda some somewhat spectrum squares stability stacs statistical stier stoc strategies studies subpath switched symmetric symposium system tardos tassiulas technical technion that then theoretical theory this through topology traffic tragedy transportation tsitsiklis uber unfortunately uniqueness university unternehmensforschung users variational verkehrsplanung vetta victims viruses volume wang wardrop wesley wexler when whether which will williamson winsten wireless with worst yale yampolskiy yang zhang
http://doi.acm.org/10.1145/1109557.1109644	86	Oblivious String Embeddings and Edit Distance Approximations	above accelerating algorithm algorithms analysis ancestors andoni approximate approximating approximation batu bound bounds cascades coin cole common compression computer computing consistent construction data december designing deterministic deza discrete discussion distance distances distortion dynamic economical edit efficient efficiently embedding embeddings ergun estimate estimates exceeds factor fast faster february finding focs foundations fourier function guarantees gupta harel ieee indyk into iteration jayram journal khot kilian krauthgamer kumar labeling locally logc lower lowest macro magen manuscript masek matching mccreight micro minimum naor nearest nikova nonembeddability normed note ostrovsky paradigm parallel parallelization parsing paterson patterns preceding produce proof provides rabani raskhod raskhodnikova references report rubinfeld running sahinalp sami schieber science sciences siam simplification soda space spaces stoc string sublinear suffix symposium system tarjan technical techniques that then theorems theory this time tossing tree umiacs unpublished upper using vishkin weakly where yossef
http://doi.acm.org/10.1145/1109557.1109646	88	Certifying Large Branch-width	algorithm algorithms appear approximating assume automata axioms because berlin bodlaender bologna bounded branch branchwidth calculate certificate checked choose claim clear clique combin combinatorial combinatowe comput conclude conjecture connectivity construct construction constructive contained contradiction contradicts conversely decide deciding decomposition deduce defined denoted describe description each either enough equivalently exists first fixed fleischer fmin following follows fujishige function functions given graph graphs having hence hlinny input iwata jacm journal kits languages larger lecture lemma linear matroid maximal minimization minimizing minors modular most notes npconp obstructions obtain only open oracle order otherwise pairs parametrized play polynomial previous princeton programming proof provide rank references result rial robertson role same satisfied satisfies schrijver seymour show since size springer still strongly subby submitted submodular submodularity subset subsets such suppose tangle tangles than that then theorem theory there therefore thesis thilikos this those three thus time tree true unique university using valid well wellcheck whether width
http://doi.acm.org/10.1145/1109557.1109680	122	Relating singular values and discrepancy of weighted directed graphs	algorithms analysis appreciation arithmetic author bilu bollob both bound butler cambridge chung cknowledgment clearly combinatorica compare constructing degree discrepancy discrete discussions ectral efficient eigenvalues expander express first focs follow follows from geometric given graham graph graphs hall hand hermitian holds horn inequalities inequality introducing introduction johnson lifts linial many math matrices matrix mean most nikiforov note prentice preprint press problem proceedings publications quasi quasirandom random references respectively result right river saddle second sequences show siam side sides similarly singular spectral stewart stimulating term terms that then theory this three times university values verify west when wilson wishes with
http://doi.acm.org/10.1145/1109557.1109608	50	Solving Random Satisfiable 3CNF Formulas in Expected Polynomial Time	above acknowledgements advantage aforementioned again algorithm algorithmic algorithms alon amer analogous analysis analyze annual another anymore appear appearances appears approach approxima approximating arguments artificial aspects assigment assignment assume assuming assumption author automata auton backtrack backtracking before beier bender bilu binomial blum both bound brevity calculated cayley certifying chernoff chromatic cking clause clauses clique closely coefficients collection colloquium colorability colorable coloring colouring comb combinatorial comp compared complexity comput computation computer computing conclude conference consists constructed containing contains cook correctly correspond counted counting coupon covered crawford crossover deciding decouple define definition deleting denote dependency describe deviated differences differently discrete discussion disjoint dyer each easily edge edges edition efficient endpoints entire european event events every example exists expectation expectations expected experimental feige finding finishes first fixed flaxman following follows formulas foundations free friedgut frieze from fully furer further gent given goal goerdt graph graphs greatly greedy gutfreund hard havan hidden holds however implement indeed independence independent induced inequality influenced info inom institute intelligence interesting international interscience intriguing introduce introducing intuition israel italian iterative iwama january john joint jority kahale kaporis kirousis knapsack koutsoupias krauthgamer krivelevich lalas languages lanka large largest last least lectors lecture lemma less letters like linear local lows main majority manuscript master math mathematical mathematics mcdiarmid method minimal minimality misleading more most much mutually namely natural negative negatively nion notes number observation observations observe occurs oghlan omit once only optim optimal optimization osition otherwise ound over papadimitriou performance planted point polynomial positive positively possible probabilistic probability problem problems proc procedure procedures process prof programming proof proofs prop properties proposition proving question random randomly readily ready references refinement rehovot removed replace replacing report research resp results right sasson satisfiability satisfiable satisfying schadlich science search second seen semirandom series sets sharp show siam similarly simpler simplifies since size skipped smal solution some sons span spanning sparse spectral spencer stamatiou standard steger step strategy strathclyde structures stupid subramanian subset such sudakov support supports symp symposium syst taking taraz technical technique techniques test than thank that their then theorem theoret theoretical theory there therefore thesis they this threshold thresholds tight time times tion tree trees truly ttcher types union university unsatisfiability uriel using vamvakari variable variables veni vertices vilenchik vote weizmann when where which while wiley wilf with world would wrong xtend yield york zito
http://doi.acm.org/10.1145/1109557.1109612	54	Vertical Ray Shooting and Computing Depth Orders for Fat Ob jects	above addison advantages after again against agarwal algebraic algorithmica algorithms always amidst anywhere appl applications apply approximate arrangement aspect assemas assume axis balanced been before below berg between binary build building canonical cascading case cation cessing chazelle collection combining communication complexity comput computational computer computing concentrate conf consider constant constructing convex covering create cross data david dependence depth described detecting direction directional discr discrete disjoint dualize duals duncan dynamic each edge edges edition efficient efrat enclosure envelope ercub erin every feiner find first foley following found fractional free from fsttcs generation geom geometric geometry given goodman goodrich graphics guarding guibas halp handbook have hedra hidden hopkins however hughes iarcs implies incorrect input inside intersect intersections intersects intervals invasive ject jected jection jections jects john katz know kreveld latter left lemma level levels lift line linear lines lncs make manner matouek models motion moving multi netherlands nielsen obstacles octrees oint olygons once order orders otherwise ourov overmars pages parallel parameter part partitioning partitions pellegrini personal placed placement plane planes planning point points polylies practice prepro preprocess press previous principles problems proc query querying range ratio realistic references related removal replace representing results right rourke same says scenes schwarzkopf searching second section segment semi separately sequences sets sharir shooting siam since size slab small soda software space springer standard stapp strepp structure structures structuring subset subsets surface symp sympos tech technique test that their then theorem theoret theory therefore these thesis this through thus time total treat tree trees triangles union university upper using utrecht valid values vary verify verifying verlag vertical vertically vertices vleugels well wesley whether which whose will with witness work would
http://doi.acm.org/10.1145/1109557.1109638	80	FPTAS for mixed-integer polynomial optimization with a fixed number of variables	acknowledges acknowledgment adonet alexander algebra algebraic algorithm algorithmic algorithms also applications approximation arxiv author authors available award barvinok bernd bisection bounded bounds cambridge chancellor coefficients combinatorics commutative complexity computation computational computed computer computers computes computing convex counting david davis degree dimension donal ectives effective electronically eprint erations etienne european feasible fellow find first fixed foundation francisco freeman from functions garey geometry gives grant gratefully guide haws hemmecke hendrik homepages http huggins humboldt ideals inapproximability inequality input inst integer integral intractability introduction iterated james jeremiah jesus johan john johnson journal klerk lattice laurent lemma lenstra little loera lowing magdeburg math mathematics matthias maximum mial michael minimization monique negative network npcompleteness number olic operations optimal optimization osium over pablo parrilo persp peter point points polyhedra polynomial polynomials polynoo polytope polytopes pommersheim press proceedings programming ptas publ rational raymond references remaining research results ruriko same satisfy science shea short similarly simplex size solution some springer stad stoc sturmfels support supported symb symp tauzer that theorem theoretical theory time toric total univ value variables varieties verlag weismantel were when with york yoshida
http://doi.acm.org/10.1145/1109557.1109672	114	An algorithmic Friedman­Pippenger theorem on tree embeddings and applications to routing (Extended Abstract) 	abstract acknowledgements aggarwal ahuja alan algebraic algorithmic algorithms alok alon amnon amotz andrew annual anonymous applications applied aravind arora aspects attention back baruch beat been benny berlin bipartite blum bohman bound bounded bruce circuits colouring combinatorica combinatorics come complexity comput computation computing constructing construction contain coppersmith corrigendum david defect degree depth developed difficulties digraphs discret discrete disjoint drawing edge efficient eigenvalue electronic embedding enough expander expanders expanding explicit extended extracting feldman flows friedman frieze from future graph graphs hall hamiltonian have haxell hope improvements indebted industrial inform international invoked isaac issues james joel karp krivelevich leighton lemma lett limited line local loebl london lower madhu maggs magnanti manuscript martin math mathematics method methods michael molloy near nearly network networks nicholas noga nonblocking optical original orlin pages papadimitriou particular partitioning path paths paul peleg penny philadelphia pippenger powerful prentice present press probabilistic proceedings process ramaswami random randomness ravindra rearrangeable reed referee referees references river routing saddle sanjeev satish scheduling schieber selection sense sets shma siam simply small society soda sources spanning springer srinivasan stoc strictly submitted sudakov sudan suggesting superconcentrator switching symposia symposium telephone testing thank that theory these they thomas trees upfal upper verlag versions very volume vornberger weak whether wide wigderson with yannakakis york zuckerman
http://doi.acm.org/10.1145/1109557.1109640	82	Generating all vertices of a polyhedron is hard	academiae acta algorithm algorithms algorothms amaldi analysis angewandte annual anonymous applications applied arrangements associated association avis backtrack balinski berlin bounds bremner bussieck certain cgta chakravarti chand characterization charnes chazelle classes combinatorial communications complexity computational computer computing concerning constraints constructive contributions convex cook coop cornell counting cycle cycles densest description detailed determining digraph dimacs dimension discrete dissertation dokl double dual dullahi dyer ecke editors efficient einfachen endent enumerable enumeration ergraphs european extreme faces facet farkas feasible finding fixed floyd francisco freeman fukuda gallai games generating geometry gleeson good graphen heidelb helpful hemisphere henderson hull hulls hungaricae identifying incidences incremental indep inequalities infeasible information introduction irrelevant ishyp ithaka johnson journal kapur karp khachiyan kuhn lawler leeds lems lenstra letters liebling linear listing lubb machinery many margot marzetta math mathematicae mathematical mathematics mathematik matrices mattheiss maximal maximum mean method methods minimally minimum motzkin network networks nphardness oints olyhedra olyhedral olyhedron olynomial olytop oolean operations optimal optimization orsa ostinfeasibility output pages papadimitriou path paths pfetsch pivoting polyhedra preparata primal proba problem problems procedures proceedings processing programming proll provan proving raiffa read referee references reine reliability remarks research results reverse review rinnooy rutgers ryan schrijver science scientiarum search seidel sensitive sets shortest siam size some soviet spanning springerverlag strongly subsystem subsystems swart symposium systems tarjan technical thank theorem theoretical theorie theory thesis third thompson thrall time trees trends trotter tucker ungleichungen university valiant vertex vertices volume warshall wiley with york