Get 40% off of select print and eBooks in Engineering & Materials Science!

Lecture Notes in Computer Science

Randomization and Approximation Techniques in Computer Science

International Workshop RANDOM'97, Bologna, Italy, July 11-12, 1997 Proceedings

Editors: Rolim, Jose (Ed.)

Free Preview

Buy this book

eBook $69.99
price for USA in USD (gross)
  • The eBook version of this title will be available soon
  • ISBN 978-3-540-69247-8
  • Digitally watermarked, DRM-free
  • Included format:
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $89.99
price for USA in USD
  • ISBN 978-3-540-63248-1
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this book

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 from 37 submissions; also included are four invited contributions by leading researchers. The book focuses on algorithms and complexity aspects arising in the development of efficient randomized solutions to computationally difficult problems. The papers are organized in sections on approximation, randomness, algorithms, and complexity.

Table of contents (18 chapters)

Table of contents (18 chapters)
  • Polynomial time approximation schemes for some dense instances of NP-hard optimization problems

    Pages 1-14

    Karpinski, Marek

  • Average-case complexity of shortest-paths problems in the vertex-potential model

    Pages 15-26

    Cooper, Colin (et al.)

  • Approximation algorithms for covering polygons with squares and similar problems

    Pages 27-41

    Levcopoulos, Christos (et al.)

  • Greedily approximating the r-independent set and k-center problems on random instances

    Pages 43-53

    Kreuter, Bernd (et al.)

  • Nearly linear time approximation schemes for Euclidean TSP and other geometric problems

    Pages 55-55

    Arora, Sanjeev

Buy this book

eBook $69.99
price for USA in USD (gross)
  • The eBook version of this title will be available soon
  • ISBN 978-3-540-69247-8
  • Digitally watermarked, DRM-free
  • Included format:
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $89.99
price for USA in USD
  • ISBN 978-3-540-63248-1
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Services for this Book

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Randomization and Approximation Techniques in Computer Science
Book Subtitle
International Workshop RANDOM'97, Bologna, Italy, July 11-12, 1997 Proceedings
Editors
  • Jose Rolim
Series Title
Lecture Notes in Computer Science
Series Volume
1269
Copyright
1997
Publisher
Springer-Verlag Berlin Heidelberg
Copyright Holder
Springer-Verlag Berlin Heidelberg
eBook ISBN
978-3-540-69247-8
DOI
10.1007/3-540-63248-4
Softcover ISBN
978-3-540-63248-1
Series ISSN
0302-9743
Edition Number
1
Number of Pages
VIII, 236
Topics