Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21--23, 2009. Proceedings (Q838961)

The articles of this volume will be reviewed individually. The preceding workshops APPROX 2008 and RANDOM 2008 have been reviewed (see Zbl 1149.68010). Indexed articles: \textit{Aazami, Ashkan; Cheriyan, Joseph; Jampani, Krishnam Raju}, Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs, 1-14 [Zbl 1254.68350] \textit{Aggarwal, Ankit; Deshpande, Amit; Kannan, Ravi}, Adaptive sampling for \(k\)-means clustering, 15-28 [Zbl 1254.68351] \textit{Carroll, Douglas E.; Meyerson, Adam; Tagiku, Brian}, Approximations for aligned coloring and spillage minimization in interval and chordal graphs, 29-41 [Zbl 1254.68352] \textit{Chekuri, Chandra; Ene, Alina; Korula, Nitish}, Unsplittable flow in paths and trees and column-restricted packing integer programs, 42-55 [Zbl 1254.68353] \textit{Chekuri, Chandra; Gamzu, Iftah}, Truthful mechanisms via greedy iterative packing, 56-69 [Zbl 1254.68354] \textit{Chuzhoy, Julia; Codenotti, Paolo}, Resource minimization job scheduling, 70-83 [Zbl 1254.90067] \textit{Correa, José R.; Skutella, Martin; Verschae, José}, The power of preemption on unrelated machines and applications to scheduling orders, 84-97 [Zbl 1254.90068] \textit{Eisenbrand, Friedrich; Rothvoß, Thomas}, New hardness results for Diophantine approximation, 98-110 [Zbl 1254.68349] \textit{Feige, Uriel; Immorlica, Nicole; Mirrokni, Vahab S.; Nazerzadeh, Hamid}, PASS approximation. A framework for analyzing and designing heuristics, 111-124 [Zbl 1254.68242] \textit{Georgiou, Konstantinos; Magen, Avner; Tulsiani, Madhur}, Optimal Sherali-Adams gaps from pairwise independence, 125-139 [Zbl 1254.68125] \textit{Gibson, Matt; Kanade, Gaurav; Krohn, Erik; Varadarajan, Kasturi}, An approximation scheme for terrain guarding, 140-148 [Zbl 1255.68302] \textit{Gupta, Anupam; Krishnaswamy, Ravishankar; Kumar, Amit; Segev, Danny}, Scheduling with outliers, 149-162 [Zbl 1255.90060] \textit{Guruswami, Venkatesan; Sinop, Ali Kemal}, Improved inapproximability results for maximum \(k\)-colorable subgraph, 163-176 [Zbl 1255.68072] \textit{Harren, Rolf; van Stee, Rob}, Improved absolute approximation ratios for two-dimensional packing problems, 177-189 [Zbl 1255.68304] \textit{Jaffe, Alex; Lee, James R.; Moharrami, Mohammad}, On the optimality of gluing over scales, 190-201 [Zbl 1255.68191] \textit{Khandekar, Rohit; Kimbrel, Tracy; Makarychev, Konstantin; Sviridenko, Maxim}, On hardness of pricing items for single-minded bidders, 202-216 [Zbl 1255.68075] \textit{Koch, Ronald; Peis, Britta; Skutella, Martin; Wiese, Andreas}, Real-time message routing and scheduling, 217-230 [Zbl 1255.68047] \textit{Kortsarz, Guy; Nutov, Zeev}, Approximating some network design problems with node costs, 231-243 [Zbl 1255.68305] \textit{Lee, Jon; Sviridenko, Maxim; Vondrák, Jan}, Submodular maximization over multiple matroids via generalized exchange properties, 244-257 [Zbl 1255.90106] \textit{Magen, Avner; Moharrami, Mohammad}, Robust algorithms for \textsc{Max Independent Set} on minor-free graphs based on the Sherali-Adams hierarchy, 258-271 [Zbl 1255.68306] \textit{Meyerson, Adam; Tagiku, Brian}, Minimizing average shortest path distances via shortcut edge addition, 272-285 [Zbl 1255.68307] \textit{Nutov, Zeev}, Approximating node-connectivity augmentation problems, 286-297 [Zbl 1255.68308] \textit{Paluch, Katarzyna; Mucha, Marcin; Mądry, Aleksander}, A 7/9-approximation algorithm for the maximum traveling salesman problem, 298-311 [Zbl 1255.68309] \textit{Pandit, Saurav; Pemmaraju, Sriram V.; Varadarajan, Kasturi}, Approximation algorithms for domatic partitions of unit disk graphs, 312-325 [Zbl 1255.68310] \textit{Rothvoß, Thomas; Sanità, Laura}, On the complexity of the asymmetric VPN problem, 326-338 [Zbl 1255.68311] \textit{Alon, Noga; Panigrahy, Rina; Yekhanin, Sergey}, Deterministic approximation algorithms for the nearest codeword problem, 339-351 [Zbl 1255.68298] \textit{Barak, Boaz; Rao, Anup; Raz, Ran; Rosen, Ricky; Shaltiel, Ronen}, Strong parallel repetition theorem for free projection games, 352-365 [Zbl 1255.68146] \textit{Ben-Eliezer, Ido; Hod, Rani; Lovett, Shachar}, Random low degree polynomials are hard to approximate, 366-377 [Zbl 1255.68069] \textit{Ben-Sasson, Eli; Viderman, Michael}, Composition of semi-LTCs by two-wise tensor products, 378-391 [Zbl 1255.94088] \textit{Bogdanov, Andrej; Qiao, Youming}, On the security of Goldreich's one-way function, 392-405 [Zbl 1255.94053] \textit{Brubaker, S. Charles; Vempala, Santosh S.}, Random tensors and planted cliques, 406-419 [Zbl 1254.05180] \textit{Chandrasekaran, Karthekeyan; Deshpande, Amit; Vempala, Santosh}, Sampling \(s\)-concave functions: the limit of convexity based isoperimetry, 420-433 [Zbl 1255.90091] \textit{Chebolu, Prasad; Frieze, Alan; Melsted, Páll; Sorkin, Gregory B.}, Average-case analyses of Vickrey costs, 434-447 [Zbl 1255.91140] \textit{Chen, Victor}, A hypergraph dictatorship test with perfect completeness, 448-461 [Zbl 1255.68147] \textit{De, Anindya; Trevisan, Luca}, Extractors using hardness amplification, 462-475 [Zbl 1255.68289] \textit{Efremenko, Klim; Reingold, Omer}, How well do random walks parallelize?, 476-489 [Zbl 1255.05180] \textit{Frieze, Alan; Melsted, Páll; Mitzenmacher, Michael}, An analysis of random-walk cuckoo hashing, 490-503 [Zbl 1255.68059] \textit{Goldreich, Oded; Krivelevich, Michael; Newman, Ilan; Rozenberg, Eyal}, Hierarchy theorems for property testing, 504-519 [Zbl 1255.68290] \textit{Goldreich, Oded; Ron, Dana}, Algorithmic aspects of property testing in the dense graphs model, 520-533 [Zbl 1255.68291] \textit{Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu}, Succinct representation of codes with applications to testing, 534-547 [Zbl 1255.94082] \textit{Harrow, Aram W.; Low, Richard A.}, Efficient quantum tensor product expanders and \(k\)-designs, 548-561 [Zbl 1255.81107] \textit{Jayram, T. S.}, Hellinger strikes back: a note on the multi-party information complexity of AND, 562-573 [Zbl 1255.68074] \textit{Kinne, Jeff; van Melkebeek, Dieter; Shaltiel, Ronen}, Pseudorandom generators and typically-correct derandomization, 574-587 [Zbl 1255.68292] \textit{Klivans, Adam R.; Long, Philip M.; Tang, Alex K.}, Baum's algorithm learns intersections of halfspaces with respect to log-concave distributions, 588-600 [Zbl 1255.68123] \textit{Kopparty, Swastik; Saraf, Shubhangi}, Tolerant linearity testing and locally testable codes, 601-614 [Zbl 1255.68293] \textit{Lovett, Shachar; Reingold, Omer; Trevisan, Luca; Vadhan, Salil}, Pseudorandom bit generators that fool modular sums, 615-630 [Zbl 1255.68294] \textit{Lucier, Brendan; Molloy, Michael; Peres, Yuval}, The Glauber dynamics for colourings of bounded degree trees, 631-645 [Zbl 1255.68116] \textit{Matulef, Kevin; O'Donnell, Ryan; Rubinfeld, Ronitt; Servedio, Rocco A.}, Testing \(\pm 1\)-weight halfspace, 646-657 [Zbl 1255.68295] \textit{Meka, Raghu; Zuckerman, David}, Small-bias spaces for group products, 658-672 [Zbl 1255.68102] \textit{Minder, Lorenz; Vilenchik, Dan}, Small clique detection and approximate Nash equilibria, 673-685 [Zbl 1255.68084] \textit{Ron, Dana; Tsur, Gilad}, Testing computability by width two OBDDs, 686-699 [Zbl 1255.68296] \textit{Shpilka, Amir; Volkovich, Ilya}, Improved polynomial identity testing for read-once formulas, 700-713 [Zbl 1255.68297] \textit{Tao, Terence; Vu, Van}, Smooth analysis of the condition number and the least singular value, 714-737 [Zbl 1255.65088]