“Balls into Bins” — A Simple and Tight Analysis View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1998

AUTHORS

Martin Raab , Angelika Steger

ABSTRACT

Suppose we sequentially throw m balls into n bins. It is a natural question to ask for the maximum number of balls in any bin. In this paper we shall derive sharp upper and lower bounds which are reached with high probability. We prove bounds for all values of m(n) ≧ n/polylog(n) by using the simple and well-known method of the first and second moment. More... »

PAGES

159-170

Book

TITLE

Randomization and Approximation Techniques in Computer Science

ISBN

978-3-540-65142-0
978-3-540-49543-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-49543-6_13

DOI

http://dx.doi.org/10.1007/3-540-49543-6_13

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1038366427


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, D-80290\u00a0M\u00fcnchen"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Raab", 
        "givenName": "Martin", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, D-80290\u00a0M\u00fcnchen"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Steger", 
        "givenName": "Angelika", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/322248.322254", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011671553"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "Suppose we sequentially throw m balls into n bins. It is a natural question to ask for the maximum number of balls in any bin. In this paper we shall derive sharp upper and lower bounds which are reached with high probability. We prove bounds for all values of m(n) \u2267 n/polylog(n) by using the simple and well-known method of the first and second moment.", 
    "editor": [
      {
        "familyName": "Luby", 
        "givenName": "Michael", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Serna", 
        "givenName": "Maria", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-49543-6_13", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-65142-0", 
        "978-3-540-49543-7"
      ], 
      "name": "Randomization and Approximation Techniques in Computer Science", 
      "type": "Book"
    }, 
    "name": "\u201cBalls into Bins\u201d \u2014 A Simple and Tight Analysis", 
    "pagination": "159-170", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-49543-6_13"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b6c325520d94a75049d17dc4593bb8286d00da6f3f66fa4c74794f66b2b76ea6"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038366427"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-49543-6_13", 
      "https://app.dimensions.ai/details/publication/pub.1038366427"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T20:07", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8687_00000267.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-49543-6_13"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-49543-6_13'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-49543-6_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-49543-6_13'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-49543-6_13'


 

This table displays all metadata directly associated to this object as RDF triples.

84 TRIPLES      23 PREDICATES      28 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-49543-6_13 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author Na422c38681cf4dc0ba9ea0fd3ed35a0e
4 schema:citation https://doi.org/10.1145/322248.322254
5 schema:datePublished 1998
6 schema:datePublishedReg 1998-01-01
7 schema:description Suppose we sequentially throw m balls into n bins. It is a natural question to ask for the maximum number of balls in any bin. In this paper we shall derive sharp upper and lower bounds which are reached with high probability. We prove bounds for all values of m(n) ≧ n/polylog(n) by using the simple and well-known method of the first and second moment.
8 schema:editor Nce73928907f54d90af2f18822cb8b089
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf Naefd807752d747cbaddd79f89097f6dd
13 schema:name “Balls into Bins” — A Simple and Tight Analysis
14 schema:pagination 159-170
15 schema:productId N2400b1022d314bb5b1a0b4fffd791682
16 N36062deb97544f2082c448e5d3d1ebb6
17 N8fed7bec27ef45a3b078e199aaf8540f
18 schema:publisher Nc3216e895efc427ca2f33487485ebf0b
19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038366427
20 https://doi.org/10.1007/3-540-49543-6_13
21 schema:sdDatePublished 2019-04-15T20:07
22 schema:sdLicense https://scigraph.springernature.com/explorer/license/
23 schema:sdPublisher Na3feed039cdf4e90b008b9370897b508
24 schema:url http://link.springer.com/10.1007/3-540-49543-6_13
25 sgo:license sg:explorer/license/
26 sgo:sdDataset chapters
27 rdf:type schema:Chapter
28 N0df4f5e82669457e8cf63c1bb74d268e schema:familyName Serna
29 schema:givenName Maria
30 rdf:type schema:Person
31 N1957952756ee45f59a4c18c439c841cd rdf:first N64de455001d146c9b6264ebd467da2ef
32 rdf:rest rdf:nil
33 N2400b1022d314bb5b1a0b4fffd791682 schema:name dimensions_id
34 schema:value pub.1038366427
35 rdf:type schema:PropertyValue
36 N31f5e334219141e3b75d4fba79b9c907 schema:familyName Luby
37 schema:givenName Michael
38 rdf:type schema:Person
39 N36062deb97544f2082c448e5d3d1ebb6 schema:name doi
40 schema:value 10.1007/3-540-49543-6_13
41 rdf:type schema:PropertyValue
42 N54b5263008954649b7c6483e888610ae schema:name Institut für Informatik, Technische Universität München, D-80290 München
43 rdf:type schema:Organization
44 N5798f6f89d3647509bb53e473b68db50 rdf:first N0df4f5e82669457e8cf63c1bb74d268e
45 rdf:rest rdf:nil
46 N64de455001d146c9b6264ebd467da2ef schema:affiliation N54b5263008954649b7c6483e888610ae
47 schema:familyName Steger
48 schema:givenName Angelika
49 rdf:type schema:Person
50 N7286062ed6894518b12c1ec3c98eb128 schema:familyName Rolim
51 schema:givenName José D. P.
52 rdf:type schema:Person
53 N8fed7bec27ef45a3b078e199aaf8540f schema:name readcube_id
54 schema:value b6c325520d94a75049d17dc4593bb8286d00da6f3f66fa4c74794f66b2b76ea6
55 rdf:type schema:PropertyValue
56 Na3feed039cdf4e90b008b9370897b508 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 Na422c38681cf4dc0ba9ea0fd3ed35a0e rdf:first Nc6de22de691b4591be977149d1347f21
59 rdf:rest N1957952756ee45f59a4c18c439c841cd
60 Na5cdc8a39af146c592ffee9b54dac695 schema:name Institut für Informatik, Technische Universität München, D-80290 München
61 rdf:type schema:Organization
62 Naefd807752d747cbaddd79f89097f6dd schema:isbn 978-3-540-49543-7
63 978-3-540-65142-0
64 schema:name Randomization and Approximation Techniques in Computer Science
65 rdf:type schema:Book
66 Nc3216e895efc427ca2f33487485ebf0b schema:location Berlin, Heidelberg
67 schema:name Springer Berlin Heidelberg
68 rdf:type schema:Organisation
69 Nc3ab72915b114cc7a0de65012812e448 rdf:first N7286062ed6894518b12c1ec3c98eb128
70 rdf:rest N5798f6f89d3647509bb53e473b68db50
71 Nc6de22de691b4591be977149d1347f21 schema:affiliation Na5cdc8a39af146c592ffee9b54dac695
72 schema:familyName Raab
73 schema:givenName Martin
74 rdf:type schema:Person
75 Nce73928907f54d90af2f18822cb8b089 rdf:first N31f5e334219141e3b75d4fba79b9c907
76 rdf:rest Nc3ab72915b114cc7a0de65012812e448
77 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
78 schema:name Mathematical Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
81 schema:name Statistics
82 rdf:type schema:DefinedTerm
83 https://doi.org/10.1145/322248.322254 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011671553
84 rdf:type schema:CreativeWork
 




Preview window. Press ESC to close (or click here)


...