부산대학교 도서관

\{The 18th Symposium has been reviewed [ 2490500 ].\} \par Contents: Nir\ Ailon\ and Edo\ Liberty, Fast dimension reduction using Rademacher series on dual BCH codes (1--9) 2367443 ; Ping\ Li [Ping\ Li\asup {12}], Estimators and tail bounds for dimension reduction in $l_\alpha$ $(0<\alpha\leq2)$ using stable random projections (10--19) 2485284 ; M.\ A.\ Iwen, A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods (20--29) 2485285 ; Piotr\ Indyk, Explicit constructions for compressed sensing of sparse signals (30--33) 2485286 ; Aaron\ Bernstein\ and David\ Karger, Improved distance sensitivity oracles via random sampling (34--43) 2485287 . \par S.\ Thomas\ McCormick\ and Satoru\ Fujishige, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization (44--53) 2485288 ; Jin-Yi\ Cai\ and Pinyan\ Lu, Holographic algorithms with unsymmetric signatures (54--63) 2485289 ; Guy\ Kindler, Assaf\ Naor\ and Gideon\ Schechtman, The UGC hardness threshold of the $l_p$ Grothendieck problem (64--73) 2485290 ; Ilias\ Diakonikolas\ and Mihalis\ Yannakakis, Succinct approximate convex Pareto curves (extended abstract) (74--83) 2485291 ; Daniele\ Micciancio, Efficient reductions among lattice problems (84--93) 2485292 . \par Xiaomin\ Chen, János\ Pach, Mario\ Szegedy\ and Gábor\ Tardos, Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles (94--101) 2485293 ; Raghavan\ Dhandapani, Greedy drawings of triangulations (102--111) 2485294 ; Siu-Wing\ Cheng\ and Tamal\ K.\ Dey, Maintaining deforming surface meshes (112--121) 2485295 ; Arno\ Eigenwillig\ and Michael\ Kerber, Exact and efficient 2D-arrangements of arbitrary algebraic curves (122--131) 2485296 ; Nicla\ Bernasconi, Konstantinos\ Panagiotou\ and Angelika\ Steger, On properties of random dissections and triangulations (132--141) 2485297 . \par Bonnie\ Berger, Rohit\ Singh\ and Jinbo\ Xu, Graph algorithms for biological systems analysis (142--151) 2485298 . \par Julián\ Mestre, Adaptive local ratio (152--160) 2485299 ; Ulrich\ Faigle\ and Britta\ Peis, Two-phase greedy algorithms for some classes of combinatorial linear programs (161--166) 2485300 ; Ding-Zhu\ Du, Ronald\ L.\ Graham, Panos\ M.\ Pardalos, Peng-Jun\ Wan, Weili\ Wu\ and Wenbo\ Zhao, Analysis of greedy approximations with nonsubmodular potential functions (167--175) 2485301 ; Claire\ Mathieu\ and Warren\ Schudy, Yet another algorithm for dense max cut: go greedy (176--182) 2485302 ; Ignaz\ Rutter\ and Alexander\ Wolff, Computing large matchings fast (183--192) 2485303 . \par P.\ E.\ Haxell\ and G.\ T.\ Wilfong, A fractional model of the border gateway protocol (BGP) (193--199) 2485304 ; Prahladh\ Harsha, Thomas\ P.\ Hayes, Hariharan\ Narayanan, Harald\ Räcke\ and Jaikumar\ Radhakrishnan, Minimizing average latency in oblivious routing (200--207) 2485305 ; Gianluca\ De Marco, Distributed broadcast in unknown radio networks (208--217) 2485306 ; Robert\ Elsässer\ and Thomas\ Sauerwald, The power of memory in randomized broadcasting (218--227) 2485307 ; Amos\ Fiat, Yishay\ Mansour\ and Uri\ Nadav, Competitive queue management for latency sensitive packets (228--237) 2485308 . \par Elchanan\ Mossel\ and Allan\ Sly, Rapid mixing of Gibbs sampling on graphs that are sparse on average (238--247) 2485309 ; László\ Babai, Nikolay\ Nikolov [Nikolai\ Valeriev\ Nikolov]\ and László\ Pyber, Product growth and mixing in finite groups (248--257) 2485310 ; Venkatesan\ Guruswami\ and Atri\ Rudra, Concatenated codes can achieve list-decoding capacity (258--267) 2485311 ; Mark\ Braverman\ and Elchanan\ Mossel, Noisy sorting without resampling (268--276) 2485312 ; Michael\ Zuckerman, Ariel\ D.\ Procaccia\ and Jeffrey\ S.\ Rosenschein, Algorithms for the coalitional manipulation problem (277--286) 2485313 . \par Uriel\ Feige, On allocations that maximize fairness (287--293) 2485314 ; Susanne\ Albers, On the value of coordination in network design (294--303) 2485315 ; Matthew\ C.\ Cary, Abraham\ D.\ Flaxman, Jason\ D.\ Hartline\ and Anna\ R.\ Karlin, Auctions for structured procurement (304--313) 2485316 ; Baruch\ Awerbuch, Yossi\ Azar\ and Rohit\ Khandekar, Fast load balancing via bounded best response (314--322) 2485317 ; Yossi\ Azar, Kamal\ Jain\ and Vahab\ Mirrokni, (Almost) optimal coordination mechanisms for unrelated machine scheduling (323--332) 2485318 . \par T.-H.\ Hubert\ Chan, Anupam\ Gupta\ and Kunal\ Talwar, Ultra-low-dimensional embeddings for doubling metrics (333--342) 2485319 ; Alexandr\ Andoni, Piotr\ Indyk\ and Robert\ Krauthgamer, Earth mover distance over high-dimensional spaces (343--352) 2485320 ; Venkatesan\ Guruswami, James\ R.\ Lee\ and Alexander\ Razborov [A.\ A.\ Razborov], Almost Euclidean subspaces of $l^N_1$ via expander codes (353--362) 2485321 ; Ittai\ Abraham, Yair\ Bartal\ and Ofer\ Neiman, Embedding metric spaces in their intrinsic dimension (363--372) 2485322 ; Noga\ Alon\ and Michael\ Capalbo [M.\ R.\ Capalbo], Optimal universal graphs with deterministic embedding (373--378) 2485323 . \par Ilan\ Gronau, Shlomo\ Moran\ and Sagi\ Snir, Fast and reliable reconstruction of phylogenetic trees with very short edges (extended abstract) (379--388) 2487605 ; Thomas\ Holenstein, Michael\ Mitzenmacher, Rina\ Panigrahy\ and Udi\ Wieder, Trace reconstruction with constant deletion probability and related results (389--398) 2487606 ; Krishnamurthy\ Viswanathan\ and Ram\ Swaminathan, Improved string reconstruction over insertion-deletion channels (399--408) 2487607 ; Ho-Lin\ Chen, Ashish\ Goel\ and Chris\ Luhrs, Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly (409--418) 2487608 ; Ely\ Porat\ and Klim\ Efremenko, Approximating general metric distances between a pattern and a text (419--427) 2487609 . \par Yuval\ Emek, David\ Peleg\ and Liam\ Roditty, A near-linear time algorithm for computing replacement paths in planar directed graphs (428--435) 2487610 ; Ran\ Duan [Ran\ Duan\asup 2]\ and Seth\ Pettie, Bounded-leg distance and reachability oracles (436--445) 2487611 ; Ken-ichi\ Kawarabayashi\ and Bruce\ Reed [Bruce\ A.\ Reed], A nearly linear time algorithm for the half integral disjoint paths packing (446--454) 2487612 ; Anand\ Bhalgat, Ramesh\ Hariharan, Telikepalli\ Kavitha\ and Debmalya\ Panigrahi, Fast edge splitting and Edmonds' arborescence construction for unweighted graphs (455--464) 2487613 ; Virginia\ Vassilevska, Nondecreasing paths in a weighted graph or: how to optimally read a train schedule (465--472) 2487614 . \par Jessica\ Chang, Thomas\ Erlebach, Renars\ Gailis\ and Samir\ Khuller, Broadcast scheduling: algorithms and complexity (473--482) 2487615 ; Tomáš\ Ebenlendr, Marek\ Krčál\ and Jiří\ Sgall, Graph balancing: a special case of scheduling unrelated parallel machines (483--490) 2487616 ; Julien\ Robert\ and Nicolas\ Schabanel, Non-clairvoyant scheduling with precedence constraints (491--500) 2487617 ; Guy\ E.\ Blelloch, Rezaul\ A.\ Chowdhury, Phillip\ B.\ Gibbons, Vijaya\ Ramachandran, Shimin\ Chen\ and Michael\ Kozuch, Provably good multicore cache performance for divide-and-conquer algorithms (501--510) 2487618 ; P.\ Brighten\ Godfrey, Balls and bins with structure: balanced allocations on hypergraphs (511--517) 2487619 . \par Naoyuki\ Kamiyama, Naoki\ Katoh\ and Atsushi\ Takizawa, Arc-disjoint in-trees in directed graphs (518--526) 2487620 ; Sergio\ Cabello, Matt\ DeVos, Jeff\ Erickson\ and Bojan\ Mohar, Finding one tight cycle (527--531) 2487621 ; Chandra\ Chekuri, Guy\ Even, Anupam\ Gupta\ and Danny\ Segev, Set connectivity problems in undirected graphs and the directed Steiner network problem (532--541) 2487622 ; Nicholas\ J. A. Harvey, Matroid intersection, pointer chasing, and Young's seminormal representation of $S_n$ (542--549) 2487623 ; Harold\ N.\ Gabow\ and Suzanne\ Gallagher, Iterated rounding algorithms for the smallest $k$-edge connected spanning subgraph (550--559) 2487624 . \par Persi\ Diaconis, Shuffling cards, adding numbers, and symmetric functions (560). \par Timothy\ M.\ Chan, On the bichromatic $k$-set problem (561--570) 2487625 ; Jie\ Gao [Jie\ Gao\asup 1], Leonidas\ J.\ Guibas, Steve\ Y.\ Oudot\ and Yue\ Wang, Geodesic Delaunay triangulation and witness complex in the plane (571--580) 2487626 ; Adrian\ Dumitrescu\ and Csaba\ D.\ Tóth, Minimum weight convex Steiner partitions (581--590) 2487627 ; Lee-Ad\ Gottlieb\ and Liam\ Roditty, Improved algorithms for fully dynamic geometric spanners and geometric routing (591--600) 2487628 ; Josep\ Díaz, Dieter\ Mitsche\ and Xavier\ Pérez-Giménez, On the connectivity of dynamic random geometric graphs (601--610) 2487629 . \par Aravind\ Srinivasan, Improved algorithmic versions of the Lovász local lemma (611--620) 2487630 ; Frédéric\ Havet, Bruce\ Reed [Bruce\ A.\ Reed]\ and Jean-Sébastien\ Sereni, $L(2,1)$-labelling of graphs (621--630) 2487631 ; Frederic\ Dorn, Fedor\ V.\ Fomin\ and Dimitrios\ M.\ Thilikos, Catalan structures and dynamic programming in $H$-minor-free graphs (631--640) 2487632 ; Isolde\ Adler, Martin\ Grohe\ and Stephan\ Kreutzer, Computing excluded minors (641--650) 2487633 ; Reid\ Andersen\ and Kevin\ J.\ Lang, An algorithm for improving graph partitions (651--660) 2487634 . \par Chandra\ Chekuri, Nitish\ Korula\ and Martin\ Pál, Improved algorithms for orienteering and related problems (661--670) 2487635 ; Yuval\ Rabani, Leonard\ J.\ Schulman\ and Chaitanya\ Swamy, Approximation algorithms for labeling hierarchical taxonomies (671--680) 2487636 ; Mark\ Huber\ and Jenny\ Law, Fast approximation of the permanent for very dense problems (681--689) 2487637 ; T.-H.\ Hubert\ Chan\ and Anupam\ Gupta, Approximating TSP on metrics with bounded global growth (690--699) 2487638 ; Nir\ Halman, Diego\ Klabjan, Chung-Lun\ Li, James\ Orlin\ and David\ Simchi-Levi, Fully polynomial time approximation schemes for stochastic dynamic programs (700--709) 2487639 . \par Jon\ Feldman, S.\ Muthukrishnan, Anastasios\ Sidiropoulos, Cliff\ Stein\ and Zoya\ Svitkina, On distributing symmetric streaming computations (710--719) 2487640 ; Amit\ Chakrabarti, T.\ S.\ Jayram\ and Mihai\ Pǎtraşcu, Tight lower bounds for selection in randomly ordered streams (720--729) 2487641 ; Funda\ Ergun\ and Hossein\ Jowhari, On distance to monotonicity and longest increasing subsequence of a data stream (730--736) 2487642 ; Piotr\ Indyk\ and Andrew\ McGregor, Declaring independence via the sketching of sketches (737--745) 2487643 ; Michael\ Mitzenmacher\ and Salil\ Vadhan, Why simple hash functions work: exploiting the entropy in a data stream (746--755) 2487644 . \par Mike\ Paterson, Yuval\ Peres, Mikkel\ Thorup, Peter\ Winkler [Peter\ Mann\ Winkler]\ and Uri\ Zwick, Maximum overhang (extended abstract) (756--765) 2487645 ; Joshua\ Cooper, Benjamin\ Doerr, Tobias\ Friedrich\ and Joel\ Spencer, Deterministic random walks on regular trees (766--772) 2487646 ; Benjamin\ Doerr, Tobias\ Friedrich\ and Thomas\ Sauerwald, Quasirandom rumor spreading (773--781) 2487647 ; Domingos\ Dellamonica, Jr., Yoshiharu\ Kohayakawa, Vojtěch\ Rödl\ and Andrzej\ Ruciński, Universality of random graphs (782--788) 2487648 ; Asaf\ Shapira\ and Raphael\ Yuster, The effect of induced subgraphs on quasi-randomness (789--798) 2487649 . \par Marcel\ R.\ Ackermann, Johannes\ Blömer\ and Christian\ Sohler, Clustering for metric and non-metric distance measures (799--808) 2487650 ; Robert\ Krauthgamer\ and Tim\ Roughgarden, Metric clustering via consistent labeling (809--818) 2487651 ; Matt\ Gibson, Gaurav\ Kanade, Erik\ Krohn, Imran\ A.\ Pirwani\ and Kasturi\ Varadarajan, On clustering to minimize the sum of radii (819--825) 2487652 ; Ke\ Chen [Ke\ Chen\asup 3], A constant factor approximation algorithm for $k$-median clustering with outliers (826--835) 2487653 ; Sergio\ Cabello, Panos\ Giannopoulos, Christian\ Knauer\ and Günter\ Rote, Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension (836--843) 2487654 . \par Alex\ Fabrikant\ and Christos\ H.\ Papadimitriou, The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond (844--853) 2487655 ; Ho-Lin\ Chen, Tim\ Roughgarden\ and Gregory\ Valiant, Designing networks with good equilibria (854--863) 2487656 ; Sushil\ Bikhchandani, Sven\ de Vries, James\ Schummer\ and Rakesh\ V.\ Vohra, Ascending auctions for integral (poly)matroids with concave nondecreasing separable values (864--873) 2487657 ; Peter\ Bro\ Miltersen\ and Troels\ Bjerre\ Sørensen, Fast algorithms for finding proper strategies in game trees (874--883) 2487658 ; Ofer\ Dekel, Felix\ Fischer\ and Ariel\ D.\ Procaccia, Incentive compatible regression learning (884--893) 2487659 . \par Guy\ E.\ Blelloch, Space-efficient dynamic orthogonal point location, segment intersection, and range reporting (894--903) 2487660 ; Timothy\ M.\ Chan\ and Eric\ Y.\ Chen, In-place 2-d nearest neighbor search (904--911) 2487661 ; Sébastien\ Collette, Vida\ Dujmović, John\ Iacono, Stefan\ Langerman\ and Pat\ Morin, Distribution-sensitive point location in convex subdivisions (912--921) 2487662 ; Kenneth\ L.\ Clarkson, Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm (922--931) 2487663 ; Anirban\ Dasgupta [Anirban\ Dasgupta\asup 2], Petros\ Drineas, Boulos\ Harb, Ravi\ Kumar [S.\ Ravi\ Kumar]\ and Michael\ W.\ Mahoney, Sampling algorithms and coresets for $l_p$ regression (932--941) 2487664 . \par Naveen\ Garg, Anupam\ Gupta, Stefano\ Leonardi [Stefano\ Leonardi\asup 1]\ and Piotr\ Sankowski, Stochastic analyses for online combinatorial optimization problems (942--951) 2487665 ; N.\ Buchbinder, T.\ Kimbrel, R.\ Levi [Retsef\ Levi], K.\ Makarychev\ and M.\ Sviridenko [Maxim\ I.\ Sviridenko], Online make-to-order joint replenishment model: primal dual competitive algorithms (952--961) 2487666 ; Michael\ Saks\ and C.\ Seshadhri, Parallel monotonicity reconstruction (962--971) 2487667 ; Ioannis\ Caragiannis, Better bounds for online load balancing on unrelated machines (972--981) 2487668 ; Gagan\ Goel\ and Aranyak\ Mehta, Online budgeted matching in random input models with applications to Adwords (982--991) 2487669 . \par Andrei\ Broder, Computational advertising (992). \par Henry\ Lin [Henry\ Chih-Heng\ Lin], Christos\ Amanatidis, Martha\ Sideri, Richard\ M.\ Karp\ and Christos\ H.\ Papadimitriou, Linked decompositions of networks and the power of choice in Polya urns (993--1002) 2487670 ; Reid\ Andersen, A local algorithm for finding dense subgraphs (1003--1009) 2487671 ; Prasad\ Chebolu\ and Páll\ Melsted, PageRank and the random surfer model (1010--1018) 2487672 ; Arpita\ Ghosh [Arpita\ Ghosh\asup 1]\ and Mohammad\ Mahdian, Charity auctions on social networks (1019--1028) 2487673 ; Ning\ Chen [Ning\ Chen\asup 5], On the approximability of influence in social networks (1029--1037) 2487674 . \par Bruce\ Kapron, David\ Kempe, Valerie\ King, Jared\ Saia\ and Vishal\ Sanwalani, Fast asynchronous Byzantine agreement and leader election with full information (1038--1047) 2487675 ; Bhavani\ Shankar, Prasant\ Gopal, Kannan\ Srinathan\ and C. Pandu Rangan, Unconditionally reliable message transmission in directed networks (1048--1055) 2487676 ; Chinmoy\ Dutta, Yashodhan\ Kanoria, D.\ Manjunath\ and Jaikumar\ Radhakrishnan, A tight lower bound for parity in noisy communication networks (1056--1065) 2487677 ; James\ Aspnes, Muli\ Safra\ and Yitong\ Yin, Ranged hash functions and the price of churn (1066--1075) 2487678 ; Graham\ Cormode, S.\ Muthukrishnan\ and Ke\ Yi, Algorithms for distributed functional monitoring (1076--1085) 2487679 . \par Amihood\ Amir\ and Igor\ Nor, Real-time indexing over fixed finite alphabets (1086--1095) 2487680 ; Shay\ Mozes, Krzysztof\ Onak\ and Oren\ Weimann, Finding an optimal tree searching strategy in linear time (1096--1105) 2487681 ; Prosenjit\ Bose, Karim\ Douïeb\ and Stefan\ Langerman, Dynamic optimality for skip lists and B-trees (1106--1114) 2487682 ; Seth\ Pettie, Splay trees, Davenport-Schinzel sequences, and the deque conjecture (1115--1124) 2487683 ; Surender\ Baswana\ and Soumojit\ Sarkar, Fully dynamic algorithm for graph spanners with poly-logarithmic update time (1125--1134) 2487684 . \par Mario\ Mense\ and Christian\ Scheideler, SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems (1135--1144) 2490485 ; Ashish\ Goel\ and Hamid\ Nazerzadeh, Price based protocols for fair resource allocation: convergence time analysis and extension to Leontief utilities (1145--1153) 2490486 ; Zoya\ Svitkina, Lower-bounded facility location (1154--1163) 2490487 ; Barbara\ M.\ Anthony, Vineet\ Goyal, Anupam\ Gupta\ and Viswanath\ Nagarajan, A plant location guide for the unsure (1164--1173) 2490488 ; Friedrich\ Eisenbrand, Fabrizio\ Grandoni [Fabrizio\ Grandoni\asup 2], Thomas\ Rothvoß\ and Guido\ Schäfer, Approximating connected facility location problems via random facility sampling and core detouring (1174--1183) 2490489 . \par Andrei\ Z.\ Broder, Adam\ Kirsch, Ravi\ Kumar [S.\ Ravi\ Kumar], Michael\ Mitzenmacher\ and Sergei\ Vassilvitskii, The hiring problem and Lake Wobegon strategies (1184--1193) 2490490 ; Noga\ Alon, Haim\ Kaplan, Gabriel\ Nivasch, Micha\ Sharir\ and Shakhar\ Smorodinsky, Weak $\epsilon$-nets and interval chains (1194--1203) 2490491 ; Takuro\ Fukunaga, Magnús\ M.\ Halldórsson\ and Hiroshi\ Nagamochi, Robust cost colorings (1204--1212) 2490492 ; Ido\ Ben-Eliezer, Tali\ Kaufman, Michael\ Krivelevich\ and Dana\ Ron, Comparing the strength of query types in property testing: the case of testing $k$-colorability (1213--1222) 2490493 ; Nayantara\ Bhatnagar, Sam\ Greenberg\ and Dana\ Randall, Sampling stable marriages: why spouse-swapping won't work (1223--1232) 2490494 . \par Adrian\ Dumitrescu\ and Csaba\ D.\ Tóth, On stars and Steiner stars (1233--1240) 2490495 ; Boris\ Aronov, Mark\ de Berg, Chris\ Gray [Christopher\ Miles\ Gray]\ and Elena\ Mumford, Cutting cycles of rods in space: hardness and approximation (1241--1248) 2490496 ; Olivier\ Devillers, Jeff\ Erickson\ and Xavier\ Goaoc, Empty-ellipse graphs (1249--1257) 2490497 ; David\ Eppstein, Recognizing partial cubes in quadratic time (1258--1266) 2490498 ; Thomas\ Erlebach\ and Erik\ Jan\ van Leeuwen, Approximating geometric coverage problems (1267--1276) 2490499 . \par \{The papers will not be reviewed individually.\}