Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 7th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2004 and 8th international workshop on randomization and computation, RANDOM 2004, Cambridge, MA, USA, August22-24, 2004. Proceedings. (Q1763057)

The articles of this volume will be reviewed individually. The preceding workshops have been reviewed (see Zbl 1026.00023). Indexed articles: \textit{Alicherry, Mansoor; Bhatia, Randeep; Wan, Yung-Chun (Justin)}, Designing networks with existing traffic to support fast restoration, 1-12 [Zbl 1105.68300] \textit{Andreev, Konstantin; Garrod, Charles; Maggs, Bruce; Meyerson, Adam}, Simultaneous source location, 13-26 [Zbl 1105.90357] \textit{Babaioff, Moshe; Blumrosen, Liad}, Computationally-feasible truthful auctions for convex bundles, 27-38 [Zbl 1106.91313] \textit{Berman, Piotr; DasGupta, Bhaskar; Sontag, Eduardo}, Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks, 39-50 [Zbl 1106.68432] \textit{Bilò, Vittorio; Goyal, Vineet; Ravi, R.; Singh, Mohit}, On the crossing spanning tree problem, 51-60 [Zbl 1106.68374] \textit{Bläser, Markus}, A 3/4-approximation algorithm for maximum ATSP with weights zero and one, 61-71 [Zbl 1106.90061] \textit{Chekuri, Chandra; Kumar, Amit}, Maximum coverage problem with group budget constraints and applications, 72-83 [Zbl 1106.90062] \textit{Chrobak, Marek; Kolman, Petr; Sgall, Jiří}, The greedy algorithm for the minimum common string partition problem, 84-95 [Zbl 1106.68434] \textit{Dhamdhere, Kedar}, Approximating additive distortion of embeddings into line metrics, 96-104 [Zbl 1106.68435] \textit{Elkin, Michael; Kortsarz, Guy}, Polylogarithmic inapproximability of the radio broadcast problem (extended abstract), 105-116 [Zbl 1105.68302] \textit{Feige, Uriel; Reichman, Daniel}, On systems of linear equations with two variables per equation, 117-127 [Zbl 1105.68047] \textit{Garg, Rahul; Kapoor, Sanjiv; Vazirani, Vijay}, An auction-based market equilibrium algorithm for the separable gross substitutability case, 128-138 [Zbl 1105.91303] \textit{Gupta, Anupam; Srinivasan, Aravind; Tardos, Éva}, Cost-sharing mechanisms for network design, 139-150 [Zbl 1105.68304] \textit{Hast, Gustav}, Approximating Max \(k\)CSP using random restrictions, 151-162 [Zbl 1105.68462] \textit{Khuller, Samir; Kim, Yoo-Ah; Woeginger, Gerhard}, Approximation schemes for broadcasting in heterogeneous networks, 163-170 [Zbl 1105.68307] \textit{Kowalski, Dariusz R.; Pelc, Andrzej}, Centralized deterministic broadcasting in undirected multi-hop radio networks, 171-182 [Zbl 1105.68308] \textit{Mirrokni, Vahab S.; Vetta, Adrian}, Convergence issues in competitive games, 183-194 [Zbl 1105.91300] \textit{Newman, Alantha}, Cuts and orderings: On semidefinite relaxations for the linear ordering problem, 195-206 [Zbl 1105.90358] \textit{Svitkina, Zoya; Tardos, Éva}, Min-max multiway cut, 207-218 [Zbl 1105.68313] \textit{Achlioptas, Dimitris; Moore, Cristopher}, The chromatic number of random regular graphs, 219-228 [Zbl 1105.05063] \textit{Ailon, Nir; Chazelle, Bernard; Comandur, Seshadhri; Liu, Ding}, Estimating the distance to a monotone function, 229-236 [Zbl 1105.68420] \textit{Alon, Noga; Asodi, Vera}, Edge coloring with delays, 237-248 [Zbl 1105.90014] \textit{Ambainis, Andris; Smith, Adam}, Small pseudo-random families of matrices: Derandomizing approximate quantum encryption, 249-260 [Zbl 1105.68343] \textit{Bar-Yossef, Ziv; Jayram, T. S.; Krauthgamer, Robert; Kumar, Ravi}, The sketching complexity of pattern matching, 261-272 [Zbl 1105.68460] \textit{Ben Or, Michael; Coppersmith, Don; Luby, Mike; Rubinfeld, Ronitt}, Non-abelian homomorphism testing, and distributions close to their self-convolutions, 273-285 [Zbl 1105.68119] \textit{Ben-Sasson, Eli; Sudan, Madhu}, Robust locally testable codes and products of codes, 286-297 [Zbl 1105.68346] \textit{Bogdanov, Andrej; Wee, Hoeteck}, A stateful implementation of a random function supporting parity queries over hypercubes, 298-309 [Zbl 1105.68461] \textit{Coja-Oghlan, Amin; Goerdt, Andreas; Lanka, André}, Strong refutation heuristics for random \(k\)-SAT, 310-321 [Zbl 1105.68423] \textit{Coja-Oghlan, Amin; Moore, Cristopher; Sanwalani, Vishal}, Counting connected graphs and hypergraphs via the probabilistic method, 322-333 [Zbl 1105.05035] \textit{Dodis, Yevgeniy; Elbaz, Ariel; Oliveira, Roberto; Raz, Ran}, Improved randomness extraction from two independent sources, 334-344 [Zbl 1106.68036] \textit{Flaxman, Abraham D.; Frieze, Alan M.}, The diameter of randomly perturbed digraphs and some applications, 345-356 [Zbl 1106.68082] \textit{Gamarnik, David; Nowicki, Tomasz; Swirszcz, Grzegorz}, Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method., 357-368 [Zbl 1111.05089] \textit{Ganguly, Sumit}, Estimating frequency moments of data streams using random linear combinations, 369-380 [Zbl 1106.68366] \textit{Gutfreund, Dan; Viola, Emanuele}, Fooling parity tests with parity gates, 381-392 [Zbl 1106.68368] \textit{Halevy, Shirley; Kushilevitz, Eyal}, Distribution-free connectivity testing, 393-404 [Zbl 1106.68375] \textit{Langberg, Michael}, Testing the independence number of hypergraphs, 405-416 [Zbl 1106.68376] \textit{Trevisan, Luca}, A note on approximate counting for \(k\)-DNF, 417-425 [Zbl 1106.68427]