Randomization and approximation techniques in computer science : international workshop RANDOM '97, Bologna, Italy, July 11-12,1997 : proceedings
This book constitutes the refereed proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97, held as a satelite meeting of ICALP'97, in Bologna, Italy, in July 1997. The volume presents 14 thoroughly revised full papers selected...
Guardado en:
| Autor Corporativo: | |
|---|---|
| Otros Autores: | |
| Formato: | Livre numérique |
| Lenguaje: | Anglais |
| Publicado: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Colección: | Lecture notes in computer science
1269 |
| Materias: | |
| Acceso en línea: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Nota: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Randomization and approximation techniques in computer science, international workshop RANDOM '97, Bologna, Italy, July 11-12,1997, proceedings, José Rolim, ed., 1997, New York, Springer, 1 vol. (VIII-225 p.), Lecture notes in computer science, 3-540-63248-4 • Randomization and Approximation Techniques in Computer Science, Texte imprimé, 9783662161517 |
Tabla de Contenidos:
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- Average-case complexity of shortest-paths problems in the vertex-potential model
- Approximation algorithms for covering polygons with squares and similar problems
- Greedily approximating the r-independent set and k-center problems on random instances
- Nearly linear time approximation schemes for Euclidean TSP and other geometric problems
- Random sampling of Euler tours
- A combinatorial consistency lemma with application to proving the PCP theorem
- Super-bits, demi-bits, and NP/qpoly-natural proofs
- Sample spaces with small bias on neighborhoods and error-correcting communication protocols
- Approximation on the web: A compendium of NP optimization problems
- Random-based scheduling new approximations and LP lower bounds
- Go with the winners generators with applications to molecular modeling
- Probabilistic approximation of some NP optimization problems by finite-state machines
- Using hard problems to derandomize algorithms: An incomplete survey
- Weak and strong recognition by 2-way randomized automata
- Tally languages accepted by Monte Carlo pushdown automata
- Resource-bounded randomness and compressibility with respect to nonuniform measures
- Randomness, stochasticity and approximations.