Randomization, Approximation, and Combinatorial Optimization,9783540663294

Randomization, Approximation, and Combinatorial Optimization

by
ISBN13: 9783540663294
ISBN10: 3540663290
Format: Paperback
Pub. Date: 1999-09-01
Publisher(s): Springer Verlag
  • Free Shipping Icon

    Free Shipping On Orders Over $59

    Free standard shipping on order over $59 to your home address. Marketplace purchases through third-party sellers are excluded from free shipping promotions.

List Price: $90.05

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

New Textbook

We're Sorry
Sold Out

Used Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $56.82

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

Summary

This book provides a general introduction to impact stratigraphy, with emphasis on the recognition of distal impact ejecta in the field, by focusing on the impactoclastic layers of the Umbria-Marche sequence in Central Italy, with an almost perfect stratigraphic record over the last 200 Million years. A general introduction to impact cratering and a discussion of distal ejecta and impact layers around the world is followed by a detailed description of the record of the impact of extraterrestrial bodies in sediments of the Umbria-Marche Apennines. The volume is of interest to a diverse audience in the geological and planetary sciences, ranging from (upper) undergraduate to research level. This book can also be used by students and researchers as a field guide to some of the most important Italian impact layers.

Table of Contents

Session Random 1
Completeness and Robustness Properties of Min-Wise Independent Permutations
1(10)
Andrei Z. Broder
Michael Mitzenmacher
Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families
11(5)
Michael Saks
Aravind Srinivasan
Shiyu Zhou
David Zuckerman
Session Approx 1
Independent Sets in Hypergraphs with Applications to Routing via Fixed Paths
16(12)
Noga Alon
Uri Arad
Yossi Azar
Approximating Minimum Manhattan Networks
28(11)
Joachim Gudmundsson
Christos Levcopoulos
Giri Narasimhan
Approximation of Multi-color Discrepancy
39(12)
Benjamin Doerr
Anand Srivastav
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
51(12)
Hans Kellerer
Session Approx 2
Set Cover with Requirements and Costs Evolving over Time
63(10)
Milena Mihail
Multicoloring Planar Graphs and Partial K-Trees
73(12)
Magnus M. Halldorsson
Guy Kortsarz
Session: Random 2
Testing the Diameter of Graphs
85(12)
Michal Parnas
Dana Ron
Improved Testing Algorithms for Monotonicity
97(12)
Yevgeniy Dodis
Oded Goldreich
Eric Lehman
Sofya Raskhodnikova
Dana Ron
Alex Samorodnitsky
Linear Consistency Testing
109(12)
Yonatan Aumann
Johan Hastad
Michael O. Rabin
Madhu Sudan
Improved Bounds for Sampling Contingency Tables
121(9)
Benjamin James Morris
Invited Talk
Probabilistic and Deterministic Approximations of the Permanent
130(1)
Avi Wigderson
Session Random 3
Improved Derandomization of BPP Using a Hitting Set Generator
131(7)
Oded Goldreich
Avi Wigderson
Probabilistic Construction of Small Strongly Sum-Free Sets via Large Sidon Sets
138(6)
Andreas Baltz
Tomasz Schoen
Anand Srivastav
Session Approx 3
Stochastic Machine Scheduling: Performance Guarantees for LP-based Priority Policies
144(12)
Rolf H. Mohring
Andreas S. Schulz
Marc Uetz
Efficient Redundant Assignments under Fault-Tolerance Constraints
156(12)
Dimitris A. Fotakis
Paul G. Spirakis
Scheduling with Machine Cost
168(9)
Csanad Imreh
John Noga
A Linear Time Approximation Scheme for the Job Shop Scheduling Problem
177(12)
Klaus Jansen
Roberto Solis-Oba
Maxim Sviridenko
Invited Talk
Randomized Rounding for Semidefinite Programs - Variations on the MAX CUT Example
189(8)
Uriel Feige
Session Approx 4
Hardness Results for the Power Range Assignment Problem in Packet Radio Networks
197(12)
Andrea E. F. Clementi
Paolo Penna
Riccardo Silvestri
A New Approximation Algorithm for the Demand Routing and Slotting Problem with Unit Demands on Rings
209(12)
Christine T. Cheng
Session Random 4
Algorithms for Graph Partitioning on the Planted Partition Model
221(12)
Anne E. Condon
Richard M. Karp
A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
233(12)
Seth Pettie
Vijaya Ramachandran
Fast Approximate PCPs for Multidimensional Bin-Packing Problems
245(12)
Tugkan Batu
Ronitt Rubinfeld
Patrick White
Pfaffian Algorithms for Sampling Routings on Regions with Free Boundary Conditions
257(12)
Russell A. Martin
Dana Randall
Minisymposium on Scheduling Talks
Klaus Jansen
Scheduling with Unexpected Machine Breakdowns
269(12)
Susanne Albers
Gunter Schmidt
Scheduling on a Constant Number of Machines
281(8)
F. Afrati
E. Bampis
C. Kenyon
I. Milis
Author Index 289

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.