“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 N1b5caa09470d4640af7df83c8234a387
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 N95b7d9631d6e486090e068f562821434
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N1893892ccd034ad684277bc8449d8061
13 schema:name “Balls into Bins” — A Simple and Tight Analysis
14 schema:pagination 159-170
15 schema:productId N22c03502478241bfbbb36b0f04eee96c
16 Nc934c1f023c54a3cb6e487d101b3287b
17 Ne01790221f88419580d773d6432360f9
18 schema:publisher N29b18fd1ba654098a5331e326c4c73ef
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 N0237d5af9e42401484e542deec1ecf31
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 N01a67455d84545f28688a09b9a090edf rdf:first Naf793f1fecf74782859525dc10a3884b
29 rdf:rest rdf:nil
30 N0237d5af9e42401484e542deec1ecf31 schema:name Springer Nature - SN SciGraph project
31 rdf:type schema:Organization
32 N17889cd05c824fb38d0b9d487cf689ad rdf:first N3fd36f1372b74769b6edaf010d64aebd
33 rdf:rest N01a67455d84545f28688a09b9a090edf
34 N1893892ccd034ad684277bc8449d8061 schema:isbn 978-3-540-49543-7
35 978-3-540-65142-0
36 schema:name Randomization and Approximation Techniques in Computer Science
37 rdf:type schema:Book
38 N1b5caa09470d4640af7df83c8234a387 rdf:first Nfc71100b1bab4fa7a677d1d93f162e35
39 rdf:rest N1cb19daa7c44459abdcfb14ebfc3d375
40 N1cb19daa7c44459abdcfb14ebfc3d375 rdf:first Ned0683d9098c4b3d855cda37d7f29a2c
41 rdf:rest rdf:nil
42 N22c03502478241bfbbb36b0f04eee96c schema:name dimensions_id
43 schema:value pub.1038366427
44 rdf:type schema:PropertyValue
45 N29b18fd1ba654098a5331e326c4c73ef schema:location Berlin, Heidelberg
46 schema:name Springer Berlin Heidelberg
47 rdf:type schema:Organisation
48 N3fd36f1372b74769b6edaf010d64aebd schema:familyName Rolim
49 schema:givenName José D. P.
50 rdf:type schema:Person
51 N7155ec4157d4452b8c25887cb7cf3691 schema:name Institut für Informatik, Technische Universität München, D-80290 München
52 rdf:type schema:Organization
53 N95b7d9631d6e486090e068f562821434 rdf:first Nb3337b7e64604fbbb91e04b4ad1ada4e
54 rdf:rest N17889cd05c824fb38d0b9d487cf689ad
55 N9a6a152f388640849698fe02224b7931 schema:name Institut für Informatik, Technische Universität München, D-80290 München
56 rdf:type schema:Organization
57 Naf793f1fecf74782859525dc10a3884b schema:familyName Serna
58 schema:givenName Maria
59 rdf:type schema:Person
60 Nb3337b7e64604fbbb91e04b4ad1ada4e schema:familyName Luby
61 schema:givenName Michael
62 rdf:type schema:Person
63 Nc934c1f023c54a3cb6e487d101b3287b schema:name readcube_id
64 schema:value b6c325520d94a75049d17dc4593bb8286d00da6f3f66fa4c74794f66b2b76ea6
65 rdf:type schema:PropertyValue
66 Ne01790221f88419580d773d6432360f9 schema:name doi
67 schema:value 10.1007/3-540-49543-6_13
68 rdf:type schema:PropertyValue
69 Ned0683d9098c4b3d855cda37d7f29a2c schema:affiliation N7155ec4157d4452b8c25887cb7cf3691
70 schema:familyName Steger
71 schema:givenName Angelika
72 rdf:type schema:Person
73 Nfc71100b1bab4fa7a677d1d93f162e35 schema:affiliation N9a6a152f388640849698fe02224b7931
74 schema:familyName Raab
75 schema:givenName Martin
76 rdf:type schema:Person
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)


...