http://www.informatik.uni-trier.de/~ley/db/conf/soda/soda2004.html
SODA 2004
http://doi.acm.org/10.1145/982792.982910	96	GENERIC Q UA N T U M F O U R I E R T R A N S F O R M S	aaecc abelian acknowledgements acmsiam adalbert adapted addison advances affine alexander algebra algebraic algorithm algorithms also amer american amnon analysis annals annual applications applied approximate architectures archive authors barenco barry basis beach beals bennett berlin beth california class clausen cleve clifford codes college compact completed complexity comput computation computational computer computing conrad cooleytukey coppersmith correcting crete cristopher daniel dartmouth david diaconis diameters discrete divincenzo editor efficient elementary error extensions factoring factorization fast fifteenth finite foundation foundations fourier francisco frank frederic gabor gates general generalized graduate grants graph gratefully greece grigni group groups hales hallgren harary harmonic heraklion hersonissos hidden hospitality ieee improved induced instances institute invariant island ivanyos january jean john journal july kerber kitaev knowledge lecture leonard linear logarithms magniez margolus markus martin maslen math mathemati mathematical mathematics measurements mechanical michael michelangelo miklos milius monica moore national ninth nonabelian normal notes notices november number october order oregon over pages parallel paso permutation persi peter physical physics pierre polynomial portions portland press prime print problem problems proceedings products puschel quant quantph quantum reconstruction redondo references report representations research revew robert rockmore rotteler russell sally sampling santha schulman science sciences sean second selection separation serre shma shor siam silver simon sixth sleator smolin society solvable some spring springer stabilizer street studies subgroup suite support symmetric symposium technical texas thank their theoret theory thirteenth thirty this thomas time tracy transform transforms twenty umesh under useful using value variables vazirani verlag volume watrous weinfurter were wesley where wreath york
http://doi.acm.org/10.1145/982792.982823	24	Optimal Online Bounded Space Multidimensional Packing	acta alberto algebraic algorithm algorithmica algorithms allocation analysis andre andrew annual applied approximability approximation asymptotic bansal behaviour bins blitz bound bounded bounds brown caprara carlos case cheng chung claire coffman combinatorica comp company computer computing conclusions conjecture coordinated coppersmith correa covering csirik cube cybernetica david dimensional discrete dominant donna editor editors edward efficient electronic elsevier enumerating erasmus fast fernandez ferreira fiat flavio found foundations fourth frank frenk gabor galambos garey generalized george gerhard good graham harmonic harmony heuristics hochbaum however hypercube ieee illinois improve improved inapproximability information interesting into item janos jayme jeffrey johannes johnson jose journal karmarkar karp kenyon kohayakawa labbe lack lecture left letters liang line linear lower lueker manuscript many martine mathematics maxim memory methods michael miyazawa moment multi multidimensional narendra netherlands nikhil notes online open operacional operations packing pages paper patterns performance pesquisa possible prabhakar princeton problem problems proc proceedings processing publishers publishing question raghavan ratio rectangle references report research results richard ronald rotterdam scheduling scheme schemes science section seiden should show siam siang simple solved song space springer squares state stee steve survey sviridenko symp symposium systems szwarcfiter technical that theoretical theory there these thesis this time types ullman university unpublished upon upper urbana vega verlag vliet volume wakabayashi wenceslas what within woeginger worst yoshiharu yoshiko
http://doi.acm.org/10.1145/982792.982927	109	Invadable Self-Assembly: Combining Robustness with Efficiency	abstract acknowledgement adleman algorithmic also annual assembled assembly assume attached attaches automata based before bell binary biomolecular bits block blocks boundaries built california call cambridge cellular cheng column combinatorial communication complexity computation computer computers computing conceptually consider considering constructed construction contain corresponding counting crystals defined department design dimacs dimensional discrete discussions each east eastassembly editor empty erfield eriments espanes espans exists experiments extended figure filled first force fourth from fuelled general glue goel hence hole huang immediate institute invadable invoking journal june kemp labean lagoudakis last like local logk machine macro made making mathematical mathematics meeting mills moisset molecular most nature neglecting neumann north optimization outline output pages parallel partial pasadena pattern perform personal position possible press princeton problems proceedings program proof proving read reading recognition rectilinear references reif representing represents resolving ries rothemund rubin running satisfiability science second seeman self selfto series side sierpinski simmel simulated simulates size some south southern squares symposium system systems technical technology thank that theorem theorems theoretical theory there thesis third thirty thiry tile tiles time towards triangle trigger turb turing universal university useful uses volume wang wenzler west while will winfree with workshop would yang yurke zero
http://doi.acm.org/10.1145/982792.982797	3	The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables 	about access according accounting acuna adaptive addressable algorithm allerton almeida almost alternative annu answer application applications approximate area assignment august barrier between beyond bitvectors bloom bloomjoin blue both bound bounds broder brodnik buhrman build byers cache cacm cannot capalbo case checking chernoff choice cikm codes coding cohen combinatorica comm communication communications communities complexity compressed comput computational computer computing conditional conductors conf conference considine constant content corresponds cuena database degree delivery denote denotes designing development differential digests directions discrete disjoint distinguish distributed each efficiently element encoded enforcing engineering errors estan european expander expansion fails fair fairness families family fang feng file filter filters follows forwarding foundat fredman from furthermore garcia geographical gets given givesnus gossiping gremillion hand hash hashbased high hsiao icarus iceberg ieee imperative independent index infocom inform information informed intersect intersects isdn join jones kandlur kent kleitman knowledge komlos kubiatowicz least ledlie letters ling list location lohman loops lowable lower luby mackert management manber martin math matias matrix mcilroy measurement membership methods miltersen minimum mitzenmacher mobile molina most motwani mullin munro must network networking networks next nguyen november once only openarch optimal optimizer other over overlay parameter partition partridge password peer peery perf performance planetp previous prob probabilistic probability proc proceedings processing protocol queries queue radhakrishnan random randomness razborov references region reingold remark report revealed review rhea ross rousskov routing rutgers saha sanchez scalable search security selforganization seltzer semijoin semijoins september serban service sets sharing shin shivakumar should show siam sigcomm sigmod sigops since sipser small snoeren software space sparse spectral spel spencer spielman stoc stochastic storing strayer subfamilies such summarize summary survey symp systems szemeredi table taylor tchakountio technical ternational that then theory therefore this thus time traceback tradeoffs traffic trans transactions twoway ullman union updated using vadhan validation varghese venkatesh vldb wessels wetherall whitaker wide wigderson with without workshop worst
http://doi.acm.org/10.1145/982792.982922	106	Finding Dominators Revisited	addison additional again algorithm algorithms alstrup among ancestors annual appel applications apply applying appropriate assume balanced based belongs bender biconnected buchsbaum calculation call cambridge case cases colton common compiler compilers components compression comput compute computed computer computing conclude consider core depth dichotomous disjoint dominator dominators done either evaluate farach fast finding first fixed flow flowgraph fredman gabow graph graphs harel have hopcroft idom immediate implementation information jcss journal kaplan know label lang languages latin lauridsen least lemma lengauer letters line linear listed lowest machine make mass microtree minimum modern nearest need nontrivial note november offline order other otherwise pages parallelization parent path paths pointer press principles problem problems proceedings process processed processing program programming pxdom query range reading references related relative result revisited rogers root same satisfy schieber sciences sdom search sethi seventeenth shortest siam simpler simplification since spanning special stoc strong symposium syst system systems tarjan techniques that then theorem theory therefore this thorup time tools trans transactions tree trees ullman union university using verification vertex vertices vishkin wesley westbrook where will willard with
http://doi.acm.org/10.1145/982792.982816	18	Efficient Estimation Algorithms for Neighborhood Variance and Other Moments	academic according aggregate aggregates aggregation algorithms annual apart applications approximate architectures babcock babu better bins book callaghan case charikar closure clustering cohen company comput computing consider constants construction corresponds cube cubes data database datar decaying decreasing defined dependence derive diego different dimension dimensional dimensions distributed domain each edge edition estimate estimation exponential exponentially extension fixed folding foldings framework from functions generalizes gibbons gionis gradshteyn half higher hill included includes indyk integrals interested interesting into iobtain issues item items kaplan lengths maintaining maps mcgraw median medians mink model models motwani network next norm norms number obtain over pages panigraphy papoulis paral particular partition partitioned pods points polylogarithmic possible predicate predicates preparation press principles probability problems proc processes products query random range reachability references relevant respective ryzhik second selection series shifts siam since size sketch sliding smaller spaced spatially statistics stochastic strauss stream streaming streams subcubes subset such summaries symp symposium system systems tables that then theory these they this thus tile time tirthapura transitive uniformly used value values variables variance vectors when where widom width widths windows with would yield york zero
http://doi.acm.org/10.1145/982792.982859	54	Probabilistic Analysis of Knapsack Core Algorithms	above academic acknowledgments addition additional algorithm algorithms allocation analysis analyze applications applied apply approach arithmetic around assumed automatically average balas based beats because behavior beier best between birkhauser bits bounds cannot capital code columns combinatorial combine combines combo compete completeness comput computer computers computing concept concepts considering continue contrast copenhagen core correlated dantzig david dependencies difference differences different diku discrete domf dominance dominated dominating dyer dynamic dynamically each entry european even exact expected experimental experiments exponentially extremum fact features filter finally find finding finds firetm first fixed fractional freeman frieze from garey give gives goldberg growing guide handbook horowitz ideas immediately implementation implementations implemented implementing increases instances integer interesting interface intractability introduces items johnson journal kluwer knapsack known lagarias large linear listed lists loss lossf lueker magnitudes management marchetti martello mathematics measurements merged more most much multidimensional nemhauser notes numbers obtain obtained odlyzko only operational operations optimal optimization optimum orders other outperform over pardalos particular partition partitions pisinger plan point polynomial preceding preliminary preprocessing presented presents previous probabilistic probability problem problems proceedings programming providing publishers random reason references research result results running sahni science seconds sections seriously several shows siam significant size slightly small solution solutions solver spaccamela specified static stoc stripe structures studies study subset suggest super switch symposium table test thank that then theoretical theory there these thesis this thorough three time toth trends ullmann uniformly university uses using variable variants vocking want well which wiley with without zemel zero
http://doi.acm.org/10.1145/982792.982956	133	On the diameter of the symmetric group: polynomial bounds	aaai acad algebra algebraic algorithms almost amer appl appropriate arbitrarily argument artificial assoc assumes attained average babai bhkls bounded bounds bovey cambridge cannot cayley certain chains chebyshev comb combinatorial combinatorica combinatorics communications complexity comput computation computer computing concept conf construct could cube cycles databases degree denote deviation diam diameter discr dixon dordrecht driscoll efficient eigenvalues elements erdos europ even expect expected fact finding finite first focs furst generate generating generator generators goldreich graph graphs group groups handbuch hard have hetyei heydemann hopcropft ieee independence independent inequality info inst intel intelligence interconnection jerrum kantor kluwer knuth korf landau lehre leipzig length lett ligence linear london louis lubotsky luks manipualtion math matrices mckenzie members minimum montreal more much nato nearindependence nearly need networks notes odlyzko optimal over pair pairs pairwise pattern perm permutation permutations phys pick plan plausible polynomial polynomially power practice preceding press primzahlen probability problems proc products prove proven publ random references representation rosa rubik sabidussi science second section seems sequence sequences seress short sims slowly small society solutions some standard statistical stochastic subgroup surely symbolic symmetric symmetry symposium teubner than that then theoretical theory therefore this three through time total turan turgeon univ using value verteilung verw wahrscheinlichkeitstheorie what with words would
http://doi.acm.org/10.1145/982792.982934	115	A Characterization of Easily Testable Induced Subgraphs	academic academy algorithm algorithmic algorithms alon also amsdimacs annals annual another application applications applied approximation areas arise arithmetic aspects association asymptotic automatic behrend bermond bogdanov bollob bound bounded bulletin burlingham california called case cases characterization characterizations characterize chromatic closure clustering cnrs cographs colorability coloring column combin combinatorial combinatorica combinatorics combining complement complete complexity comput computation computational computer computing connection constant contain containing corneil cotree czuma decisions degree design diego digraphs directed discrete domains duke easily edge edition editors efficient equivalent european examination exponent extremal fischer fixed focs forbidden formed fournier frankl free freeness frieze from general geometry goldreich goldwasser graham graph graphs handbook have having hypergraph hypergraphs icalp ieee index integers inter interesting intersection jasekaran journal juntas kannan karpinski kindler kluwer known krivelevich languages large learning lefmann lehman lemma lerchs linear loque lower math mathematics matrices mckee mcmorris measure methods might monotonicity national naturally newman number obata obtained only open operations order over pardalos parnas partitions perl philadelphia pittsburgh polynomials poset possible precisely press primer probabilistic problem problems proc proceedings program progression properties property publishers queries quick ramsey random randomization randomized raskhodnikova recall recognition reducible references regarding regular regularity reif replacing representation resolve results robust rolim rothschild rubinfeld safra samorodnitsky sampling satisfiability scheduling science sciences second seems sets shapira short siam simonovits simplest since single small soda sohler solving sotteau spencer stewart stoc structural subgraph subgraphs subsection such sudan survey symp symposium szegedy szemer terms testable tester testing that theorem theorems theoretical theory there these they this three topics towards tree trevisan unclassified under undirected unified uninformed union unique vega vergnas vertex vertices which wiley with without york yuster
http://doi.acm.org/10.1145/982792.982830	30	~ Approximate Distance Oracles for Unweighted Graphs in O(n2 ) time	adjacent algorithm algorithms almost also annual appear approximate approximation arithmetic automata baswana between bound bounded bounds calculus case close cohen combining computation compute computed computer computing consider construction contributed contributes coppersmith data directed distance distributed does each earlier edges elementary elkin exact exist expectation expected fact fixed focs following follows formed foundations fredman from general given graph graphs halperin hence however icalp indeed independently integer international iterations journal koml languages lemma lemmas linear linearity loquium matrix maximum mentioned more multiplication neighbor neither note number optimal oracle pages pairs paths peleg picking presented previous principles probability proceedings processed programming progressions proof references repeat report result running sample science selected selecting shortest show siam simple since size small some spanner sparse springer state stoc storing stretch structure subgraph symbolic symposium szemer table than that theorem theory there therefore thorup thus time unpublished unweighted using vazirani verified verlag vertex vertices weighted will winograd with worst would zwick
http://doi.acm.org/10.1145/982792.982809	13	On Distributions Computable by Random Walks on Graphs	acknowledgments addison algorithms amer anonymous apostolico appear atomic bias bution careful characterize coins combinatorial complexity computable computing condition context convexity directions distributions free from galil generation geometry grammars helpful karlin kelly knuth like math memoirs moment mossel nato necessary nonuniform number paper peres random reading recent referees references remarks results series shapley spaces springer starting states thank their this traub unknown verlag weiss wesley wiley with words would
http://doi.acm.org/10.1145/982792.982833	32	Proximity Mergesort: Optimal In-Place Sorting in the Cache-Oblivious Model	achieve acknowledgments advisor agarwal aggarwal alfred algorithm algorithms alok alpern also alstrup amortized andrew angeles annual anonymous april areas arge ashok author automata bender block bryan cache cacheoblivious cambridge cannot case chandra city clearly colton comments communications complexity complicated computational computer computing danner data december demaine derick dictionaries dictionary discrete dokl edition editor editors efficient elements equal erik existent farach fast fewer field focs foundations franceschini frigo geometry gianni grossi halmstad harder help helpful hendra hierarchical hierarchy holland icalp ieee implicit inactive information input interesting international jainen jeffrey journal july jyrki karlsson kata knuth kronrod languages lars layout lecture leiserson letters like linda lingas loquium lost manuscript martin master math memory merging michael mikkel minimum minkley model movement moves multilevel munro notes november oblivious october open operational operations optimal order ordering original orthogonal output pages pagli panka pasanen place press problem problems proc proceedings processing professor programming prokop quite ramachandran raman range rauhe recovered referee references related results roberto salowe scandinavian science sciences scott search searches searching second selection september siam silver simplified simulation since single snir society soda solutions sorting soviet spring springer stability stable steiger stephen street structures suggestions suite support supporting suwanda swat sweden symposium system table tasks technique than thank their theis theory there these thesis this thorup tomi tony transfer tree trees under underlies update updates venkatesh verlag vitter volume wads william with without wood working workshop worst would york
http://doi.acm.org/10.1145/982792.982914	99	Approximating the Two-Level Facility Location Problem Via a Quasi-Greedy Approach	aardal accounts acknowledgement ageev alexander algorithm algorithms also analytic anglia annals annual anonymous appear applied apporixmation approach approx approximate approximation asaf ascent author automata back bank barros based been bound branch bumb capacitated cation chardaire charikar chekuri chuadk chudak combinatorial combined comments communication computational computer computing constraints converges cooperative cornell cornu costdistance dachuan depends depot design designing develop discrete distribution dowbrands drafts dual east echelon edwards eede engineering engineers european even exact experience facility feedbacks finally fisher float focs form formulation foundations framework francis games general goes good greedy group guarantee guha hansen helpful hierarchical icalp ieee improved industrial infinity information informs integrated interfaces international jain jols journal kaufman kern khuller kortsarz labbe languages less letters leung level levin lflp like linear lncs location logistics loquium mahdian mathematics maximization median metric meyerson mirchandani mngt model muggenborg multi multilevel munagala naval nemhauser network norwich note oper operational operations optimization optimize paper performance personal pete placement plant plotkin polynomial possible preliminary problem problems procedure proceedings processing programming quarterly queyranne references research results reviewers robinson saberi school science shmoys siam side simple sium society soft solution some steiner stoc strictly strikes strongly studied study submitted submodular suggest support sviridenko sympo symposium system systems tardos tcha than thank thanks that their theory thesis this time uncapacitated university veinott version warehouse when which whose wiley with within wolsey workshop would yinyu york zhang
http://doi.acm.org/10.1145/982792.982959	136	Constructing finite field extensions with large order elements	acknowledgment agrawal algorithm also altogether american annual answers applications applying arxiv assume barbara bernstein berrizbeitia boneh cardinality cheng coefficient computer conference consider constant cryptology degree denote discussions does ecpp editor element elements essentially exist extension factor factored family fields finite following form from gathen gauss generator greater have helpful hence high hsin http igor iitk implies international into irreducible iteration kayal lanl large lecture lemma logq math mathematical monic news nonnegative notes number numbers order orders output over pages papers pedro periods polynomial polynomials primality primes proc proof provable proving quartic question random references root roots round santa satisfying saxena science sharpening shparlinski shuhong society solutions some springer step subset take takes than thank that their theorem there this thus time verlag volume which with
http://doi.acm.org/10.1145/982792.982796	2	Tight Bounds for the Partial-Sums Problem	ability advances algebraic algorithmica algorithms also alstrup amram ancestor andersson annual answer appear applications array arxiv based beame because bender better binary biweighted bound bounds brodal burkhard cache case chazelle closure combination complexity computation computational computer computing conference conjecture cost cumulative data demaine derive developed dietz difficulty direction discrete dynamic easy edition efficient especially experience extract fagerberg famous farachcolton fenwick fich finally find focs found foundations framework frandsen fredman frequency from fsttcs further fusion future galil generalization geometry group hampapuram hard hierarchy hope however http husfeldt iacono implemented improving including indexing information inherent instructions interesting international introduction isaac journal kleitman kolmogorov layout limited line list location lopez lower maintaining make marked matching memory miltersen model more most multilevel munro nordic november oblivious offline offs ones only operation optimal orthogonal ortiz paper parentheses partial planar point pose practice predecessor present presented probe problem problems proc prove queries query quite raman rams range rank rauhe references related research results retrospect sadakane saks science sciences searchable searching second seems select sense siam skyum software springer stems stoc structure structures subset succinct sums sung surpassing survey symposium system tables technique techniques technology than that theoretic theoretical theory there this thorup tight trade transitive tree trees understand unfortunately verlag vitanyi wads will willard with word work workshop would york
http://doi.acm.org/10.1145/982792.982960	137	Polynomial Interpolation from Multiples	above absolute acknowledgement additional ajtai algebraic algorithm algorithms alit also althe analog analytic annalen annual anymore application applications applied apply approximation areas assume assumption attenthat attracting austral authors basis berlin birkhauser bits black boneh both bound bounded bounds bull calculate case codes coding coefficient coefficients combinatorial combined comp comput computn conclude congruence consider consideration consistent constant constraints construct controlled corresponding cost crucial cryptographic cryptography cryptology debrecen decoding degree denominator depends desire diffie discr discussions does each easy efficients equations estimate everest evertse example exponential extended faces fact factoring factors fields finally finite follows form from fudge general geometric given gorithm group gruyter guruswami hardness have hidden hide hierarchy however ieee ignored immediate implies impossible improved indeed inform information ingredients input instead integer integers interpolates interpolating interpolation justify kaonecker keys konyagin kumar lattice lattices leading lect lemma lenstra linear list lman lower lowered mabb making manuscripta many matem math mathematische matrices meeting mentioning method mially mmabb modulo monographs more most much multiple multiples multiplicative namely nguyen nonzero notes number numerator obtain only open optimization original output over oviedo papers particular playing polynomial polynomially polynomials polynowith poorten possible prime primes problem proc progress proportional publ queries question rational recovering recurrence reducing reduction reed references related relation relaxed remains remarks residue returning returns ring rings roots rounding russian satisfy sbornik schemes schlickewei schmidt schnorr schrijver secret security seek sequences shortest shows shparlinski siam sieve significant since sivakumar size small solomon solutions solve some spanish sparse special springer springerverlag stern subspace such sudan sums surveys symp teresting thank that their theor theorem theory there therefore this thus time tion trans tschel under unique univ univariate unknowns update useful value values variables vector vectors venkatesan verlag waldschmidt ward weaker when where which whole wigderson will with works would zeros
http://doi.acm.org/10.1145/982792.982835	34	Family Trees	access accessed accomodating achieve acknowledgments acmsiam addressable advantage advantageous algorithm algorithms also annual applications arbitrary architectures arrays aspnes assuming awerbuch balakrishnan balanced bases bears being bordeaux both bounds bozanis butterfly cache caching cascade castro change chord client close communications compact computing conclusion concurrent conf conference congestion consistent content contention contribution could cowen data decentralized degree described design deterministic dictionary discrete discussions distributed does domain drafts druschel dunagan dynamic each efficient emulation ensure environment environments estimation event exist expectation expected family files first fraction francis from furthermore gavoille given graphs group handley harvey hash hashing have helpful hence high hypercubes hyperring immediate implement implementation imply including infrastructure input international internet intl introduction iyer jczak john jones july june kaashoek karger karp kaufman kermarrec keys koorde kroll labri large lehman leighton level levine lewin like linear lists litwin locality localized lock lookup made malkhi management manolopolous many memory minimum model more morgan morris multiple munro name names naor neimat network networked networks nine node nodes notification numeric only optimal order ordered ordering other overlay overlook pages panigraphy paper paral part patterns peer peleg performance pointers practical predecessor presented preserving previous principles probability proc procedure proceedings process properties protocols queries random range rata ratnasamy readers references relieving report results reviewing routing rowstron running saroiu scalable scale scheideler schneider scribe sdds search searched searches searching section service shah shenker shown siam sigcomm sigmod simple simultaneously situation skip skipnet source spots squirrel stoica stretch structure structures such suited summary support symposium systems table take target technical technologies than thank that theimer theory these they third this time topeer topic traffic tree trees tributed uniform universit update updated updates used useful usenix very viceroy well where whole wide widmayer with wolman workshop world would writers
http://doi.acm.org/10.1145/982792.982920	104	Hole and Antihole Detection in Graphs	academic acmsiam acyclic acyclicity additional algorithm algorithmic algorithms also antihole antiholes appear applied approach aspects asymptotically augmented berge berry best bordat both case certain checking chong chordal chordality chudnovsky classes comb come comparability complement complexity computed computer computing concluding connectivity constructed construction consuming contain containing contains cormen cornu corresponding cost currently dahlhaus decomposition dept deren described design detecting detection determination discrete does edge edges edition efficient elimination exist existence existing exists explicitly fact farbung fastest finally finding focs former foundations general golumbic graph graphen graphs gustedt halle handle handles have hayward heggernes hold hole holes hypergraphs ieee imply improved improvement indicates inform input interesting introduction ioannina jols kreise large latter leiserson length letters light linear lueker maintaining martinin math mathematisch mcconnell mcgill mentioning missing modifiable modular more naturwissenschaftliche needs nikolopoulos none nordic note obvious only open optimal paid palios parallel participating perfect pose practical preprint presented press problem problems proc process proves recognition recognizing reduce references reihe remarks report require requires result results return rivest robertson rose runs same samtliche school science search seems selectively separability sequential seymour shown siam simple sind soda something space special spinrad sritharan starr stein strong structure such symp systems tarjan technical test than that then theorem theoretic theory these thesis they this thomas time timeluther triangulated undirected ungerade univ verify vertex vertices very vukovi weakly whenever whereas whether which while wiss with wittenberg workshop worst worth would yannakakis yokoyama york zeitschrift
http://doi.acm.org/10.1145/982792.982818	20	Optimal Routing in Chord	addison algorithm also appears applications automata average balakrishnan bitfixing characterization choose chord computation consider considerably convert converting dabek different dimension dimensional either experiments figure find fixing following from general hopcroft however hypercube hyperskewbe idea identical ieee improvement improves indicate interesting internet introduction kaashoek karger languages left length lengths liben lookup lowell makes morris motwani network networking node nodes obtained open optimal path pearson peer perform presence problem properties protocol references results right route routes routing scalable shorter shows simple simply standard stoica suppose that their then theory these this three toleft transactions ullman union upon wesley which wish with
http://doi.acm.org/10.1145/982792.982952	130	Approximate classification via earthmover metrics	above according achieves acknowledgment acmsiam algorithm algorithms along also alternative analysis annual approach approximating approximation approximations arbitrary assigned assignment associated association awerbuch bartal between bound boykov calinescu charikar chekuri child children cknz class classification clustering collection combinatorial combinatorica combinatorics communication complexity comput computer computing conference constant contain corollary corresponding cost costs cuts dahlhaus decomposition decompositions denote derandomized described designing desired details diameter discrete discussions distance distortion distributed distribution distributions down dynamic each earth earthmover easily edge edges efficient embedding energy eran european every excluded exists expectation expected extends extension extensions factor fakcharoenphol fast felzenszwalb fhrt fields finite flow following forbidden formulation foundations from geiger general generate generating geometric given goel graph graphs grouping guha gupta halperin harrelson have help helpful here huttenlocher ieee importantly improved inequality input integrality intel international ishikawa jacm january jcss johnson journal junctions karger karloff karzanov khanna klein kleinberg labeling labels leads leighton ligence like linear linial lower machine machinery markov matching maxflow measures metric metrics minimization minimum minors more moreover mover multicommodity multiterminal multiway naor network node nodes nomial note number omit optimal optimization original over pages pairwise papadimitriou partitions pattern peleg personal pictorial plotkin point points polye polynomial preserved probabilistic probabilities probability problem problems procedure programming proof propagate proposition provides proximate proximation rabani random randomized really recognition references relationships required results root round rounded rounding saks sample satish scheme science segmentation separation several seymour siam siamsymposium small smooth solution solvable solve space sparse specified springer stein steiner structures submitted such summing symposium talwar tardos technique thank that their then theorem theorems theory there thereby these this thorup thus tight time transactions tree trees triangle uniform uniformly uses using variable vazirani veksler verlag vertices vision where which while with workshop would yannakakis yields york young zabih zosin
http://doi.acm.org/10.1145/982792.982918	102	Subexponential parameterized algorithms on graphs of bounded-genus and H -minor-free graphs	acknowledgments adding adjacent affecting after again algorith algorithm algorithmic algorithms along also american annual another anual appear applications apply applying approx approximation artificial asks aspects authors automata auxiliary available baltimore base basic because believe berlin between bidimensional bipartite bipartition boltenhagen boundary bounded bounds branch branchwidth call called canada cannot case cases cell center centers characterizes circle claim class classes clique closed closure collection colloquium combin combinatorial combinatorica combining communication compact complexity component components computation computational computer computing comupter conactible concepts conclude conditions conference conjecture connected connection consecutive consider constant construct contains contractable contraction contractions contrapositive corresponding counting cover crosscap crossing cuts cycle decomposition decompositions definitions dekker demaine denotes desired digraphs dimension direction disc discrete discussions disjoint distance distinguish dominating domination dominationtreewidth domthen done drawing dynamic each eccc edge edges efficient electronic electronically elsevier embedable embedded embedding embeddings encouragement enough equal equivalence euler every example excluded excludes excluding existence exponential extended fact fair families family feedback fifth final find finite finland first fixed flow focs following follows foundations francisco free from frontiers function fundamentals general generalization generalize generalized genus germany given graph graphs grid have helpful holds homeomorphic homotopic hopkins however hypothesis icalp ideas ieee imies implies improved imum inating incident increase indebated indeed induction input intelligence international into isaac italy johns journal kaufmann kernels kface lack languages larger least lecture lemma lems length less line linear linearsize lncs local main making manifold manuscript many marcel mathematical maxi maximum meeting mentioned mfcs mica mind minimum minor minorclosed minors more morgan most multicommodity naomi need network nishimura noncontractible nonorientable nonseparating noose norm normal notation notations notes notice null number observe obstructions obtain obtained obvious online only open operation optimization order orientable outerplanar paper parameter parameterized parameters part partial partially paths paul personal philadelphia planar plane point points polynomial portal powers prabhakar present press prob problem problems proceedings programming proof proofs property proposition prove proved providing publishers publishing question quickly ragde recently reduction references region regions related removals remove represenpl represent representative representativity representing research result resulting results scandinavian schemes science sciences second seen separating sequence sets seventeenth seymour shallow shown siam simplify since site size smaller society soda solution solve solved some space speed speedup sphere split splittable splitting splittings springer step stoc strictly strong structures studies subcollection subexponential subgraph subset subsets such suppose surface surfaces suspect swat symposium taking tativity technique tempting than thank that then theorem theorems theoretic theory there therefore this tight time ting tractable transformed transversals tree trees treewidth triangulated triangulation turku turn twenty uncertainty union university upper used useful using vancouver verlag vertex vertices very where whether which width with within without workshop xiii york
http://doi.acm.org/10.1145/982792.982866	60	Correlation Clustering: Maximizing Agreements via Semidefinite Programming	above achieves acknowledgments adapt agreements algorithm algorithmica algorithms also amos analysis andersson appear applications approach approx approximation arbitrary arccos bansal based between bisection blum both cedure cedures charikar chawla choose choosing cluster clustering clusters comparable consider contribution correlation david decreases defines delivers demaine denote describe different disagreements distributed distribution dotan each edge efficient efficients eiwout emans emanuel empty engebretsen ensure equations expected extend fiat focs former formulation frieze function gives giving goemans graphs guruswami have helpful however hyperplane hyperplanes ieee immorlica improved improvements independently information inside into involved involving itself jacm jective jerrum latter least lemma lies limitations linear many mathematical maximizing maximum maxj minimized minimizing more moses most multiple need nodes normal normals obtained only optimal ordinates origin osing other partial partition passing point possibly pouco pout probabilities probability problems proc procedure produces program programming proof qualitative random randomly rapidly ratio references relax relaxation replaced resembles respectively results round rounding same satisfiability scheme semidefinite sets sharing shmoys significantly sketch solution solve some space sphere stad standard such suggestions thank that their theorem ther there these they this through times uniformly unique unit using value variant vectors vertices weighted when where which while whose williamson wirth with works wout xdge
http://doi.acm.org/10.1145/982792.982891	80	Lyndon Words with a Fixed Standard Right Factor	abbc abcc acbc accc addisonwesley algebra algebras algo algorithm algorithms alphabet also american analytic applications apply assoc asymptotic available average basic basis bbbc bbcc bcbc bccc beginning behavior benot berstel boasson book booth brackets bull burnside calculus central chapters chen circular class closed combinatorics complex component comput computed consider construction context convenient decomposition deleting denote difference differential difficulty duval eatcs efficiently element encyclopedia enuuse even every exactly fact factor factorizable factorization factorizing first fixed flajolet four free functheorem function further generate generating give given gives groups having hence hint homogeneous however html http increasing individual inform inria instance jolet journal language languages last least length lett letter letters lexicographical lexicographically linear list lothaire lower lyndon math mathematics merate moreover next notation numbers obtained only operator order ordered over oxford preparation press problem process product proof properties publist quotient random rational recall references regular reject remark reports research result reutenauer right runs ruskey same sawada sedgewick series shifted smaller smallest space standard step strings structurally study subb symbol symbolic than that then theor theorem this thoroughly time tions trans under underline uniquely university until used using vein when which with word words would
http://doi.acm.org/10.1145/982792.982820	21	Approximation Schemes for Multidimensional Packing	acknowledgments algorithmica algorithms annual another approximability approximation aptas archivum authors bansal before berlin bins bound bounds brazilian caprara case chin classic coffman combinatorial combinatorica combinatorics comments computer computing cube cutting david decide deis determine dimensional distributed does errors even evidence example fact fast fernandez ferreira finding focs following formulated foundations garey generalize geometry given gives good graco graphs hardness harmony height higher ieee illustrates implies inapproximability interesting into johnson journal kenyon kleitman kohayakawa krieger larger leung leveloriented like little lodi lueker many mathematics mathematicum mentioned mimeographed minimum minor miyazawa monaci more moser multidimensional near needed novotny number obtained open operacional operations optimal packing paper paral partially performance pesquisa pointing polynomial poorly presentation problem problems proceeding proceedings question raghavan rectangle rectangles references regarding related remila report research result results rounding schemes science second seems seiden showed siam since smaller solution solved solves some springer square squares stage stee stock strip stronger suggestions suppose sviridenko symposium tarjan task techniques than thank that their them theorem there these they this three time trivial twodimensional unit unless unsolved useful uses vazirani vega verlag version wakabayashi width will with within wong work would young
http://doi.acm.org/10.1145/982792.982909	95	A certifying algorithm for the consecutive-ones property	acad academic acta algorithm algorithmic algorithms analogous ancestor annals applications arrangements aspects between blum boolean booth boston brandstaedt breach cambridge cederbaum certifying checking chein children circularones classes clustering comb combinatorial common comparability component comput computer computing connected consecutive cormen dahlhaus declares decomposition degenerate described discrete does efficient eher either elements even fails focus foregoing functions gallai generalized geometric give golumbic gordon graph graphen graphs habib hard have hierarchical hill hring hungar hypergraphs incompatibility intersection interval introduction journal kratsch least leda leiserson lemma lempel linear lueker math mathematics maurer mcconnell mcgraw mckee mcmorris mehlhorn modular monographs node ones operations optimization orientation orientierbare over pairs paral parity partitive perfect permutation philadelphia planarity platform press prime proof property recognition recognizing references relations relationship reliability research result rivest rosenstiehl same science show siam single soda software spinrad split stein structure substio suppose survey syst systems testing that their then theorem theoretical theory this time topics transitiv transitive tree trees tucker tution university using wasserman york
http://doi.acm.org/10.1145/982792.982857	52	Fast mixing for independent sets, colorings and other models on trees	abstract academic algo amenable apparent appear appl arxiv berkeley berlin bethe bolyai bound boundary bounds broadcasting cambridge cayley chains cluster coloring colorings colouring combinatorial combinatorics commu comp computer computing condition conditions constant constants contemporary convergence core countable coupling criteria dapest decomposable definition degree dept dimacs discrete disorder dmtcs dynamics eecs elaborate electronic equation exactly extended fact fast fields finally five flour flow follows found foundations free from full further generalized gibbs girth glauber graph graphs gruyter hard high homogeneous http hyperbolic ieee implication improved independent infinite information interesting introduction ising janos journal july larger lattice lecture lectures lemma lett letting light london lower lution marginally markov markovian math mathematics maximum measure measures mechanics mentary mention mentioned mixing model models modern modified morphisms ncstrl nication note notes october only order original paper part parts phase philos phys physics poincare point potts preliminary preprint press probab probability problem proc rand random randomly range reconstruction references regular related report reviews royal saint sampling science second sets show slightly sobolev solved some spin springer states statist statistical statistics stochastic struc struct studies sunsite survey symp symposium systems tech than that then theorem theory this threshold thresholds time transformations transitions tree trees uniform uniqueness university version volume walks walter where with
http://doi.acm.org/10.1145/982792.982890	79	Fast Approximate Pattern Matching with Few Indels via Embeddings	achieves algorithm algorithms also always approximate approximately arguments arranged been before being between binary block blockmatch blocks build call calls case conference consider construct corresponding counting data databases datasets definition deletions denote denotes differs difficult dimensional distance dynamic each entries entry equal euclidean fact fast fill final finding first fixed following follows given hamming identifying implement implementation implemented implementing indyk information initialize insertions instead integer international karloff koudas large length letters longest massive match metric mismatches most muthukrishnan needed numbers observe obtaining operations oracle order original other parameters pdhg positions power prefix preprocessing problem proceedings proceeds processing programming purpose query real recurrence references representative reqc returns same search searching series setting show since size sketches slightly smaller specifically square stated states strings structure structures subroutine subsection substitutions such suffices support table than that then therefore this thus time trends uses using value version very vldb when where which with
http://doi.acm.org/10.1145/982792.982838	36	Improved Upper Bounds for 3-SAT	algorithm allows also analysis apparently appl argument assigned assignment based baumer becomes between both case claim clause coding constraint correct dantsin decision deterministic discrete distance dynamic eccc finds focs follows from further goerdt hamming high hirsch hofmeister hssw improved improving independent initial kannan kleinberg kullmann least lemma lemmas less lncs local math metho minimum monien next ning number onential pairs papadimitriou paturi ppsz presented probabilistic probability problems proc proof pudl raghavan recall references repetitions rolf rtime saks same satisfaction satisfiability satisfying schiermeyer schuler search single solving speckenmeyer stacs standard starting starts steps success suppose than that then there time uses values variables watano when which with worst zane
http://doi.acm.org/10.1145/982792.982888	77	When Indexing Equals Compression: Experiments with Compressing Suffix Arrays and Applications	abouelhoda abstract access achievable achievements adaptive adding addressing algorithm algorithmica algorithms almost also analysis applications arikawa arimura arithmetic array arrays asaka baeza balanced based believe bell bender bentley best biology block boosting both bounds brodnik burrows burrowswheeler bury canter canterbury cascading chazelle class codes coding colton communication communications competitive compressed compressing compression computational computer computing considering constant construct construction corpus cost data databases datacompression depends despite develepment developed dictionaries directly discovery documents economical efficient encoding engineering enhanced entropy exact experience experimental exploit extended farach fast ferragina file files focs fractional full further genome giancarlo gigabytes gonnet google graphs grossi grounded guibas gupta gusfield have help high html http images improvement improvements index indexable indexes indexing indices info infor information integers intense inverted isaac ishii jacobson journal kanazawa known kurtz langdon latin lempel length line linear locally managing manber manuscript manzini matching mccreight membership method methods minimum minutes model moffat more moura multisets munro myers navarro nelson neubert notions offs ohlebusch opportunistic optimal order outperform pagh parentheses partitions pattern patterns perform personal plan planar possible practical practically practice problem property proximity query raman reduced reducing redundancy references refine removing representation representations requirement reserch retrieval revisited rissanen room roughly sadakane sakamoto savings scheme science sciortino search searches self sequences shtml siam sicomp significant silva similar sleator snider soda software solid sophisticated sound space spire srinivasa static stoc string strings strong structures structuring study succinct such suffix system szip tarjan technique techniques test text that theoretical there these time tois trade transform tree trees trie tune tuneable underlying unix unknown upon using vitter wabi wavelet wheeler which williams with witten work yates yields ziviani zobel
http://doi.acm.org/10.1145/982792.982945	124	End-to-End Packet-Scheduling in Wireless Ad-hoc Networks	about access acknowledgments adaptation additional adler advantage after alessandro algorithm algorithmic algorithms alon along amply analysis andrews anil applicable approach approximation april arbitrary architectures around aspects assignment available averaging away awerbuch balakrishnan balancing barrett believe berger better between bigger brooks cannot capacity certain channel characterizing choosing chosen chung colored coloring colorings colors combinatorica communication compensated complexity computation computer computing conges congested congestion connected connection constant control cost costs cowen criteria davie deal decomposition decompositions decrease decreases defined definition delaware delay department describe destination destinations diameter different dilation discrete discussions disk distributed dominating done doubling dropped drozda dubhashi during each ease easy edge edges edition effect efficient either empirical empirically ensures expected experimental experimented experiments exponentially fact factor fast fernandez figure figures finding finocchi first fixed follows foundations framework from gains gets global goel goldberg good grable graham graph graphs grid grids hand hari heavily heide helpful hence here hops however hypercube ieee impact implementation implications increase increased increases increasing incurred incurs induced infocom initial injected instantaneous interaction interconnection interestingly intermediate international into istrate japan jcss journal june kaufman khot kobe krumke kumar large last latency layer least lecture leighton length linear linearly lines linial link lloyd lncs local locality longer loss lost lowmodified luby maggs manuscript marathe matchings mathematics maththematics maximum measure media meyer mobihoc mobile models modified morgan most much multi multiplicative naturally needs network networking networks newark node nodes notes notice number obtained order ostrovsky other over overloaded packet packets pages pairs panconesi paradigm parallel parameters particular partition pass path paths peleg penalty performed performs permutations peterson placement plane plot plotkin plots plotted polynomial practice previously problem proc proceedings processor proofs proposed protocols provably publishers rabani radhakrishnan radio raghavan ramanathan ranade random randomized randomly randomness range ravi recall reduce reducing reduction references regions relationship removing respect respectively results richa rounding rounds route routes routing runs saks schedules scheduling scheideler science second seems sensitivity sequentially sets sheideler shop shortest show siam silvestri simple since size skeletons some sorting source sources space specific specifically springer square srinivasan stabilizes stage steps strategies strategy structures study subhash substantial switching symposium systems tailored tardos technique terms than thank that then theory thesis third this thite thompson thousands three through tion total trade transactions transmitted traversed trying twice unified unit universal university used useful using valiant value values varied varies various verlag vertex vizing vocking weakly weighted weights were which while wireless with within without yields zhang
http://doi.acm.org/10.1145/982792.982947	126	Optimally Scheduling Video-on-Demand to Minimize Delay When Server and Receiver Bandwidth May Differ	achieve achieves acknowledgements ailan algorithms among analysis april area audio bandwidth beek before being broadcast broadcasting comprehensive computer consider consistent contradiction delay demand describe design differ digital discrete does dtdx dxdt each early efficient engebretsen entirely exists fact factor fixed fragmentation harmonic ieee infocom interval introducing january july kurose ladner length like mascots media model modeling most movie network nikolaidis nossdav note operating optimal pages played popular problems proc proceedings protocol protocols proves received receiver references richard same scheduling schemes segment sender server siam simple simulation some stripped study such sudan support suppose symp symposium systems tami tamir techniques telecommunications thank that then there this time towsley transfer video videos when where with workshop would
http://doi.acm.org/10.1145/982792.982807	11	Linear Phase Transition in Random Linear Constraint Satisfaction Problems	according achlioptas acknowledges acknowledgments alan aldous algorithm algorithms also amer analysis annual applications applying approximating aronson assignment asymptotic asymptotics author based between boufkhad case cghs chvatal combinatorial combinatorics combining comes complexity computer consider constraint constraints containing contribution convergence converges coppersmith correspondence corresponding dard david defined details discrete discussions distributed dover dubois durrett duxbury edge edition event exact exactly examples exist fact fairly fernandez fields fifth first formulae formulas foundations friedghut frieze from fruitful gamarnik gets goerdt graph graphs grateful gratefully greedy growing grzegorz havel holds ieee independent instead interesting international janson jiaghayi john jonathan just kaporis karp kirousis koubek lalas large lecture lemma lenghts limit linear link local luczak mandler manuscript matching matchings math mathematical mathematics maxcut maxim maximum maxsat method mezard michael mick minimal moderately moment moore naor neighborhood note notes nowicki objective observed obtain odds omit only optimization order papadimitriou parisi part peres phase physique pittel polyhedral pose preprint press previous probab probabilistic probabilities probability problem problems proc proceedings proposition proprties random rank reed refer references required results revisited rucinski same satisfaction satisfiability science sciences second section select sets sharp shown siam side sipser solution some sons sorkin spanning sparse springer stankesten steele steiglitz structures submitfor submitted sufficiently suppose sviridenko swirscsz symposium system techniques term testing that their then theory these this threshold thresholds tight transition transitions tree trees typical unpublished unsatisfiability using values variables vega verlag weak weight where wiley with wormald
http://doi.acm.org/10.1145/982792.982803	8	Network Failure Detection and Graph Connectivity	about acknowledge acknowledgments acta adversaries adversary algorithm algorithms already also analogy annual another applications apply arch assume asymptotic augmenta augmentation awege balanced because berkeley blumer bound bounds building cactus centroids chain cheriyan cherkasskij chervonenkis chung circuits cited claffy claim clear clearly combin complete computed computer computing connected connection connectivity conp constant contradiction contribution cuts deciding defining delete deleting dept described detecting detection difficult dimension dinits direction directions discrete discussions distance edge eecs ehrenfeucht ekon empty equal equivalence eulerian exist expander exponentially extend extensions fact failure failures fakcharoenphol family fast finally find finding fleischer flow flows focus foundations framework frank fridman from full further gabow garrett generality given graham graph graphs group gupta hand haussler have here hung ieee improved includes indeed independent inet inferring instance interesting internet investigate ippm jordan journal kantendisjunkter karzanov kleinberg korte laszlo layouts learnability least left lomonosov loss lovasz mader mahdavi many master math mathematical matters maximalzahl mcrobb measuring meets metody metrics minimal minimally minimum monk moscow motivation multicommodity muthukrishnan natural nature nauka need network node nodes note number obtain open optimal optimality optimization orlin other packing parallel parameterizing paths paxson performance picard pleasure polynomial portion problem problems proc programming promel properties prospect proved provide provided provides questions queyranne realization references representation representations respect restricted result results russian same schrijver science sciences section separator separators sept sets shallcross showing shredder shredders siam since size solution some springer step strong structure studies study subgraph submodular such suel suffices survey symposium system techniques tests that theory there thesis this thurimella time times tion tomography topologies towards tree trivial uber using value vapnik verlag version vertex vingralek vlsi warmuth weak weighted when whether which with without work working would
http://doi.acm.org/10.1145/982792.982879	70	A General Approach to Online Network Optimization Problems	above acmsiam adam algorithm algorithmic algorithmica algorithms alon alternative annual applications applies apply applying approach appropriate approximate approximating approximation arbitrary awerbuch azar bartal basic berlin berman between bienkowski boston bound bounds buchbinder cannot choose claimed cleaning commodity company competitive complementary computation computer computing condition congestion conl considering constructing contains copt corresponding corresponds cost coulston cover decomposition denote denotes description deterministic developed dimitris discrete dual dynamic each edge edges edition element essentially facility factor fakcharoenphol first flow focs follow follows fotakis foundations from garg general generalized group hard harrelson height hence here hidrum hochbaum however icalp ieee imase improve integral into journal konjevod korzeniowski line local location lower main math maximum mcfopt metho metric metrics meyerson minimize minimizing minimum most multi multicut naor networks note oblivious observe online only optimal order pair pairs path polylogarithmic polynomial practical preserved primal primaldual probabilistic problem problems proc proceed proceedings produced providing publishing ratio ravi reduce reduction references relaxed result routed routing scheme schemes science second separates setting show siam simple since sink slackness source sourcesink spaa spaces spencer springer stage standard steiner substituting symp symposium take talwar technique that their then theorems theory there this thus tight time translates tree trees trivially unique values vazirani verlag vertices waxman when where which wiley with yannakakis yielding yields york zero
http://doi.acm.org/10.1145/982792.982941	121	The Wake-Up Problem in Multi-Hop Radio Networks	achieved algorithms annual another appear applications apply approach approx approximation aspects automata between bound bounds broadcast broadcasting bruschi cambridge case chlamtac chlebus chrobak clementi codes coll collision combinatorial communication communications complexity computation computer computing constructions crescenzi czumaj detection determinism deterministic develop direction discrete distributed efficient expansion explicit exponential factor families fast faster focs foundations gasieniec gibbons goldreich gossiping however icalp ieee indyk international isaac israeli itai journal jurdzinski knowledge kowalski kushilevitz languages lncs logaritmic lower mansour manuscript mathematics mobile monti motwani multihop multiple network networks optimum ostlin pelc peleg penna pinto podc poly press principles probabilistic problem proc proceedings programming protocol radio raghavan random randomization randomized references related remains robson rytter science sciences selective selectors siam silvestri since single small soda stachowiak stacs still structures study substantial superimposed symposium synchronizers synchronous system systems techniques terministic than theoretical there thus time topological topology trans undirected university unknown upper wake wakeup wave weinstein with within workshop would yehuda
http://doi.acm.org/10.1145/982792.982862	56	Minimum Moment Steiner Trees	aided algo algorithm algorithmica amsterdam appl approximation arborescence automation based because boundary bounded changed complete computer condition conf cong constant delay design disc distance distributed driven except from garey graphs hanan hand have here holland horowitz hwang ieee improved interconnect johnson june lemma leung math model networks north optimal other penfield performance problem proc property rectilinear references richards robins rubinstein sadayappan satisfy shor siam signal soda steiner steps symp that then theorem therefore trans tree trees true where winter with works zelikovsky zhou
http://doi.acm.org/10.1145/982792.982902	89	Structural and Algorithmic Aspects of Massive Social Networks	acad acknowledgments actual additionally alamos albert algorithmic algorithms alon also although among analysis anil annals applications applied approximating approximation around assessment attack available barab barabasi barrett berlin best bollobas bornholdt bounds broder case chang chen chernoffhoeffding chung city colorings combinatorics comm comments complex components comput computer computing concentrated conf confidence connected constrained control cooper cover craft critical data database degree degrees diameter distributions dominating drawn dynamics edition efficient emergence emergency empirical epidemics epidemiological episims equitable eubank extend faloutsos faster fastgen fastgreedy feige figure focs formal foundations four free frieze from general given govindan graham graph graphs guclu handbook have helpful high homeland hottop http ieee infocom infrastructures input instantiated internet jacm jacob jagopalan jamin jeong july june kaplan kumar laboratory lacp language lanl laur laws least lective level ling locations lpox madrid maghoul marathe mass mathematical mcdiarmid mechanics merits method model models molloy much national natl nature networks office origin overview path pemmara phys point power principles probabilistic problems proc provides quarterly raghavan random real reed references regulargreedy relationships report research response responses results reviewers revisited riordan scalable scale scaling schester science second security seen sequence sequences sets sharply shenker should shows shtml siam simulation since sivakumar slower smal smith soda solution spencer spring srinivasan stata statistical still stochastic stop strategies strogatz structure structures symp symposium system systems table take technical than thank that their theory those threshold tomkins topologies topology toroczkai transims transportation understanding upfal vaccination virtual volume vregulargreedy wang watts wein where wide wiener wiley willinger with world
http://doi.acm.org/10.1145/982792.982938	118	Non-migratory Online Deadline Scheduling on Multiprocessors	about academic according achieve actually admit admits algorithm algorithms alone also amir amount analysis arbitrarily assumed attaining augmentation baruah believe berman better between bound buttazzo centralized certain chrobak clairvoyance close comp competitive complete completed computer computing congress conjecture consider control corollary could coulston critical current dark dead deadline decision depends dertouzos different difficult distributed does each editors edmonds effect eliminating engineering epstein etitive etween extra fact factor fiat firm from function further given greater guarantee hard have hence highest however icalp ieee ifip implementation inalgorithms increase information inputs inquire jobs journal kalyanasundaram kluwer know koren laxity least lecture line lishers loose lower make many match maximum migration migratory mishra moca module monitor more multi multiprocessor need needed noga notes notice obtain offline offs online only opti optimal order original other otics over overload overloaded ower owerful pages park particularly performance phillips physical pool possible possibly precisely preemptive presence problem problems proc procedural proces processes processor processors pruhs pubof quite raghunathan ramamritham ratio real recall reduce reduced references related require required requirement resource reveals rosier scaled sched schedule scheduler scheduling science seems selected selecting selection sequence sgall shasha shown shows siam simple soda software some sors span speed springer spuri stankovic state status stead stee stein stoc subset sufficient survey swat symposium system systems tained tasks than that theoretical there third this thus tichy time torng trade transactions unit upper useful using vakhania value values verlag wein when where which with woeginger work
http://doi.acm.org/10.1145/982792.982929	111	Reconstructing Strings from Random Traces	able above afterwards akademii algorithm algorithms alon also annual applications asymptotical backward between biased binary binomial boils bound cambridge capable clearly codes coin computer conclude consider contants correcting correction deletion deletions density discrete diskret distance distinguinhing distinguishbetween distinguishing distribution does dokl doklady dominates down edmonds efficient english enlgish erasure exact expression fair first flips following follows former forward foundations from functions furthermore geometric good gusfield have hence hich ieee including independent inform information informatsii insertion insertions known last latter lemma lengths less levenshtein like linear luby mathematics metric moves nauk nearly negative negligible note number ones optimal optimality over peredachi perfect physics position possible press prior probability problems problemy proof prove random reconstruction recovery references required requires return reversals runs russian same samples science section sequences show showing shown shulman since soviet spurious sssr state stay step steps strings such suitable summing symposium than that them then theory this thus time trans translation transmission transpositions trees university until upper using values vari variables vious visit walk well with would zuckerman
http://doi.acm.org/10.1145/982792.982912	97	Quasiconvex Analysis of Backtracking Algorithms	abstr abstract acknowledgements adjustment algorithm algorithms also always amenta analysis analyze another appear appearing appropriate arithmetic arxiv august automatically automation backtracking based basis before beigel berlin bern better binomial bius bound bounded bounds briggs byskov cardinality case causing central codes coefficients color coloring colouring comments complex comput computational computed computer computing conditions confluent conjecture consistent constraint construct correct correctness covering cubic dantsin data december defined derived design determine diagrams dickerson direction discrete discussions displays drafts drawings duality edge eecs eppstein especially evidence exact example explore exponential fachb factor faster february find finding first formula foundations freie from gamuts general generalized generally geom geometry george goodrich gramm grant graph graphs have helly help helpful here highly hints hirsch however html http ieee improved independent information inst instance interest itself january jesper keith keithmbriggs language least lecture like linear little lower lueker lycos math mathematics mathematik matouek maximal maximum members meng mesh meshing more niedermeier notes number observations october only open optimal optimization optimized paper papers part paturi pdmi perform perhaps placement planar point polynomial possible ppsz preprint probabilistic problem problems proc program programming programs proof proven publicat pudl pudlak python quasiconvex real recurrence recurrences references refinement repeated repository research robson rossmanith rossum rtner saks salesman satisfaction satisfiability schoning science sets setting sharir siam simple situations small smoothing soda software solution solving some source sparse specifying springer ssor start state steklov step structures subexponential such supported symp table target tech thank that their theorem theorems theory there these this those tight tighten tiled time tools towards transformations traveling tudelft type under univ upper used useful using variables vector verlag visualization visualizing warners ways website well welzl what where which while with within work worksh worst would zane
http://doi.acm.org/10.1145/982792.982906	92	Computing Equilibria for Congestion Games with (Im)perfect Information	about algorithm algorithms allocating american analysis appear approach approximating arrangements auctions balancing bandwidth based bayesian behavior beier bell bounds bursty capacity carnegie claim class collusive commerce competition completeness complexity computers computing conference congestion conitzer connections constraints coordination core crowding cryptographic cryptology davidm demand deng dept devanur dilemma discrimination disneyland disturbed dual economic economics efficient electronic entry eqqeeq equilibria equilibrium exact expected facilities fact feldmann finding focs fotakis free freeman function gairing game games garey glasgow goel goldberg guide hardness harris harsanyi have holzman html http icalp impagliazzo imperfect incomplete indyk information informed international intractability johnson journal june kleinberg knapsack kontogiannis koutsoupias kyle leland load lucking management manlove marchetti market maskin mavronicolas maximinimal mellon meyer mial mickey milchtaich minimaximal monderer monien monopolistic monopoly mouse naor nash nashification obtain optimal optimization order papadimitriou part partial payoff payoffs played player players polyno possessing potential presence pricing primal probabilistic problem problems provably publications pure putting quarterly rabani rand random randomly ratio raviv references related representation results review riley rode ronen rosenthal routing saberi safra sandholm schemes schmalensee science scotchmer secure selfish sequentially shapley shared soda solution solvable spaccamela specific speculation spirakis staiger stoc stochastic strategy strong structure structures studies subset tardos tariffs that theory thesis tier time together type uncertainty university used value vazirani vocking where with wolak yone zero
http://doi.acm.org/10.1145/982792.982853	49	An Optimal Randomized Algorithm for Maximum Tukey Depth	acknowledgements acmsiam agarwal algorithms algos aloupis also amenta analysis andconquer appear appl applications applying approximating arrangements aspects asymptotically bell berlin bern bivariate bound bounds canad center centerpoint chan chazelle clarkson clouds cohen cole collision combinatorial complexity comput computation computational computing conf congress considering constants constraints constructing contours convex cormen cortes cutting cycles data depth design detecting diam diameter dimacs dimension dimensional dimensions discrete discussions divide down dyer dynamic easy edelsbrunner efficient eppstein erickson estimates example expected fall fast faster fermattorricelli finite fixed found from geom geometric geometry gill gomez goodman graphs gupta hidden hill html http huge hull hulls hyperplane hyperplanes ieee improved initial integer interesting internat introduction involving iterated jadhav janardan japan jects kreveld labs langerman lect leiserson lemma level linear lines location lower made manuscript many math mathematicians mathematics matouek maximal maximum mcgraw median medians megiddo mesh methods miller minimum mitchell moving mukhopadhyay multidimensional multivariate naor networks norton notes obtain optimal optimization pages papers parallel parameters picturing placement planar plane plotkin point points pollack polynomial posing practical preliminary problem problems proc programming programs providence proximity queries radon ramaswami ramos random randomized references regression related remark remarks requirements revisited rithms rivest rousseeuw ruts same sampling schwarzkopf seem seidel sellares separation serial session sets setting sharir shor siam sinica slowing small smid smoothing snoeyink sorting soss souvaine special speckmann springer statist statistica statistical statistics stefan steiger stein streinu strongly struyf sturtivant subsequent survey surveys sympos tardos technique teng thank that theoret theory three threevariable thus time toth toussaint tukey using vegas verlag version violated violations welzl when whether wigderson with workshop would year
http://doi.acm.org/10.1145/982792.982871	63	Dynamizing Static Algorithms, with Applications to Dynamic Trees and History Independence 	abstract acar adaptive adjusting algorithm algorithms annual anti application applications applied arrays attribute august balancing basch bentley binary blelloch caching carnegie carter characterizing classes cohen computation computer computing contraction copenhagen cryptography data decomposable demers department design dietz diku directed discrete discussions driscoll dynamic dynamically dynamization easy editors euler evaluation expression extended feedback foundations frederickson from fully function functional functions further geometric grammars graph guibas harper hartline hash henzinger hershberger history holm hong ieee incremental independent international isaac journal king languages lazy lecture lichtenberg line list made maintaining maintenance making many mathematical mellon micciancio miller minimum mobile modht mulmuley multidimensional naor network notes oblivious operation order overmars pages parallel part pentney persistent polylogarithmic presistence press principles problems proceedings programming pugh randomized references reif renato report reps rocke rooted sarnak saxe schwarzkopf science sciences search searching self separating shuffling siam simplex sleator spanning springer springerverlag static structure structures symposium syntax system tamassia tarjan teague technical teitelbaum thank their theory thirteenth thirtythird time tours transformation tree trees university updating vittes volume wegman werneck with workshop
http://doi.acm.org/10.1145/982792.982795	1	COMPACT REPRESENTATIONS OF ORDERED SETS	acta algorithm algorithmica algorithms almost also alternative annual aragon averaged balanced because bell between binary black blandford blelloch blocked blocking bootstrapping brin bringing brodnik buchsbaum caching cardoze carlsson case catenable caused citation codeword coding compact compression computed computer computing conference constant data described dichromatic dictionaries digital dimensions document double effective elias ended factor faster figure foundations framework functional gigabytes guibas heap here however html http ieee implementation implementations implemented improvement index informatica information integers international interpolative issues japan ject journal july kadow kaplan kaufman lecture levcopoulos library linear lists lookup managing march membership memory merge mergesort merging meshes meshing minimum moffat morgan most motwani much munro natural needed note notes order ordered over page pagerank pages pagh part path performance persistent petersson probabilistic proc pugh purely queues randomized ranking redundancy references reordering report representations results retrieval roundtable runs science search seconds section sedgewick seidel serial sets shown siam sigal significantly simplicial size sizes skip slowdown sometimes sort sorted space standard stanford static structural structure structures stuiver sublinear sundar suspect symp symposium table tarjan tech technical technologies template than that theory this three through thus time tokyo transactions treap treaps tree treebased trees union universal universe using values varying winograd with witten workshop wormald worst
http://doi.acm.org/10.1145/982792.982841	39	Multicommodity Facility Location	aardal algorithm algorithms among annual applications approximating approximation approximations arora arya back balinski berlin capacities charikar client clients coloring combinatorial combining commodity como computer computing conference consider constantfactor constraint cover degree design discrete each facility finding fixed foundations garg graph greedy guha gupta halld hard have heuristic ieee ignored implies improved inequality infocom integer integrated international khandekar khuller kumar linear local location logistics mahdian median meyerson minimized minimizes minimum multicast multicommodity multimedia munagala naor network next nonuniform online optimal optimization over packing pandit plementary problem problems proc proceedings programming programs proof ravi real references relaxation rent representative resource roughgarden routing rsson scheiber science scientific search served serves shmoys siam sinha sinjce solution solutions springerverlag strikes sudan summing symposium tardos testing that theory time uncapacitated vazirani violation vitter wexler where which with zhang
http://doi.acm.org/10.1145/982792.982851	47	Almost-Delaunay Simplices: Nearest Neighbor Relations for Imprecise Points	abellanas able abstracts accuracy acid acknowledgements across agarwal aided akad alexander algorithm algorithmic algorithms alignment almdel almost almostnative also analysis analytical analyze analyzing anatomy angelov angew anlike annealing annu annulus appl application applications applied approximation architecture arise aronov artificial assembly assessing atom aurenhammer averagecase baker bakowies bala bandyopadhyay bank barber based bayesian become berg berlin berretty better bielefeld binding biogeometry bioinformatics biol biology biophys body boissonnat boots brien brookhaven brown building calculations cambridge cammer canadian carnegie carter case cases cates caused cavities centroids chain chains change changes characteristic characterize characterized chazelle chen chichester chomilier chothia circle circles classification clearer code comp comparing complete comput computation computational computations computer computers computing concentric concepts conference conformation conformational conformations constrained constructing contact contacts containing content conti convex cope copies core correlations cutoff data database david debug decoys decreases degenerate delaunay density description design detect deuxieme development diagram diagrams different dill dimensional discrete discriminate discussions distinguishing distributions dobkin domains driven duncan dwyer easy ebara edelman edelsbrunner edgell edition education efficient engineering epsilon equally errors establishment estestvennyh evaluated exact exchange expected experiments faces fast fatty favorable fewer filtered fitting fold folds formes found four fourbody fragments from fukuyama functions fundamensitivity future garcia geom geometric geometry georges germany gerstein give given goodrich graph group grouping gudmundsson guibas gunsteren hammar hannover have helical helices helix heuristic hierarchical high higher hinge histograms hofacker hope http huang huhdanpaa hull hulls hunting hurtado hydrophobic identification identified identify ieee implementation implications imprecise improve improved inaccessible indicates individual indiways information input inside inter interactions internal interpretation introduced introduction investigate janardan jernigan john journal jullien kooperberg kreveld krishnamoorthy leach lead lefebvre lesk letters liang liao ligand likelihood linear local lopez macromolecules many matematicheskih math maximum mcconkey measurement mehlhorn mellon members memoire meshing method metrology minimum miyazawa modelling modified molecular more mornon motif mucke multi munson mutations nakanishi nakano native nauk nearest neighborhood neighboring neighbors nonatomic nouvelles novel nuli number okabe open optimization order otdelenie other overmars oxford packed packing packj page pages pair papers parallelloedres parameter parametres particle particularly patheffective paul peaks pearson peled penn perturbation pittsburgh plane pockets point points polyhedra potential potentials powder press primitifs principles probability problem proc procedure proceedings processing produce properties protein proteins proved prune pseudo quadratiques quantification quantify quickwe radial radii ramos rcsb recherches recognition references regions regular reine relative represented research residue residues results reveal richards rivlin robert robust robustness round roundness sadoc salesin same schemes schwarzkopf science scores scoring second sellation sensitivity separation sequence sequences sets shape sharir sheets shells shermer siam side significance similar simons simplices simplicial simplicity simulated simulation singh site sites smid snapp snoeyink sobolev softw solvent sons soyer spatial specific sphere springer sssr stability stadler standard state statistical stolfi structural structure structured structures submitted subramaniam sudhakar sugihara surfaces surv survey symp sympos systems taylor technique technology term terms tern tertiary tessellation tessellations testal tetrahedra than thank that their them theorie theory these thesis thiele this those threading threshold thresholds time tolerance tool tools total trans transforms triangulation triangulations tropsha tsai tuples turns under undergoing understanding unfavorable univ university univie unweighted using vaisman values verlag vide visualize volume volumes voronoi wako water weberndorfer weighted well were wernisch which width wiley with wodak wohler woodward work worst yamato yvinec zhang zimmer
http://doi.acm.org/10.1145/982792.982880	71	Approximate Local Search in Combinatorial Optimization	aarts abraham abstract ahuja alamitos algorithm algorithms andreas annual applied approximability approximate approximation approximations arkin augmentation ausiello baltimore cambridge capacitated chandra chapter combinatorial combinatorics complexity computational computer computers computing contract cuts department discrete easy equivalent ergun european ffer finding fischer flows foundations fractional freeman garey general generic global graham grant guide handbook hard hardness hassin heuristic http ieee information institute integer interscience intractability johnson journal july karloff karlsson khanna klauck krentel large lecture lenstra letters linkernighan local locally lueker management manuscript massachusetts mathematics maximum means meineche motwani neighborhood northholland note notes npcompleteness npoptimization nserc numerical operations optimal optimization oraclepolynomial orlin other packing papadimitriou paper parametric pardalos partially penttonen permutable primal princeton problem problems proceedings processing programming programs protasi punnen radzik reducibility references research results rubinstein salesman scale scandinavian schmidt school schulz science sciences scientific search series siam simple sloan solutions solve solving spirakis springer ssrn star steiglitz structure sudan supply supported survey sviridenko swat symposium syntactic system techniques technology that theory through time tovey transportation traveling tschel university unpublished vazirani vector verifying versus very views volume weighted weismantel were wiley with working workshop world yannakakis ziegler
http://doi.acm.org/10.1145/982792.982846	43	Graph Decomposition and a Greedy Algorithm for Edge-disjoint Paths	algorithms also approximating approximation approximations argument bound cambridge careful chandra check chekuri claim comp delete deleted disc disjoint each easy edge edgedisjoint edges figure flow follows foundations from generated greedy guruswami hardness have improved improves inductively integer ipco jararemaining khanna kleinberg kolliopoulos lemma main more most near note number optimal packing pair pairs paths problem problems proc proceedings programs prove quadruple references related remaining remark remove repeating results revisited routing sanjeev section shepherd shows some srinivasan stein still stoc such symp that theorem thesis this unsplittable uses using vertices yannakakis
http://doi.acm.org/10.1145/982792.982863	57	Approximation Schemes for Minimum 2-Edge-Connected and Biconnected Subgraphs in Planar Graphs	abstract after algorithm algorithms also althofer annual another appears application applications appropriate approx approximability approximate approximation approximations arora automata because below better between biconnected bicycle bicycles block blocks border both boundedan bounding btained called calls careful case cases cheriyan cles committed compatible comput computer computing concluding connected connecting connectivity consider consisting construction contains context contract contraction cost costs counterpart counting csaba cutvertex cutvertices cycle cycles cyplane czuma decomposition deficiency define defined definition dense dependence dependency depends depth determined development diestel difficult difficulties direction discrete dobkin duce each eared early ecss edge edgeconnectivity edges eliminated embedded endpoints euclidean exponential extend external face faces factor families fast fernandes figure figures finding first forbidden foundations from general generalization generalize genus geom geometric glued goal gomoryexternal graph graphs grigni hard hardness have heavy hence here however icalp ieee illustrating improved indeed induced instance instances intl intro ipco issues jordan joseph jothi journal just justifying karger karpinski klein know koutsoupias krysta languages lemma light lingas lipton lncs longer look main methembedded miller minimum minor minors modify more most multi need nested next node nodes normal number obtained olynomial omit only other pages pair papadimitriou path planar plane plus point polynomial portal portals possible previous problem problems proc programming progress proximation prunes raghavachari ratio recursive references remark remarks replace representing require research resetting respect result resulting robertson safe safely salesman same scheme schemes science sciences separating separator separators seymour shares show siam similar simple sissokho size small soares solution some spanner spanners spanning sparse special specifically springer state step stored subgraph subgraphs subproblem such sufficient super suppose surviving swat symposium system szigeti tarjan that their them then theorem theorems theory these they this time tractable traveling tree trees type types uncompressed used using usual varadara vcss vempala verlag version vertex vertices very vetta visible weighted where which will with woloszyn works workshop york zero
http://doi.acm.org/10.1145/982792.982885	75	Approximate Budget Balanced Mechanisms with Low Communication Costs for the Multicast Cost-Sharing Problem	afkss always ambivalent appear approximate approximation archer balanced behaviour bottomup budget call calling carried change changes closest cluster collusion comput computation compute computed conf connecting connectivity consists constant contributes cost could data down dynamic each economical edge edges embed equals even execute executed factor feigenbaum following follows found frederickson from fsttcs furthermore game games gets hardness height homes ideas increases induction inherits into krishnamurthy leaf lemma level lncs make mechanism meets messages multicast next node note number over overpay papadimitriou pass path proc procedure properties references results root roots running runs sami scaling section send sending sends sent sharing shenker siam simply simulated since smallest software spanning structures summarizes technology that theorem theoret theoretic these this times topology transmissions tree trees under users weight weights when where with works yale
http://doi.acm.org/10.1145/982792.982950	128	Randomized Pursuit-Evasion with Limited Visibility	addition adler afterwards aigner alavi also always ancestor ancestry another appl application applications applied aspect automata automation basar based become before bernhard bipartite both brightwell builds call case catch cated cation cess chatzigiannakis child chwa class clear closer colomb comb combinatoria communication complexity comput computation computational computers computing concluding conference consider contains continue control copnumber cops corresponding cycle define deleted design differential dimension direction disc discrete dismantlable distance distributed does dynamic each easy edges editors efficient ellis erimental establish established establishes european evaluation evasion eventually every exist extend extension fact figure finite first fitzpatrick folding follow follows forest formulations from fromme further future game games garey general geometry gibbs giving gradually graph graphs greedy guesses guibas hakimi happen have height help hespanha hold however hunter hunters hunterwin hybrid icalp ieee implementation information instead international isometric issue johnson journal jump jumps just known kumar label languages lapaugh latombe lavalle leave lemma lick loquium lower lowest maintain maintaining make many math mathematics measures megiddo metho mobile motwani moves must natural needed neighbors networks neufeld never nikoletseas noncooperative note notion nowakawski nowakowski numb number olsder once only orough oulos pages papadimitriou papavassilop paper pappas parent park parsons path played polygonal polynomial porto portugal possible power prandini precisely present probabilistic problem proc proceedings products programming progress proof pursuit question rabbit rabbits racke random randomized reaches reactive ready recontamination reduce references region remain remarks replacing representation required revisits robb robotics sastry search searcher searching separation septemb sequence series shakernia shim showed siam simply since single sivadasan sohler special spirakis springer stealth still stochastic strategies strategy strong studied succeed succeeds such sudb suffice suffices suppose surprisingly symposium than that theory there therefore this time times transactions tree trivial trivially turner unbounded until using verlag vertex vertices vidal view visibility visibilitybased vocking when where whether which while will winkler wins with within work worst
http://doi.acm.org/10.1145/982792.982824	25	Windows Scheduling as a Restricted Version of Bin Packing	access acharya airdisks algorithm algorithms algs ammar annual applications approximation area assignment asymptotic average based behavior bhatia boston bounded bounds broadcast broadcasting case chairman clients coffman combinatorica comm communications complete complexity comput computers conference costs courcoubetis cycles data delivery demand demers dependent design digital dimensional discrete disks dissemination divisible editor efficient engebretsen environment evaluation franklin freeman garey gondhalekar graham guide hard harmonic hochbaum ieee imielinski information international intractability item jain johnson journal juhn kann ladner laylend letters leuker libraries linear matching math mathematics maximum media metropolitan minimizing multimedia multiprogramming naor networks npcompleteness online operation operations optimal packing packings part perfect performance periodic personal personalized problem problems proc processing providers publishing pushing pyramid real references research scheduling schieber seiden servers service services sheu shor siam simple sizes soda solved sudan survey symposium systems tamir technique techniques teletext theorems theory tijdeman time tools transactions tseng ullman using vega video viswanathan vliet weber werth windows wireless with within wong worst yannakakis zdonik
http://doi.acm.org/10.1145/982792.982827	27	On Colorings of Squares of Outerplanar Graphs	acknowledgments adjacent agnarsson algorithm algorithms also always appear appears applied approximation article assignment atlas australian authors balakrishnan base berlin bodlaender borodin both bound bounded broersmo case centers channel chordal chromatic citeseer cnrs coloring colorings colouring combinatorial comput congressus conjecture consider contracting corneil corollary cycle decompositions degree dial diameter discrete distance dortmund dual duchet earlier edge elimination exists face finally finding fsttcs fundamentals generalized generating given glebov graph graphcol graphs grateful greenlaw halld have hedetniemi hence heuvel http hypothesis ieice imada immediate incident induction inductive interest interscience introduction jensen journal kalyana kanari kearney krumke kumar larger laskar leaf lecture linear loque marathe mathematics maximum mobility molloy most neighbors networks nishizeki nonchordal notes number numerantium open orderings orsay outerplanar oxford paris partial paulra planar polynomials powers prasad prenticehall preparation press probl problem problems proof propri radio rama ravi read references remains report repr research rsson salavatipour same sentation series shier show siam small springer square squares sreenivasa steve strong strongly suggesting technical that their them then theory there this thus time toft trans tree trees treewidth university version vertex vertices wegner west when whose wiley wilson with writing yielding yields zhou
http://doi.acm.org/10.1145/982792.982842	40	SRPT Optimally Utilizes Faster Machines to Minimize Flow Time	addresses algorithm algorithmica algorithms also alsuppose amit analyze anderson annual another approximating approximation architectures argue argument assume augmentation avrahami awerbuch azar baruch base because been berman between case chandra charging chekuri clairvoyance clearly competitive completed completion computer computing computsuch construction corollary coulston critical dark determined discrete diswe does edmonds existing exists extra faster first flow following future gorithms gration have holds identical idle immediate implies imply include incurred induction integer interesting jacm jobs journal kalyanasundaram khanna knowledge kumar lack larger leads lecture lemma leonardi less line machine machines manuscript mean metrics migratory minimize minimizing miof more most multi must need negative next nonmigratory nordic norms notes observe oded online open optc optimal optimally other pages paral parallel partial particular patching performs phillips possible potts powerful preemptive prefix problems proceedings processed processor profiles proof proofsketch property prove proven proves pruhs question references regev resource respect result rsrpt sanjeev schedule scheduling science serve show shown shows siam similar simpler single sium smaller smallest some speed spends springer srpt stefano stein stretch strictly such sufficiently suppose sympoopt symposium than that then theoretical theory there this time torng total tradeoff trivially true units uses using value weighted wein well were what with within without would yossi
http://doi.acm.org/10.1145/982792.982798	4	Meldable RAM priority queues and minimum directed spanning trees	ackermann addisonwesley ahuja algebraic algorithm algorithms also amortized amot analysis applied arborescence between boas bock boolean bound bounds branchings breach brodal buckets byproduct camerini case cbms challenging chazelle cherkassky classical clrs combinatorica complexity computational computer computing connection connexion constant construct contraction cormen data decrease degradation deletions derivation design deterministic developments dietzfelbinger dijkstra directed discrete dynamic edge edition edmonds efficiency efficient emde equivalence especially expected faster fibonacci find finding first focs forest fratta fredman further fusion gabow galil general generalizations ggst goldberg good gordon graph graphs hashing heaps heide hopcroft implementation implementations improved industrial inform information integer interest into introduction inverse journal july just kaas kaplan karger karlin karp klein leiserson less lett letters linear lists logarithmic lower maffioli main mathematical mathematics mathematik mehlhorn meld meldable methods meyer minimum monotone more namely network networks news note numerische obtained obtaining only open operations optimization optimum order orlin pages paper particular path paths perfect performance philadelphia possible preserving press prim priority problem problems proc process processing queries queue queues raman randomized range recent references research results rivest rohnert sciences second shafrir shortest siam sigact silverstein simple single sinica small society soda some sorting source space spanning spencer standards stein stoc structure structures support surpassing system systems tarjan technical techniques than that their theoretic theory this thorup time transdichotomous transformation transforming tree trees type ullman undirected union unionfind upper uses using very weights willard with worst would york zijlstra
http://doi.acm.org/10.1145/982792.982908	94	Algorithms for Infinite Huffman-Codes (Extended Abstract)	abrahams algorithm algorithms alphabet alphabets american annual approach april association berger binary binomial chan channel claire code codes coding combinatorial communications computer computing conference constructing construction cost costs david defective dichotomous digits discrete distributed distributions dolev dynamic eighteenth encoding encodings ended energy environment existence finding forests franklin free gallager games geometric geometrically gilbert golin golomb group guessing hassan huffman hwang ieee inference infinite infocom information institute integer joint journal julia july karp kato kenneth kenyon korach length letter linder lossless march merhav method minimum mobile mordecai nagaoka neal nested noiseless november operations optimal optimum parse planning prefix proceedings programming random raymond redundancy references research robert rote saving science search september seroussi sided silence single societies sound source sources statistical stoc symposium systems tamas tarokh testing theoretical theory toby transactions trees type unequal vahid variable voorhis weinberger with yeung young yukelson zeger
http://doi.acm.org/10.1145/982792.982919	103	Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications	acmsiam algorithm algorithmic algorithmica algorithms amer annual appear appl applications approx approximation aspects assoc automata available baltimore barcelona bergen berlin center circuits classes closed colloquium combin combinatorial combinatorica combinatorics complete comput computation computer computing conference crossing cuts deciding decomposable decomposition decompositions deletion diameter diego dimension discrete disjoint distance dominating edge efficient electronically embedding embeddings equivalence euroconference excluded excluding exponential families fast fifth first fixed flow focs foundations francisco free graph graphs hard icalp improved independent international into isaac isomorphism italy journal languages linear lncs local locally mach math maximization maximum minor minors multicommodity network node norm obstructions optimization order outerplanar parameter partial paths planar press problem problems proceedings programming properties providence quickly record reduction references related restricted scandinavian schemes science sciences seattle separator shallow siam single site sixth soda speedup springer stoc structure subgraph surface symposium system taming tech tenth theorem theory time tree trees treewidth twenty vancouver vortex width with workshop xvii york
http://doi.acm.org/10.1145/982792.982892	81	Compression b o osting in optimal linear time using the Burrows-Wheeler Transform	above acknowledgments addition algorithm algorithms analysis annual applications arnavut arrays balkenhol bits block boosting burrows burrowswheeler bzip children class combinatorial compress compresses compressing compression computer conference constants construction corollary corporation damiano data davide deorowicz digital discrete doing economical efforts equals equipment experience experiments fenwick ferragina foundations francesca generalization giancarlo grossi gupta home http ieee improvements indexing inversion journal kurtz like lossless manzini matching mccreight modification moffat most only opportunistic optimal page pages partitions pattern practice principles proc proceedings property ranks redhat references report research satisfies science sciortino second seward shtarkov siam soda software sorting sources space step string strings structures suffix symp symposium takes technical text thank that then this time transform transformation tree trees used uses vitter volume wheeler where which wirth with within without would
http://doi.acm.org/10.1145/982792.982904	91	On the Numb er of Rectangular Partitions	acknowledgements added after aided algorithmica algorithms allowed also amer applications approaches approximation arranged asia automation available baltimore baxter berkeley between bijection block bootstrap bounds building calheiros california cambridge canada cardei catalan chen cheng chiba china chung circuits combin combinatorics communication commuting completion complexity composite computation computational computer computing conclusion conf conference connections constrained constraints control corner corollary decompositions depends describe design dimensions direct discovered discrete discuss discussed dissection dissections distinct dong dulucq during edge effective efficient electronic encyclopedia enumerative ercolation ermutations eshcar exact existence experiment fast feel figures finally fixed floorplan free from fujiyoshi functions furthermore generalized generating geometric geometry gonzalez graham guibert guillotine hard heights heuristics higher hoggatt hong however http huang hypotheses ieee improved induce integer interconnect interior japan jose kajitani kaplan kings kleiman kmst layout length lerton levcopoulos line lingas list lucena manuscript many mapping maps math mathematics meneses mention mentioning minimum mitchell monotone monticello msri much murata networks njas note novel number numbers olynomial ontario open optimal optimization original orplan pacific pair paper part partition partitioning partitions permutation permutations physical pinter placement point pointconstrained points polygons present presented problem problems proc programming quarter quasi quest questions rectangle rectangular rectilinear references related report represent representation representations research restricted revisiting rgnlp right rivest sakanushi scheme schroder section sequence sequencepairs sequences series shamir shapiro shing show siam simple simpler slicing solutions sonoma south souza stanley state stephens subdivisions symbolic symp system systems tale technical thank that then theory there this tianjin time tool topological trans trees university used variant vegas watanabe west what when which with worth yorktown zheng
http://doi.acm.org/10.1145/982792.982860	55	Torpid Mixing of Simulated Tempering on the Potts Model	acknowledgments adsorbing algorithm algorithms always amer analysis ancestral annals annealing applications applied approach approximate assoc authors birkhauser borgs calculations cambridge carlo cayley chain chains chayes chemical christian circuits claire comparison complete computation computer computing convergence cooper coste counting decomposition diaconis discussions disjoint disorder dissertation does dyer elchanan equation europhys fairfax fast focs foundation foundations frieze gellatt generalized generation geyer gore graph graphs grids ieee inference information interface jennifer jerrum journal kenyon keramidas kirkpatrick lett likelihood machines madras marinari markov martin math maximum mcmc method metropolis mixing monte mossel narrow optimization order parisi philosophical phys physics potts preprint probability proc proceedings process properties randall random rapidly rate references reversible rosenbluth saloff sampling scheme science simulated sinclair society some staircase state statist statistical statistics structures swapping swendsen symposium teller tempering tetali thank theorems thompson tion torpid transformations uniform univ useful using vecchi vigoda walks wang with york zheng
http://doi.acm.org/10.1145/982792.982901	88	An Exact Sub exp onential-Time Lattice Algorithm for Asian Options	abate accurate aingworth algorithm algorithms american analysis annual approach approximations asian asset australia average banking barrier based bessel blackwell bounds boyle break broadie cairns cambridge carlo comparison complexity computation computational computing conference connecting continuous contracts control converge convergence currency dependent derivatives desired develops dilip discrete distribution distributions domino dramatically duffie dynamic dynamics economic economics effect efficient engineering error estimating european exact exponential extremely eydeland fast finance financial first flexible forsyth gamma geman given glasserman guaranteed huang hull integrality international interpolation inversion journal kemna klassen laplace lattice lattices least levy lognormals longstaff lyuu management mathematica mathematical mathematics merton method methods milevsky mind modeling money monte motwani multiresolution notion numerical oldham option options orsa paper particularly path pathdependent perpetuities posner press price prices pricing princeton principles probability proc procedures process processes proof proposed quantitative quick rate reciprocal reduce references researches review revised rigorous risk ritchken ross rubinstein sankarasubramanian schwartz science security shaw show siam simple simplified simulation squares stochastics stock studies subexponential symposium that theory this time transform transforms trinomial turnbull university uses using valuation value values valuing vetzal vijh vorst wakeman wang white whitt with zvan
http://doi.acm.org/10.1145/982792.982817	19	Optimal Space Lower Bounds for all Frequency Moments	acknowledgment algorithms alon annual appear applications approach approximating approximation arguments asymptotic author available base bases berkeley binary bounded bounds checking chervonenkis column combinatorics communication comparing complexity computation computational computations computer computing conf conference constant continuous converges cormo counting data databases datar degree dependence dewitt discussion distinct dpwo druff each elements enumeration equation events foundations frequences frequency given graphs hamming handling helpful hence http ieee indexes indyk information international interscience jayram joins jolet jority journal kremer kumar large least lower luca main martin massive matias matrices maximum mckay metho method moments muthukrishnan naughton nisan norms number oneround only ound ounds parallel piotr practical probabilistic probabilities probability problem proc proceedings proof random randomization randomized references relative schneider science sciences seshadri simulation since sivakumar skew space spencer statistical statistics stream streams such sufficiently surprise symposium symposum system szegedy techniques terms thanks that their theorem theory there thesis through thus tight total trevisan uniform upper using values vapnik very vldb wanless which wiley with workshop wormald york yossef
http://doi.acm.org/10.1145/982792.982916	101	A deterministic near-linear time algorithm for finding minimum cuts in planar graphs	adjacent after algorithm algorithms alon always another applied applying approach appropriate assigning assume because both bound call called cannot claimed clifford closed colorcoding computation computer conquering contain containing contains corresponding corresponds cross crosses crossing curve cuts cycle david decomposed definition degree denote determined determines determining different dividing dual each edge edges either even example exists face faces fact faster figure find finding flow flows following follows formed forms found fractions from fundamental given gives graph graphs have henzinger implies inside into jacm journal karger karsten klein last lemma lies linear lipton main mathematics maximum minimum monika more most must near networks node nodes noga nontree note noting number once only other outside partitions path paths philip planar primal problem proof prove proves raphael recall references remains result richard robert runs sairam satish sciences separates separating separator shortest show siam side sides similarity since single sketch some source spanning specifically stein step subgraph subgraphs subramanian system tains tarjan than that theorem therefore this three thus time times tree triangulated twice using want weights weihe where which yielding yuster zwick
http://doi.acm.org/10.1145/982792.982806	10	Variable Length Path Coupling	aldous algorithm algorithms analysis anil annual appear application balls berg bilities bins body bounded bounds brouwer bubley chain chains coloring colorings colouring comput computer conductance constantes convex coupling czuma degree delayed dependence dimer doeblin dubhashi dyer dynamics elementary estimating expos extension fini finite five foundations frieze gebiete generating girth glauber goldberg graph graphs greenhill griffeath groups hayes high improved interbalkanique jerrum kumar kutylowski lattice least lecture lower markov markovian math mathematics maximal maximum minaire mitzenmacher mixing model molloy monomer negative nombre notes number path permutations phys points probae procedure proceedings proper proving ramesh random randomly ranjan rapid rapidly references sampling science siam simple simples sinclair springer structures study symposium tats technique theorie theory union verlag verw very vigoda wahrscheinlichkeitstheorie walks with xvii
http://doi.acm.org/10.1145/982792.982873	65	LAND: Stretch (1 + ) Locality-Aware Networks for DHTs	abraham access accessing addressable adversarial algorithms annual another applications approach approximate april architectures atomic august aware awerbuch azar balakrishnan bartal based bawa berkeley bertinoro building butterfly caching cambridge center chand chord commerce compact computer computing conference consistent content contentaddressable continuous copies data degree directions discrete distance distributed division dobzinski drushel dynamic efficiency emulation engineering environment factor fault february felber fifteenth find finding fraigniaud france francis fudico future gauron gavoille generic gengler growth handley hash hashing hebrew hildrum ieee ifip infrastructure international internet ipdps iptps italy january jaraman jczak ject jects jerusalm joseph journal july june kaashoek karger karp koorde kubiatowicz land largescale lehman leibnitz leighton lelism levine leware lewin lncs locality location lookup lynch malkhi manku march metrics midd mobile montreal morris name naor nearby nearest neighbor neighbors network networks nice ninth novel november october optimal oracles overlay pages panigrahy paper paral paris pastry pavlov peer platforms plaxton podc pomc position press principles proceeding proceedings processing protocol protocols raghavan random rata ratnasamy references relieving replicated report resolution restricted richa routing rowstron ruhl scalable scenarios scheme schemes school science service shenker sigcomm simple small spaa space spots stoc stoica stretch symphony symposium systems table tables tapestry technical technologies tecnical theory third thirteenth thirty thorup three tolerant trees univ university usenix viceroy volume wide widearea wieder workshop world worskhop zhao zwick
http://doi.acm.org/10.1145/982792.982821	22	New Approximability and Inapproximability results for 2-dimensional bin packing	above algebraic algorithm algorithmica algorithms approximate approximation aptas asymptotic benefits bins boston bounded bounds brazilian caprara case chekuri chin choose chung claire coffman combinatorica combinatorics complete complexity computational computer computing correa covering crisik cube described difference dimensional directly discrete distributed easy editor editors efficient epstein eric extends extension fernandez ferreira fiat fixed focs foundations garey gives graphs hardness harmony hochbaum information into jansen johnson journal kann karmarkar karp kenyon khanna kohayakawa letters leung level line linear location lueker makespan matching math matroids maximizing maximum methods minimization miyazawa multi multidimensional networks nphard online only open operacional optimal oriented packing pages paral performance pesquisa petrank polynomial problem problems proceedings processing programming ptas publishing raghavan rectangle references remila scheduling scheme schemes science seiden sequencing sevastianov shops siam soda solved space square squares state stee strip survey symposium tarjan that there these this time twodimensional vector vega wakabayashi within woeginger wong yield young zhang
http://doi.acm.org/10.1145/982792.982870	62	Interpolation Search for Non-Independent Data	access acta addressing against algorithmic always amortization amortize amortized analysis andersson avni avoid because between bins bounds build cacm case change changing charge charged charging complexity comput cost costs currently data deletions desired development does dynamic element elements establish files finally focs follows fore from generated george give global gonnet hence icalp immediate increasing inserting insertion insertions interpolation itai journal july known least linear mattsson maximum mehlhorn minimum nonuniformly number occurs operation ordered original pages performing perl peterson priori proceedings proof raises random rebuild rebuilding rebuilds rebuilt references remaining rogers scheme search searches searching separation sequence siam single size standard storage structure such table that then theorem therek these time tsakalidis unindexed updates value which willard with without worst yields
http://doi.acm.org/10.1145/982792.982921	105	Testing Bipartiteness of Geometric Intersection Graphs	acknowledgements advances agarwal algorithm algorithmica algorithms along also analysis applications approach approximate april arbitrary area arxiv asano balls barcelona based battista bends between bichromatic biconnectivity bipartiteline bipartiteness bottom bounds boxes callahan cambridge carnegie ccrstraightforward centre chain chan chazelle chromatic clark clique closest coarseness colbourn colorability coloring comb combinatorics commun compgeom complete completeness component components comput computatational computational computer conclusions conf connected connectivity constant constructs contemporary control crossing data davidw december decomposition decremental degree details detection determining deterministic difficult dillencourt dimensions directions discrete disk disks drawing drawn dyby dynamic each eades easier edelsbrunner edge edges efficiently efpolynomial embedding enfels entire eppstein erickson euclidean euroconf evidence existence faster ficiently figure finally find finding formed four from fully fundamenta future gadget galil garey general generic geometric geometry graf grant graph graphs grid guibas hall hamburg hard have hershberger hirschberg holm hopcroft hopkins html http hutchinson hypercubes imai imor inform informaticae intersecting intersection investigated italiano january ject jects jeffe johns johnson july june kainen kinetic kinetically krznaric lecture lengths lerton lett levcopoulos lichtenberg line linear logarithmic lower maintained mansfield matem math mathematics maximum meeting mellon might miller minimum more most mutually naive namically nearest neighbor ness nissenzweig noma nonplanar notes number objects omit ones only optimal optimization orthogonal other over packings pair pairs papers part partitioning philos planar plane points poly polygons possible potential prentice problem problems proc proof properties proved provide provided pubs radius randomized range recerca rectangles rectangular reduction reductions references relation relatives reof replace representation representations scale schnyder school schwarzkopf science search searching segment segments separated separating separators september setting several shermer short siam similar simple simplified single size soda some spanning sparsification speeding speedups sphere spheres springer squares stockmeyer straight strictly structure stumpf such suitable supported suri survey symp tamassia technique teng tesselation test testing than that them theorem theoretical theory there thesis thickness this thorup three thurston tica time times tollis tree trees triangles triples types uiuc unified unit univ upon usefor usyd vavasis verlag vertex vince visualization welzl which with wood work zhang
http://doi.acm.org/10.1145/982792.982932	113	Point Containment in the Integer Hull of a Polyhedron1	acad algorithm algorithmica algorithms annual appear association basis battista bound calling calls chazelle check choose clarkson combinatorial combinatorics comput computation compute computing concludes constant constraint constraints containingsimplex containment corner corners cost cuts dimension dimensional discrete done each editors eighth eisenbrand equivalence european expected fast faster fixed from geom geometric grotschel harvey have hull hulls hyperplane indivisibilities integer international isaac iterate john journal laue least lengths linear lncs lovasz machinery mathematics matouek mccormick multiprocessor nential number observation only operations optimization orleans over pages point points polygon polyhedron polynomial problem proc procedure proceedings production programming proof recall references requires research scarf scheduling schrijver separating separation sets sharir shown shows siam simple simplex size small smallest smallwood solved spieksma springer steps structure subexpos subset symposium that theorem theory these this thus time times together triangulating using variable vegas violates violation volume welzl when wiley with york zwick
http://doi.acm.org/10.1145/982792.982858	53	Slow mixing of Glauber dynamics for the hard-core model on the hypercube	adjacent algorithms alorithms analiz antichains appear appl approach approximate approximation argument based bipartite borgs boundary cardinality carlo chain chayes closure combined connected constant convergence core counting crucial cube define denotes discrete diskret dynamics each easier fact fast focs frieze from galvin given gives glauber graphs hamming hard have homomorphisms idea independent inequality integration introduced isoperimetric jerrum kahn least luby markov matching math method metody mixing model monte must note nphard number ordered partially perfect phase physics problems random ranked references russian sampling sapozhenko sets shows similarly simple sinclair smal small some statistical structures subsets such tetali than that theorem there this torpid transition translation turn unless vertices vigoda where which with work
http://doi.acm.org/10.1145/982792.982810	14	Exponential Bounds for DPLL Below the Satisfiability Threshold	achlioptas after algorithm analysis assf assigns backtracking beame bounds chao clause clauses complexity constant decreasing denote differential dpll during equations every examples expected formula franco generalization given hard heuristics inform input jacm lemma length literal lower makes many molloy number peres probabilistic problem proof random references residual resolution satim satisfiability selection sharp signments stays step steps stoc szemer that then threshold thus time unassigned unit unsatisfiable value variable variables will with ying
http://doi.acm.org/10.1145/982792.982895	83	Randomized k -Server Algorithms for Growth-Rate Bounded Graphs	achlioptas adding algometrical algorithm algorithmic algorithmica algorithms amortized amos andrew anefficiency anna annual application applications approximating approximations arbitrary assoc avrim bartal better blum bollob bound burch caching carl ceedings charikar chrobak clustering combinatorica communicanual comp compt comptuer comput computation computer computing conclude conjecture costadv csaba daniel danny date decomp dimacs directly etitive fakcharoenphol fiat fifth follows founda foundations from general geomeanalysis graphs have information irani journal karlin karloff karp koutsoupias larcostadv lawrence lemma line linial list lodha london lower luby mach manasse manor marek mcgeoch mendel metric metrical metrics more moses naor next noga obtain octob olylog osition ound ounds over page pages paging papadimitriou period periods phenomena probabilistic problem problems proceedings proof prorithms rabani rabinovich ramsey ramseya randomized references related rical richard rics rudolph rules sachin saks sandy science seiden server servers shall siam since sleator snoopy some space spaces steve strongly summing symposium systems talwar tarjan task technical terms that theorem theoretical theory thirty tight tion tions tomkins tree unfair weighted weights with yair young
http://doi.acm.org/10.1145/982792.982957	134	The Power of Basis Selection in Fourier Sampling: Hidden Subgroup Problems in Affine Groups	abelian above abstract acknowledgements acmsiam additive advanced alexander algorithm algorithms almost amnon annual appear applications archive atlanta basic beals been bell bernstein beth body bound bounds california cambridge cannot cardinality character characters charles class clear clearly collection completing complexity computation computer computing conrad considering consisting consists constant construction conversations corresponding coset cosets course cristopher cyclic daniel define definitive denote detail diego difficulty dihedral discrete discussed doing done each editor efficient element elements emmanuel encyclopedia eprint ethan ettinger even exponential factoring factorization field fields fifth find finite first following foundation foundations fourier frederic friedl fulton function functions fund gauss generalized generator generators generic georgia given graduate grants grateful greg grigni group groups hales hallgren harald harris have helpful hidden identify ieee igor improved information inner instances institute integers introduction iterate ivanyos january jean joseph journal jozsa katalin knill konyagin kuperberg left leonard level lidl likewise linear lisa logarithms magniez mark martin mathematical mathematics mechanical michelangelo mika miklos milius modulo monica moore more msri multiplicative nfortunately niederreiter ninth nonabelian noncommutative nontrivial normal notation note notes number obtain october onential only orbit order orleans orthogonal otherwise over pages paper paso peter physics pierre poly polynomial polynomialtime powell power pranab precisely preliminary press prime primitive print problem proceedings products proof provided quant quantph quantum qubic queries query reconstruct reconstruction references remains report representation representations representative require research result richard robert rockmore roetteler root rotman rudolf russell sally sampling santha schulman science sciences sean sergei serre sets shor shparlinski siam simon simplified simply since size solution solving some specific spectacularly springer states study subexponential subgroup subgroups such sums superpolynomial support symmetric symposium taken tashma technical technology texas texts than that their then theorem theory thirty this thomas time times tracts tracy transform transforms translation treatments tteler twenty umesh unity university unordered using values vazirani verlag when where william with work would yields
http://doi.acm.org/10.1145/982792.982801	6	A New Algorithm for Normal Dominance Constraints	about adjoining algorithm algorithms althaus amsterdam annu annual application aspects association axiomatization backofen between biconnectivity bodirsky bridging comp complexity comput computational computer configuration connectivity constraint constraints copestake csli describing descriptions deterministic discourse dominance draft duchier dynamic edge efficient finite first fleck flickinger formalisms from fully gardent grammars graph graphs hindle holm information institut intel introduction issue journal july koller kutz lambda language lichtenberg ligence linear ling linguistics lnai lncs logic logical loquium marcus maxplanck meeting mehlhorn minimal minimum niehren obtaining order pages pennsylvania philadelphia pollard polylogarithmic predicate problem proceedings pure recursion references rogers saarbrucken science semantics sept shanker soda spanning special stacs structures submitted sympos symposium talking thater their theoretical theory thiel thorup time tree trees treinen underspecification university unplugged vijay volume webber workshop
http://doi.acm.org/10.1145/982792.982836	35	The Hyperring: A Low-Congestion Deterministic Data Structure for Distributed Environments	achieve addressable algorithms alternative announcement appear applications approach architectures area arguments aspnes aumann awerbuch balakrishnan balanced based beame belong belonging belongs bender bounds brief butterfly chernoff chooses chord closest combination come communications computation computer computing conclusions concurrent conference congestion content continuous control cormen creates currently data decides delete destination deterministic dijkstra discrete distributed distribution does drawback druschel dynamic emulation enters environments erations even fault fich first florida focs following forward foundations francis goodman graphs guided hagerup handley harvey help hence highest highly hill hopkins http hypercube hyperring ieee ifip informatics information informatique infrastructure insert interconnection interesting intermediate international internet into introduction jczak ject johns jones joseph kaashoek karger karp keep krishna kubiatowicz large lecture leiserson letters level leware lists locality location lookup lowcongestion malkhi mathematics mcgraw messeguer midd mobile morris munro name naor near need network networks node notes novel once only operation operations optimal overlay pages papadakis paper parallel pastry paul peer peerto platforms plaxton podc possible practical predecessor presented press principles probabilistic probability problem proc proceedings processing properties pugh rairo random rata ratnasamy reach reached reaches references remove report request requests resolution resp result results ring rivest route routing rowstron saroiu scalable scale scheideler science search sedgewick self service shah shasha shenker show siam sigcomm similar simply skip skipnet soda spaa spinger spite stabilization stoc stoica storing strategies structural structure structures suffice suitable supposed symp symposium systems tapestry technical techniques that theimer theorem theoretical theorique theory thesis they this tods tolerant tour transforming trees uniform uniformly universal university usits viceroy vishkin wagener whether wide wieder with wolman work workshop would zhao
http://doi.acm.org/10.1145/982792.982864	58	Approximation Schemes for Metric Bisection and Partitioning	according acknowledgements adopted ajust alan alfonsin algorithm algorithme algorithmic algorithms alon also american analogously analysis another appear appendix applications apply appropriately approximability approximate approximation arbitrarily arora association assume average bennet berman better between biased bisection bounded call cardinalities case change choose claire classes clustering combinatorial combinatorica compared complete complexity comput concentration connection consider constant constraint constraints construct cost create cuts dahlhaus define defined defines degree denote dense dent depending description different disconnect discrete disctrete discussions distances distribution done each easily eccc edge embedded ends equal estimate even every example exhaustive extend extension feige fernandez figure final find finding finite fixed focs following follows fractional frieze from given goldreich goldwasser graphs guess habib hard hardness have hochbaum hoeffding hybrid icalp ieee independently indepenwe index induced indyk inequalities instances integer intersection into items ject jerrum johnson journal kannan karger karpinski kenyon krauthgamer last learning left lemma lems linear lncs manner marek mark mathematics matrices mcdiarmid methods metric mfcs minimization minimize minimum minpartitioning modifying moreover moving multiterminal multiway natural near note obtain ommitted once optimal optimization optimum other others otherwise output papadimitriou part partition partitioning partitions parts peres placing pointing polylogarithmic polynomial probabilistic probability probdone problem problems proc program programming proof property propriately ptas ptass quick rabani ramirez random randomized ravi reduced reed references regularity relations reliable remaining rename renaming repair replaciv report rounding sample sampling saran scheme schemes schulman sciences search section sequence seymour showing siam size sizes smaller smallest solution solve some space spaces springer statis statistical step stimulating stoc structures sublinear such sufficient sums system take technical terminal terminals testing than thank that them then theorem there these this those tical time together towards twice unbalance used value variables vazirani vector vega version vertex vertices weight weighted weights what which with within yannakakis yield yuval
http://doi.acm.org/10.1145/982792.982889	78	Approximate Nearest Neighbor under Edit Distance via Product Metrics	acmsiam algorithm algorithms although amenable andoni annual appear appeared appears approximate approximation arrangements arya assume attractive automata background bounds case charikar clarkson closest colloquium communication complexity computation computational computer computing constant cormode could cpsv curse data deza diagrams dimensional dimensionality dimensions discrete distance distortion document edit efficient embedding embeddings even evidence exact exchange exponential factor fifth foundations frechet geometry gupta high however hyperplanes imply improve indeed indyk information interesting international into journal kleinberg kushilevitz languages latter linear location lower match matching maybe meiser metric metrics more moses motwani mount moves much muthukrishnan natural near nearest neighbor neighbors netanyahu ninth norm normed obtain only open optimal option orthogonal ostrovsky over pages panigrahy partial paterson peled piotr point possible preliminary problem problems proceedings product programming proximity queries query question rabani raises randomized range raskhodnikova reduction references related removing replacement requirements result rina sahinalp science sciences search searching sequence setting several siam silverman simply size solve somewhat space spaces still string structure subset such symposium system techniques that then theory there thirtieth this tight towards twentyninth under unlikely uses version vishkin voronoi when with work would
http://doi.acm.org/10.1145/982792.982894	82	Dimension Reduction for Ultrametrics	acta algorithmic almost alon analysis applications applying approximating approximation arbitrary bartal bound brinkman charikar claim close combin combinatorica combinatorics conclude conf constant convex dimension dimensional discrete dlca eddings edition embedding encer enough european events extensions extremal fakcharoenphol figiel focs follows geometry graphs high hilb indeed independent inequality into john johnson last left lemma lindenstrauss linial lipschitz london mappings math mendel method metric metrics milman modern naor note odies ossibility ound overwhelming pages partitioning phenomena press probabilistic probability problems proc proof prove rabinovich ramsey reduction references results second sections since some sons space spaces spherical stoc taking talwar terms that there therefore this tight tree ultrametrics union valid when where wiley with york
http://doi.acm.org/10.1145/982792.982928	110	On Contract-and-Refine Transformations Between Phylogenetic Trees	abel acknowledgment algorithms allen also analysis analyzing annals annual anonymous applied approach archaelogical associates asymmetric bayesian below better between bioinformatics biology biosciences bollback briefly building buneman call carlo chain change chapter cherries cherry cladistics classification climbing combinatorial combinatorics company comparing comparison complexity composite concerned consensus constructing construction contains course create cycle dasgupta datasets defining discovery discrete dissimilarity distance distances edition elementary entitled evolution evolutionary felsenstein fitch forming foulds from ganapathy generalization goloboff graph hall hamiltonian have hein hence hill hillis historical huelsenbeck identical impact importance incompatibility induced inference interchange international islands jiang journal labeled labels large larget leaf leaves likelihood london lovasz maddison markov massachusetts matching mathematical mathematics maximum measures median metrics minimum model molecular monte most mrbayes multiple nearest neglecting neighbor neighbour nielsen northholland olson operations optima optimal optimization pages pair parsimonious parsimony phillips phylogenetic phylogeny plummer pointing proceedings proof publishing ramachandran reasonable recovery referee reference references relies representatives robinson ronquist sankoff science sciences seaches second sequences shown siam siblings simon sinauer sketch society solutions specified steel subsets subtree such sunderland swofford symposium systematic systematics thank that their them theoretical theory third three thus times topology toward transfer tree trees tromp valency wabi waddell wang warnow will window with workshop zhang zoology
http://doi.acm.org/10.1145/982792.982940	120	Minimizing Migrations in Fair Multiprocessor Scheduling of Persistent Tasks	abdelwahab across activities adler affinity ailamaki algorithm algorithmica algorithms allocation allow allowing although amount anderson annual aperiodic applications april architectures arriving autonomic baruah borrowed bound bridging bruno carpenter case chandra cheriton chow cohen completing computer computers computing conclusion conference constant constraints deadline definition dependent design deterministic distributed domains duda dynamic easily eclipse efficient enter environment equal euromicro evenly exit fair fairness fast finally fixedpriority flexible framework gabber gehrke general given guaranteeing hard harizopoulos have holman http ieee implementation independent information integrating international interprocessor ipps january ject jeffay jobs jones journal june laboratory latency layland letters line machines mangement manifesto march mayer memorandum migration migrations minimization model modified more multiple multiprocessor multiprocessors multiprogramming near newly note notion only operating operation operations optimal optimizing ozden paral periodic persistent perspective pfaff pfair plaxton practical practice predictable presented principles priority process processing processor program progress proportional proportionate providing purpose quality real realtime recurrent recurring references report require requires research reservation reservations resource resources restricted rosenblum rosu rtss sapuntzakis schedular scheduled scheduling schieber science sensitive server service share shares shenoy shown siam silberschatz simple single sosp space srinivasan staged state static stoica stride sudan suitable summary supporting symp symposium system systems tasks technical technology than that theory these this threads time towards under uniform usenix varvel versa vice virtual virtualtime waldspurger weihl with work workshop
http://doi.acm.org/10.1145/982792.982946	125	Routing and Scheduling in Multihop Wireless Networks with Time-Varying Channels	above achieved adaptation adaptive addition admissibility admissible adversarial affected after again aiello algorithm algorithms allocation along also alternative amount analysis analytic andrews annual anshelevich appear applications applied applying april assumption asymptotic automatic awerbuch bahia balancing based beam been before believe berenbrink between borodin bound bounded bounds brazil brinkmann bursty canada capacities capacity capcity case cdma centralized challenging channel channels choose chosen clear combining communication communications computer computing condition conditions conference congestion congress constrained control dallas data december decisions define defined defines definition dependent derive discrete distributed diversity does dual duality dynamic dynamics each edge efficiency either else endix ephremides equals experiences exponential fair fairly feasible february fernandez first flows following forward foundations francisco full fully function general gives goel gradient grossglauser gupta have hence high hold holds however ieee implied increases infocom information initialized injected injection injections input interesting interference international into iteration jalali january japan journal june kempe kleinberg know known kumar kumaran kushilevitz kushner labs larger last lemma lerton less link load magazine maximum maxmin memorandum methods mixture mobility model models modiano montreal more most much multi multihop multiple multiuser neely network networks node nodes note november number observation obtain october once only open optimal ostrovsky other over packet padovani pages panka particular passes path personal piece policies polynomial power predetermined preparation preserving primal probability problem proceedings properties proportional providing pseudo pseudoinjection quality queued queueing rabani radio raghavan ramanan rate rates real reasonable receiver receivers receives recurrence references remark repeatedly require respect rinf rohrs rosen routing rsup rule salvador sarkar satellite satisfies scaled scaling scheduling scheideler science second section semiannual server service setting shakkottai shared sharing show siam signal simple since size solution source speed speeds spring stability stolyar straightforward strategies strength submitted subset sudan summing symposium system systems tassiulas technical technology teletraffic terms than that then theorem theory there therefore think this through throughput time times timevarying together tokyo total traffic transactions transform transformations transmission transmit transmits transmitted traverses under undoing user value vancouver variable varying vectors vegas vehicular vijayakumar what where which whiting williamson wireless with would york zhang
http://doi.acm.org/10.1145/982792.982850	46	A Time Efficient Delaunay Refinement Algorithm 	algorithm algorithms analyses angles annual applications applied austin available barbic berg berlin bern boivin burch cambridge canad carl carnegie case cell charles chew clemens clifford clrs cmucs comp comput computational computer computers computing conf considered consisting constrained constructing construction contribution control cormen cornell daniel david dbvkos delauany delaunay department diagrams dimensional dinesh ding discrete discussions domains dynamic earlier edelsbrunner edition editors electronic engineering england enumerable eppstein euclidean example first focs foundations fourth frank from fully generation generator geom geometric geometry gilb gooch good grading graz guaranteed hill hong hwang incremental inputs insertion international introduction jernej john jonathan journal kadow kong kreveld kwang lecture leiserson like line louis maintenance manocha manuscript marc mark marshall mcgraw mellon mesh meshes meshing ming mount national noel notes numb obstacles octob ollivier only optimal oratories order osium otfried overmars pages parallel paul pennsylvania pittsburgh points posterpresentation press proc proceedings provably quadratic quadtrees quality references refinement revised richard rivest ronald roundtable rupp sandia school schub schwarzkopf science scientific segments seidel septemb series shang shanghua shewchuck shewchuk siam simplicial sixteenth size small soda spielman springer stein symp symposium system technical teng thank their theory thesis thomas topology towards triangle triangular triangulation triangulations triangulator univ university verlag volume voronoi walkington wang wayne well which with workshop world would york
http://doi.acm.org/10.1145/982792.982832	31	Retroactive Data Structures (extended abstract)	acknowledgments alejandro algebraic algorithm algorithms amortized analysis anonymous association authors automata backtracking balanced bender bentley boca bose cardinal carnegiemellon cell chan chapter class classic colloq comments commun complexity comput computational computer computing confluently convex data database decomposable dept discrete discussions disjoint driscoll dynamic editor editors efficiency fiat fleischer foundations fredman gehrke geometry good goodman handbook helpful hill hull international january jean journal kaplan klee languages lecture leeuwen linear lncs location lopez machinery maintain making management mannila manuscript mcgraw michael munro nearlogarithmic nonlinear notes operations ortiz orwell pages persistent planar point press probe problem problems proc programming prosenjit ramakrishnan raman raton rectangle referees references require rourke saks sarnak saxe science sciences search searching sets should siam signet simple sleator snoeyink sorted static strassen structure structures succinct symp symposium syst system systems tables tarjan thank theoretical theory time transformations tree trees ukkonen union university unpublished update using volume washington westbrook which with workshop worstcase
http://doi.acm.org/10.1145/982792.982845	42	Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms 	able acknowledge acknowledgments alenex algorithm algorithmics algorithms allpairs amato among analysis andstring anonymous answer applicazioni approach arbitrary around ball bandwidth based birkh bounded business bytes cache caspur cattaneo cherkassky closure cocoon comments computation computational computer computing connectivity connexion consider consorzio debugger decreasing deeply deletion demetrescu dense derived deserve developer different digraphs dijkstra directed distances dynamic each ects edge edges editors effect empirical engineering ensource erimental erts evaluation even example experimental experiments explicitly faruolo fast faster federico ferraro finding focs fortz fredman frigioni from fully further generalization generous goldb graph graphs greene heaps hidden highway historical hong hospitality http ieee implementation improved increasing incremental incurring indebted indeed infocom inputs instance instances internet interuniversitario ioffreda isaac issue italiano iyer journal just karger king knuth koller larger lecture length limiting line linux locally logarithmic london loubal machines maintain maintaining make makes many marchetti massaioli math mathematics matrix maximum memory miller minimum model moret most murchland nanni narvaez nethercote network networking networks nodes noon note notes number numerische onacci ones only optimization optimizing ospf ounds overall pages pair pairs paolo pasqualone path paths petrillo phillips platforms plus practice problem problems proc procedure proceedings programming queries radzik rahul ramalingam real record reduces referees references reps requires research revealed ricerca road robust roughly saving scanned school science seems seward sewardj shaefer shiloach shortest siam side since single size small soda solve solved some soon source spaccamela space spanning static stoc study substantially supercalcolo swap system tarjan technical tested than that their them theoretical theory these this thorup thus time today total traffic transactions transitive transp transportation tree trees trick tzeng unit universita usage useful user using valgrind very wall weights were which with without yeung zaroliagis zhan
http://doi.acm.org/10.1145/982792.982942	122	A Fast Approximation Scheme for Fractional Covering Problems with Variable Upper Bounds	abstract accelerating acknowledgment acmsiam adding algoo algorithm algorithmic algorithmica algorithms along also amer analysis annual appear appl applications approach approximate approximately approximating approximation available belgium berlin best between bienstock bixby blocks both bound bounded bounds boyd calls capacitated capacity carr catholique center change cheriyan cherkassky choice choosing class columbia combinatorial combinatorica commodities complexity comput computational computations computer computing concurrent conference connected connectivity constraints constructing convergence convex coordination corc core corollary cost coupling course covering cuts decomposition definition derigs design determined deterministic devoted directed directive discrete discussion dual duality each econometrics edge editor editors element endix example execute experiments extended fact factor fast faster feasibility feasible feedback final finally finding first fleischer flow flows following follows forest found foundations fractional fractionalcoverub from function gaps garg generalized goldberg gomory graph graphs grigoriadis group groups gusfield have hence ieee implementation implementing implies imply independent indust inequalities inequality inner institute integer integrality international into investigation iteration iterations iterative jain january jective journal karakostas karger karzanov khachiyan khandekar klein konjevod large lected lecture leighton lemma leung linear lines loop louvain lower makedon many math mathematical mathematics matula maxflow maximum meier melkonian mercado method methods minimum mixed modified monograph moscow most multi multicommodity multiple neal nemann network notes number oldham once oper operations optimal optimality optimization oracle other over packing pages pair papers parallel partitioned performed phase phases phillips plotkin polylogarithmic potential practice price problem problems proc proceedings program programming programs property providence publication push radzik randomized ratio ravi recall references relabel related report research rewrite rithms rounding routing russian satisfies scale schemes science sciences selected september sequential series shahrokhi shmoys show shows siam simple simpler since solution solving sparse spent springer stein steiner steps strengthening studies subgraphs submitted symposium system systems tardos tarjan technical terminal terms thanks that then theorem theory there these thesis this thoughtful three through thus time times topics total tragoudas transl tree turn uniform unit university unscaled upper using value venpala vertex very vetta violated volume weak while williamson with without work young
http://doi.acm.org/10.1145/982792.982903	90	A determinant-based algorithm for counting perfect matchings in a general graph	above again algebraic algebras algorithm algorithms allows along also analysis applied approxb approximating approximation barvinok base based bipartite bound bounds carlo case chien choosing class classes clifford combinatorica combinatorics complete completes complex complexity component computer computes computing conclude consider consolidating construct constructs containing contribution course covers cycle cycles desired details determinants discriminants discussed each easily edge endix entries equal erfect ermanent ermanents estimating estimator estimators every exactly exclusion extending factor fails fifth finally finishes first fixed following follows form formed formula frieze from further general generalization godsil graph graphs gutman hamilton have having hence here however hypothesis ignore imagine imate improvements inclusion independent induction inductive interesting interscience into janson jerrum journal july karmarkar karp larger leading lemma lines lipton longer lovasz lower lowing luby luczak magnitude manner many matched matching matchings matrix methods mixed modified moment monte natural negative next noncommutative nonetheless note noticing numb numbers obtain olynomial onential only original other pair part particular partition perfect plausible polynomial positive possible preprint present probability problem proceedings proof prove provide random rasmussen recal references remaining removed replacing respectively result rucinski same satisfy science second sequence should show siam simply since sinclair single situation smaller some spanning specifically step still straightforward structures subsequent suggesting summation symposium term terms than that their then theoretical theory there therefore these third this three thus time total transpose trees true tutte unbiased unfortunately upper used using valiant variable variance verified vertices very vigoda ways where whether which wiley will with within work would write
http://doi.acm.org/10.1145/982792.982953	131	Facility Location with Service Installation Costs	aardal acknowledgments aksoy algorithm algorithms analysis analyzed annual approx approximating approximation approximations arbitrary archer baev bartal change charikar chudak clustering computing constraint continuity coordinated cover data discrete discussions dual erenguc erties extends facility factor feige fitting francis gets greedy guarantees helpful however improved insights international inventory ipco item jagopalan jain jaraman john journal lagrangian location mahdian management manuscript markakis median metric minimum mirchandani models multi networks note only operations packing pages placement polynomial primal problem problems proceedings production prop pseudo raise rate reached reduction references relaxation replaced replenishments revealing robin rounding roundy same schema section sections shmoys siam simulate sons spaces steps stimulating straightforward suggestions survey sviridenko swamy symposium tardos thank that theory this threshold time uncapacitated unpublished using vazirani violation vitter wiley with york zhang
http://doi.acm.org/10.1145/982792.982856	51	Adaptive Sampling for Quickselect	above abstract achieved addison algorithm algorithms amounts amsterdam analysis anderson another appl applications apply approximation approximations aspects asymptotic australasian author available batfind beat beats bedient begin best bounds brown choice chosen combinatorial combinatorics communications computations computer computing congress conjecture considering cost course despite determination deterministic differential distribution does each edition element elementary endpoints equations error even exhibits expected experience extended fact features figure find first floyd following four from full furthermore future general generalize gies give given good growing grows grubel hall hand have here hoare hold however ifip impact important include incur informatics information inherent integral interesting interval introspective iteration iterations john journal kirschenhofer knuth lack large largest lection limi located long look lower mahmoud maple mart mass mathematical maxima median mentioned more musser northholland numerical obtain ofthree open operator optimal order other pages paper partition performance pivot plot point practice precise prentice previous prob probability probably problems proc procedure processing prodinger programming proof property proportion proportionfrom provide quickselect quicksort rainville random randomized rank reading reasonably refer references regions relative repeated results rivest rosler roura sample samples sampling searching section sections selection several show showing siam similarly size smallest smoothes software some sons sorting sought space start strategies stratei strongly structures studied subscripts suggest suitable terms that then theorem theoretical theoretically theory there these this thus time times uniformly unique used using value values variable various version volume wesley when where which wiley will with work yields york
http://doi.acm.org/10.1145/982792.982874	66	A Note on the Nearest Neighbor in Growth-Restricted Metrics	accessing algorithms annual another appear approximate architectures areas base berkeley both bound certificate charged clarkson communications comp computer considering constant copies deployment discrete distance distributed division dynamic environment expansion expected fact find finding first fourteenth gives globalscale growth high hildrum huang ieee issue jaraman ject jects joseph journal july june karger krauthgamer kubiatowicz larger lemma level levels location main means metric metrics more navigating nearby nearest neighbor neighbors nets network networks nodes number oracles over overcount overlay pages paral part plaxton possible probability proc proceedings proof prove proved proximity queries rapid references replicated report restricted rhea richa ruhl sample science search selected service show siam simple since size some spaces special stribling subcertificate summing symp symposium tapestry technical than that theory there this thorup total upper using versions were when where within zhao zwick
http://doi.acm.org/10.1145/982792.982913	98	Navigating nets: Simple algorithms for proximity search	algorithm also among approximate arya assouad ball balls based between children comparisons complete conclude constant cover covered dans data depth dimensions disjoint edges endix essentially every fixed follow follows forth france from leaves lemma length linear lipschitziens lower math metric mount nearest neighbor netanyahu numb omit optimal ounds path perform plongements proof radius references root search searching shortest show shows silverman similar since some sorting spirit that then this tree version vertex which will
http://doi.acm.org/10.1145/982792.982948	127	Fair and efficient router congestion control	access achieving acknowledgments active albanese algorithm allocation allocations also analysis applications approach approximately approximating assoc average avoidance bags bandwidth bennett blomer bottleneck broadband case choke codes comm comput congestion control core deficit demers detection discussions drop dynamics each early edmonds efficient elements encoded experience fair fairness fall finding flow flows floyd fredman frequent gallager gateway gateways generalized given golestani hashem helpful high ieee infocom information internet internetworking jacobson jaffe jiantao journal karp keshav koml lakshman luby mach management manuscript mckenny morris networking networks node october pages papadimitriou parekh prabhakar priority proc proceedings processor promoting protocol psounis queue queueing random references report research robin round scheme scott selfclocked sharing shenker shreedhar sigcomm simple simulation single sparse speed sred stabilized stateless steven stochastic stoica storing streams sudan szemer table tang technical thanks theory time trans transmission under understanding using varghese wang weighted with wong worst worstcase zhang
http://doi.acm.org/10.1145/982792.982852	48	Output-Sensitive Construction of the Union of Triangles	above academic acknowledgments actual actually agarwal algoapproximations algorithm algorithmica algorithms alon also although always amidst among annu another appl applicable application applications apply applying approach approaches approximate approximated approximation approximations argue arrangements assumed authors axisparallel because believe berg blue boston bottleneck bound cambridge case cause challenging chazelle choosing class cliffs collision combined compact complexity component components comput computanot computational compute concrete consisting constant construct constructing construction constructs cost counting counts covered decompose decomposition depth designed detailed details detection determine determined dimensions direction directly discrete discussions each editors eeding efficient efficiently ellipses encer englewood entire envelop equal erickson erin estimated european even example exist expect expected expressed extend extended extension ezra facilitate fact factor fail first form found free further generally generated geom geometric geometry good goodis guarantee hall halp have here heuristic holes however huttenlocher ieee implementation improve incremental inequalities input interscience intersecting intersection intersections into introduction involving iteration jects jentaan jordan katz kedem kluwer lack large larger later latomb lemma linearly livne machinery major manner manuscript many mathematical matouek method might miller models more motion motivation much mulmuley namely near needed note number obstacles olygonal omit only open optimal orciety order original other ounds output over overmars pach pages paper particular partitioning peled planar plane planning pollack portion portions positive possible practice prentice preprocessing presented press probabilistic problem problems proc procedure produce publishers quadratic quasi raises random randomized range realistic reasonably recall recompute references regions relatives remaining representing represents require resample research residual result resulting results rithms robot running runs sample sampling sariel searching seems sensitive several shallow shapes sharir showed showing shows siam sifrony simpler simplex simplices since single sity size slightly slower small smallest socondition solution solve solved sometimes space sparsely stage standard stapp step storage studied subcubic subquadratic subset such sufficient surfaces sympos symposium technique temporary terminate terms than thank that then theorem theorems theory there these this though three through thus time tional translational triangle triangles triples twist union unions univerto unknown useful using usually value values vertices violated vleugels voronoi wasteful weights well welzl when where whether which whose wiley will wish with worse would years york zone
http://doi.acm.org/10.1145/982792.982839	37	Locally satisfiable formulas	acknowledgement algorithm algorithmic algorithms also annual appear appeared applications applied approximation assignment attention attracting author available boolean bounds california cannot chernoff chosen clause clauses combinatorics comments completeness complexity computer computers computing constructed define dept derandomization deterministic discrete each eccc eecs either extremal false find finds forbidden forces formula foundations four fraction francisco freeman from functions garey gerhard given global guide guided hagerup heidelberg huang ieee implications inapproximability inform intractability john johnson journal jukna karloff least letters lieberherr like linear local math mathematics maximum method optimal outputs paper paradox partial particular pointing preliminary presented princeton probabilities probability problem problems proc process proof proposed referees references report respect result results same satisfaction satisfiability satisfiable satisfied satisfies science section siam sigact simply simultaneously some sons specker springer stad stat structures stuttgart such symposium technical thank that their then theorem theoretical theory there this time tour trevisan true truth university using usiskin valuable variable variables version versus voting wegener which wiley with woeginger would yannakakis zwick
http://doi.acm.org/10.1145/982792.982834	33	T	about above academic access according addisonwesley addition affect again algorithm algorithms allen almost also alternate alternating alternative among amplitude analogue analytic andconquer appl approach appropriately arbitrary arguments array arrays assume assumed assuming assumption asymptotic asymptotical asymptotics attention average away background base based basel bases basic because been before begin behind beta between binomial birkh bitindex bits bitsquick both bounded bounds boxed briefly byte calculate calculated calculation calculations call called cancellations case cauchy century certain certainly characterized charles check chosen chung cited classical code compare compared comparing comparison comparisons completes complex complexity complicated comput computation compute computer computing concatenation concentration concerning condition conjecture conjunction consequence consider considered constant containing continuation continuous contributions convenience converge convergence converges convex convexity correlated corresp cost course cutting data decay definiteness definition denote denotes density depends derivation derive describ designed desired details development differ difference differently digital discrete discussed distinct distributed distribution distributional divide does dominated donald dongarra double drawn draws duction dyadic each easily easy edition editors eferences either electronic element elementary elements else endence endent engineering equal equality equals error erties especially establish estimate estimates even event every evolution exact example excessive exists expansion expansions expectation expectations expected explicitly expression extended fact factor facts fair fashion fill finally find finite first fixed following follows form formula fortunately from full function functions further general generalized generalizes generated generating give given gives gnier greatest guest handle handled hardly harmonic have here higher hoare holds hosam idea identity immediately implementation implementational improve improved improvement include including increase indeed indep index indicates indicator inequality inequall influence inform initial input integer interesting interpretation interval intervals into intro invented invoke itself james janson jciech john joint just justifying keys knessl know known knuth large lder leading leads least left lemma length lengthy less limit limitations limiting line list london ludger magnitude mahmoud maintain make manipulation maple marginal martingale martingales mass math mathematica mathematical mathematics maximal mean measure meromorphic metho method middle minor mireille moment moments more moreover much multiply namely need neininger nonnegative norm normalized notation note nothing numb number numbers numerical observation observe observed obtain obvious omit onding only opens operation opportunity order ordered ordering other othness outline over overall paper paragraph particular partition passing perhaps period periodic pick pivot place plan plausible plugging poisson poissonization poissonize poissonized pole poles position positively possibility possible practice preceding precisely present press prior probability procedure product programming promised proof prop proposition prove proved provided provides proving pseudo quantify quicksort quite rairo ralph random randomly rank ranks rates rather rational rationals read reader readily reading real recall receives recurrence recursive recursively refer references register related relation remain remainder remaining remark repeated replacing required residue residues result results return returns review revisited rice right roposition rotated rotating rotation roura routine ruschendorf salvador same satisfies schwarz science search searching second section sequence setting shorthand show showing sides sign similarly simple simplification simply single situation sketch sler small smaller smoothing software solved some somewhat sons sorted sorting space split standard statement statistics still stirling strict strictly stronger structures study subarray subarrays subfiles submartingales such suitable sullivan summing sums suppose surely svante symbol symbolic systems szpankowski take taken taking technique tentatively term terminates terminating terms text than that their then theor theorem theorems theoretic theory there therein these they third this three through throughout time together total transitional transparent treatment tree trees trends triangle triple trivial true turn unif uniform uniformly unique unix unless used user using value vanishing varb variability variable variables variance vector versail version very vexity warm waste wastes weight well when where wherein whether which wiley will with would written york
http://doi.acm.org/10.1145/982792.982808	12	Quantitative Stochastic Parity Games	acad acknowledgments alfaro algebra algorithm algorithms alternation angeles annals anonymous appear applications arnold automata average behavior berkeley beyond blackwell both bound bradfield calculus california chapter chatterjee clarifying coefficients coloured competitive complexity computation compute computed computer concurrent condon contributions controllers corollary courcoubetis current dean deciding decision determinacy discrete dynamic economic editors elementary elsevier emerson equations event events everett exact exponential exponentially feasible filar finitely fixed focs follows formal foundations fragments from full game games geometry graphs guide gurevich handbook harrington have hence henzinger hierarchy hybrid icalp ieee implies improvement infinite information journal jumdar jurdzinski jutla kaelbling kaufmann kupferman languages lemmas letters lics limiting linear littman lncs logic logics many markov martin mathematical mathematics mean measures memoryless method methods modal modelchecking models morgan morgenstern neumann niwinski observation omega once only operations optimal pages parity partial paterson payoff player players pointing polynomial press princeton problems proceedings processes processing program programming progress proof pure puri puterman qualitative quantitative raghavan rational reachability recursive reduction referee references regular research rozenberg rudiments rupak salomaa science sciences shapley simple sistla small society solution solving springer stacs stoc stochastic strategies strategy strict studies survey symbolic synthesis system systems tarski thank that theorem theoretical theory there therefore thesis they this thomas time tomata tree trees university upper valuation values version vincent volume vrieze walukiewicz whose wiley wilke winner with words yannakakis zielonka zwick
http://doi.acm.org/10.1145/982792.982954	132	On Finding a Guard that Sees Most and a Shop that Sells Most	able acknowledgment addressed afrw algorithm algorithmica algorithms alon along also amidst analysis annu annual appl applications approach approximation area arguments being berg boots bounds cambridge canadian case cheng cheong chiu chlm christian clarkson class collision combinatorics comp competitive comput computational computer computing concepts conf conference congress considerably convex covering cviu dbcd dbgk dehne devillers diagrams difference discrete discussions edition editors efrat erickson facility free from fruitful fuchs further galleries gallery game geom geometry gewali ghosh giannopoulos gmmn golin greedy guarding guards handbook helmut here highway hochbaum holland homothets html http ifip illumination image info inform inter internat international involved israel ject jeff jentaan jordan joseph kedem klein klps knauer kreveld large lational lations leave lemma lery linial livne lncs locating location manuscript matching math matouek maximizing maximum meng method mitchell monographs more motion motwani mount naval north ntafos obsc obstacles okabe oostrum open optimum orourke orsa overlap overmars oxford pach pages paper path pathria peled placement planning point polygonal polygons presented press probabilistic probability problem problems proc process proof prove quarterly raghavan random randomized references regarding region regions related research respect result results roots rote round rourke sack sample sampling science sciences seems sees seidel series shapes sharir shor silverman sketching slower small smith spatial spencer square statistics sufficiently sugihara symmetric sympos teillaud tessel than thank that theo theorems theory this topp trans translated translation translations tsoukalas under understanding understood union unions university urrutia used valtr veltkamp vision volume voronoi weber weighted well were where wiley with york
http://doi.acm.org/10.1145/982792.982828	28	Detecting short directed cycles using rectangular matrix multiplication and dynamic programming	algorithmica algorithms alon also applications arithmetic barrier between breaking bridging closure clrs coding color complexity computation coppersmith cormen counting cycles demetrescu detecting developed directed dynamic edition eisenbrand fast faster finding focs fully given grandoni here huang information interesting introduction italiano journal kratsch leiserson length letters matrix multiplication multiplications other pages pairs paths press problem proc processing progressions rectangular references revisited rivest second sets shortest soda spinrad stein still symbolic techniques through transitive using winograd yuster zwick
http://doi.acm.org/10.1145/982792.982877	68	On minimizing the total flow time on multiple machines	above added algoremaining algorithm alive allow another approximately approximating approximation arrivals arrives assigned assumed awerbuch azar between bounded chekuri choice choices class classes clearly complete compute computing configuration consider correct corresponds could decided decrement decremented deferred define denote depends determines different disa distinct dynamic each eachxx either element elements else endence entries entry estimate estimating even every exists factor fewer finally first fixed flow following follows full give given gives have helps identical implies incurred information initial instance integer into jobs khanna know known largest last least lemma leonardi level machine machines migrawe minimizing more most next nonmost note notice npolylog numb number numbers oint once only optimal optimum order otherwise outside over paral particular partition partitioned poly polynomially possible precisely preemptive process processing program proof question range reach references regev released remaining rest rithm running runs schedule schemes sets show shows similarly since size sizes smaller smallest solution some srpt state states step stoc store strongly such suppose symposium than that their then theorem theory there these this thus time times tion total transform unfinished update using value verified version weight weighted weights were when where whether which will with within without works zero
http://doi.acm.org/10.1145/982792.982872	64	Caching Queues in Memory Buffers	abhinandan acknowledgements acyclic adversarial after algorithm algorithms also amongst analysis analyzed annual applicable applications approximate approximation arasu architecture area argument arises arrive ashok assume atleast azar babu badly bala bases been before began being below between bibliographical biennial borodin brian brief buffer bufferedhead buffers built bulletin bursty cache caching cambridge cannot cards carney case cetintemel chain chandrasekaran changing charles chen cherniack chunks class clock cock comments compare competitive computation computing conclusion conference constantly consume consumed consumes consumption continuous conversation convey coop corollary corp corresponding cost could counters cranor ctually daniel data database databases dataflow datar dates david defer deferring deluge described deshpande detailed details devavrat dewitt different discovery disk distributed does easily eighth ella elsewhere engineering enough enter enters enyuk erator erramilli ethernet even every exactly except exposition extended extra failure fast feng first floyd forced foreseeing form franklin from future gehrke george gigascop give given giving gray guide gurmeet happen have head hellerstein hence here hierarchical high hold hong http ieee implemented important improve improving incessantly incur indicated inject innovative input instant integration interesting international internet into issues iyer jeev jennifer jianjun johannes johnson join just kelly kleinb know komp krishnamurthy large largest least ledge leland letin like line load lookups madden maintained maintaining maintains makes management manager managers manku maximum mayur mckeown memory memoryefficient messaging michael micro minimization mining mirek mitch model modeling models modern monitoring more most motwani multiple multiqueue murad must nature need negative nesime network networking networks never newest next niagaracq nick nishizawa noticed number observe occupied occupy offline oldest oliver olston once online only onthe optimal oration other over oxford packet paper parts patterson paxson performance performed performing perk point poisson possible prabhakar preceding press previous principles problem proceedings processing proof protected provided query queue queues rajeev raman rate ratio reaches read reads reason reclaimed references region reiss remains replenish research resource result richter riedewald robin rosenstein round roundrobin routing sally sandeep scalable scheduler schedulers scheduling section seidman select self series services shah shedding shivnath shkap should show sigcomm sigkdd sigmod sikka similar simpler since single size sketch smaller software space spatsheck spite srivastava stan stanford state statistics still stochastic stonebraker stop storage stream streams structure studied such sundar suppose switches switching symposium system systems taqqu tatbul techniques telegraphcq than thank that then theodore theorem theory there therefore these this thomas thus tian tick time total traditional traffic transactions tuple tuples turns twentyfirst ugur unbounded uncertain unconsumed under university unprocessed unprotected until using varghese varma vern version very vladislav walter wang when which while wide widom will willinger wilson with words workshop world write writes written yaniv yossi yuan zachary zdonik ziedins
http://doi.acm.org/10.1145/982792.982854	50	Minimizing the Stabbing Number of Matchings, Trees, and Triangulations	acknowledgments agarwal algorithm algorithms also amounts annual appear appl applications approach approximation area arkin aronov assured average axis ball benchmark bender berg berkeley berlin bmatchings budgeted canadian chapter closely collision column combina combinatorial combinatorica communication company completeness comput computational computer computers computing conference cook costs covering crossing cunningham data decided decompositions delaunay demaine dept detection discrete discussions editors edmonds efficient egres electrical elte engineering euclidean evaluation factor fekete finally flythroughs francisco freeman further garey generalized geom geometric geometry getting grotschel guide handbooks hardness held hershberger holland however html http implications independent index inform instead interesting intersecting into intractability investigating iterated jain johnson journal just juttner kamal kiraly klosowski kreveld lecture length lett library line lines list lovasz magnanti management manhattan manuscript matal matching mathe mathematics matics matousek maximum methods minimum mitchell models monien monma msolomon nemhauser network north notes number numbers open operations optimal optimization orourke orsa other ottmann over overall padberg pages parallel pedestrian personal polygonalizations polyhedron polynomial possible prob problem problems proceedings process progress project pulleyblank pushing question reality rectilinear refer references reinelt related repeated representatives research resp right rounding rourke salesman schrijver science segments sethia sets shewchuk shoot shooting siam simple smith solomon solving some spanning springer springerverlag stabbing standards steiner structures subsets suri symposium take tetrahedralizations thank that theor theorem theory this time topp torial tours traveling trees triangulations tsplib turn unpublished verlag vertices virtual volume vrptw walk welcome welzl wiley with wolsey work york
http://doi.acm.org/10.1145/982792.982884	74	Tabulation Based 4-Universal Hashing with Applications to Second Moment Estimation	acknowledgment additional adds algorithm algorithms almost alon appendix applica applications approximating architecture arithmetic authentication available babcock babu based berkeley binger bits bloemer california carter cauchypap change charikar chen classes closest codc code codes colton combinatorial comments communication comp complexity comput computational computer computes computing conference counters cwtrick data database datar define design detection developer dietzfel dietzfelbinger double effective equality erasure estimation evaluation even exploiting farach fast finding frequency frequent from func functions graphs hagerup hash hashing high http icalp icsi imcint including independent inline instruction instructions integer intel internet invited ipaddr issues items kalfane karp karpinski katajainen krishnamurthy krishnan least like lncs lookup luby mansour manual manuals manuscript martin matias measurement methods models moment moments motwani mthorup muliplication multaddprime multimedia multiplications muthu muthukrishnan nisan nomial number numcounters only order pages pair papers pentium pentreturn pippenger plus polymultaddprime possibly power precomputed pretty prime primes principles problem proc proces protocols random randomized reference references reliable report research resilient return review rizzo rutgers scheme schnelle schonhage second sigact sigart sigmod significant simple size sketch soda software sors space sqsum stacs stoc strassen stream streamestimate streams streamupdate strings strongly structure suggestions symposium syst system systems szegedy table tables tabulation talk technical thank their theor thorup those tions tiwari tonen univ universal updating useful uses variables very void volume wegman whose widom wise with without woelfel would zahlen zhang zuckerman
http://doi.acm.org/10.1145/982792.982907	93	Efficiently Decodable Codes Meeting Gilbert-Varshamov Bound for Low Rates	above also approach asymptotically binary block bound canada cascading checked choice christian claim close code codes combining complexity computational concatenated conclude condition conference consider construct construction corrected decodable decode decoded decoding decodings defined different dimension disour distance distances each efficiently encoded english enough ensemble ensure equal equation error errors every except existence exponentially fact family field final following follows formal found fraction fractional from function generator gilbert give growing guaranteed guruswami half have high holds ieee inforcally information inner integer into large largest least length less linear list madhu main mark mation matrix maximize meet meeting meets member mial montreal more necessary optimizing outer over overall overwhelming pages parameters particular passed pick picked picking pinsker pluggin plugging polyno polynomial polynomially possibly probabilistic probability problems proc procedure program proof proven radius random rate rates reed references relative restriction result russian satisfy search seen simple size small soft solomon specifialgorithm specific state statements such sudan tance than that then theorem theorems theory there this thommesen thus time trade transactions transmission underlying unique uses using varshamov varying venkatesan very victor well where which whose will with zyablov
http://doi.acm.org/10.1145/982792.982926	108	Complexities for Generalized Models of Self-Assembly	adleman annual assembled cheng computing goel huang pages proceedings program references running self size squares symposium theory time
http://doi.acm.org/10.1145/982792.982815	17	An improved data stream algorithm for frequency moments	acknowledgments algorithm algorithms alon annual application applications approach approx approxim approximate approximating approximation arbitrary architectures arrive authentication author babcock babu base bjks black bound bounds carter chakrabarti classes communication complexity computational computations computer computing conference counting data database datar details difference differences dimacs discrete discussions disjointness distance distinct distributions during elements embeddings equality essentially estimating feigenbaum fksv focs foundations frequency functions generators gibbons graphs hash henzinger ideas ieee imate indyk information international issues jagopalan jayram jolet journal kannan khot kumar lower many martin massive mate mathematics matias methods model models modified moments motwani multi multiparty muthukrishnan nearoptimal note omitted order page pages paral pass pods preceding principles probabilistic problem proc proposition pseudorandom raghavan random randomization recall reductions references saks sampling science sciences second series siam sigact sigmodsigart similar simple sivakumar soda spaa space stable stated statistics stoc strauss stream streaming streams symposium system systems szegedy techniques thankful that their theoretical theory this those thus tight tirthapura trevisan triangles union universal used using viswanathan volume wegman where widom with woodruff work workshop yossef