Online perfect matching and mobile computing View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1995

AUTHORS

Edward F. Grove , Ming-Yang Kao , P. Krishnan , Jeffrey Scott Vitter

ABSTRACT

When each customer can be connected to at most two stations: Some intuitive algorithms have lower bounds of Ω(n) and Ω(n/log n). When the station capacities are 1, there is an upper bound of O(√n). When customers do not disconnect and the station capacity is 1, we achieve a competitive ratio of O(log n). There is a lower bound of Ω(√n) when the station capacities are 2. We present optimal algorithms when the station capacity is arbitrary in special cases. More... »

PAGES

194-205

Book

TITLE

Algorithms and Data Structures

ISBN

978-3-540-60220-0
978-3-540-44747-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-60220-8_62

DOI

http://dx.doi.org/10.1007/3-540-60220-8_62

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708\u00a0Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Grove", 
        "givenName": "Edward F.", 
        "id": "sg:person.016575751247.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016575751247.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708\u00a0Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kao", 
        "givenName": "Ming-Yang", 
        "id": "sg:person.011536202643.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011536202643.55"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708\u00a0Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Krishnan", 
        "givenName": "P.", 
        "id": "sg:person.013030315627.56", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013030315627.56"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708\u00a0Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "Jeffrey Scott", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1995", 
    "datePublishedReg": "1995-01-01", 
    "description": "When each customer can be connected to at most two stations: Some intuitive algorithms have lower bounds of \u03a9(n) and \u03a9(n/log n). When the station capacities are 1, there is an upper bound of O(\u221an). When customers do not disconnect and the station capacity is 1, we achieve a competitive ratio of O(log n). There is a lower bound of \u03a9(\u221an) when the station capacities are 2. We present optimal algorithms when the station capacity is arbitrary in special cases.", 
    "editor": [
      {
        "familyName": "Akl", 
        "givenName": "Selim G.", 
        "type": "Person"
      }, 
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Santoro", 
        "givenName": "Nicola", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-60220-8_62", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3382805", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3390996", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-540-60220-0", 
        "978-3-540-44747-4"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "name": "Online perfect matching and mobile computing", 
    "pagination": "194-205", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-60220-8_62"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f9ce37ed522206ab5c23d720268acae1b5c70698c56ba83930e10187a7052c7e"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052443567"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-60220-8_62", 
      "https://app.dimensions.ai/details/publication/pub.1052443567"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T19:56", 
    "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_00000090.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-60220-8_62"
  }
]
 

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-60220-8_62'

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-60220-8_62'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-60220-8_62'

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-60220-8_62'


 

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

105 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-60220-8_62 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N80eed0a707114845b314356ad052f5f8
4 schema:datePublished 1995
5 schema:datePublishedReg 1995-01-01
6 schema:description When each customer can be connected to at most two stations: Some intuitive algorithms have lower bounds of Ω(n) and Ω(n/log n). When the station capacities are 1, there is an upper bound of O(√n). When customers do not disconnect and the station capacity is 1, we achieve a competitive ratio of O(log n). There is a lower bound of Ω(√n) when the station capacities are 2. We present optimal algorithms when the station capacity is arbitrary in special cases.
7 schema:editor N6cc6082a7b0649e5a78302f042ef3782
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N41a0e955cda248ca96753ab5313f30a7
12 schema:name Online perfect matching and mobile computing
13 schema:pagination 194-205
14 schema:productId N23826c9da45847eb84623ceef5925bdf
15 N79a5293a92134c8fb46a98c02123e919
16 Ncc6782b0d032452ca7ea3400589850a2
17 schema:publisher Nd4f36d2ebaf44d4e8a74dd25c76b1f7a
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052443567
19 https://doi.org/10.1007/3-540-60220-8_62
20 schema:sdDatePublished 2019-04-15T19:56
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N102a4a6ea98b4d239741dea44fd56ee8
23 schema:url http://link.springer.com/10.1007/3-540-60220-8_62
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N102a4a6ea98b4d239741dea44fd56ee8 schema:name Springer Nature - SN SciGraph project
28 rdf:type schema:Organization
29 N11352a6c6fd14d298b32e0ed835057b1 schema:familyName Santoro
30 schema:givenName Nicola
31 rdf:type schema:Person
32 N23826c9da45847eb84623ceef5925bdf schema:name doi
33 schema:value 10.1007/3-540-60220-8_62
34 rdf:type schema:PropertyValue
35 N41a0e955cda248ca96753ab5313f30a7 schema:isbn 978-3-540-44747-4
36 978-3-540-60220-0
37 schema:name Algorithms and Data Structures
38 rdf:type schema:Book
39 N4738a22955414ceebb7d3807bda902d1 rdf:first sg:person.011536202643.55
40 rdf:rest Nd60bb649864549f389680128c71acaf8
41 N6cc6082a7b0649e5a78302f042ef3782 rdf:first Nb04b3d41d70d408dab956e754ece2caa
42 rdf:rest Nc7f7a2ab5f3e40bfabe9c25eac6e4d96
43 N79a5293a92134c8fb46a98c02123e919 schema:name readcube_id
44 schema:value f9ce37ed522206ab5c23d720268acae1b5c70698c56ba83930e10187a7052c7e
45 rdf:type schema:PropertyValue
46 N80eed0a707114845b314356ad052f5f8 rdf:first sg:person.016575751247.52
47 rdf:rest N4738a22955414ceebb7d3807bda902d1
48 N91047d0e27f2476a8cca9c6f8f2b733d schema:familyName Dehne
49 schema:givenName Frank
50 rdf:type schema:Person
51 Na9179c2c615b47ba975f56172ee78820 schema:familyName Sack
52 schema:givenName Jörg-Rüdiger
53 rdf:type schema:Person
54 Nb04b3d41d70d408dab956e754ece2caa schema:familyName Akl
55 schema:givenName Selim G.
56 rdf:type schema:Person
57 Nc7f7a2ab5f3e40bfabe9c25eac6e4d96 rdf:first N91047d0e27f2476a8cca9c6f8f2b733d
58 rdf:rest Ne03f743692404752b029faba324a44df
59 Ncc6782b0d032452ca7ea3400589850a2 schema:name dimensions_id
60 schema:value pub.1052443567
61 rdf:type schema:PropertyValue
62 Nd400a632699c4e34841cabe377d2dc4b rdf:first sg:person.0613677314.28
63 rdf:rest rdf:nil
64 Nd4f36d2ebaf44d4e8a74dd25c76b1f7a schema:location Berlin, Heidelberg
65 schema:name Springer Berlin Heidelberg
66 rdf:type schema:Organisation
67 Nd60bb649864549f389680128c71acaf8 rdf:first sg:person.013030315627.56
68 rdf:rest Nd400a632699c4e34841cabe377d2dc4b
69 Ne03f743692404752b029faba324a44df rdf:first Na9179c2c615b47ba975f56172ee78820
70 rdf:rest Nf82e032b40854c3f8cc9f06f4f03bfe5
71 Nf82e032b40854c3f8cc9f06f4f03bfe5 rdf:first N11352a6c6fd14d298b32e0ed835057b1
72 rdf:rest rdf:nil
73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
74 schema:name Information and Computing Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
77 schema:name Artificial Intelligence and Image Processing
78 rdf:type schema:DefinedTerm
79 sg:grant.3382805 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-60220-8_62
80 rdf:type schema:MonetaryGrant
81 sg:grant.3390996 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-60220-8_62
82 rdf:type schema:MonetaryGrant
83 sg:person.011536202643.55 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
84 schema:familyName Kao
85 schema:givenName Ming-Yang
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011536202643.55
87 rdf:type schema:Person
88 sg:person.013030315627.56 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
89 schema:familyName Krishnan
90 schema:givenName P.
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013030315627.56
92 rdf:type schema:Person
93 sg:person.016575751247.52 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
94 schema:familyName Grove
95 schema:givenName Edward F.
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016575751247.52
97 rdf:type schema:Person
98 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
99 schema:familyName Vitter
100 schema:givenName Jeffrey Scott
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
102 rdf:type schema:Person
103 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
104 schema:name Department of Computer Science, Duke University, 27708 Durham, NC, USA
105 rdf:type schema:Organization
 




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


...