Admission Control to Minimize Rejections View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001-08-02

AUTHORS

Avrim Blum , Adam Kalai , Jon Kleinberg

ABSTRACT

Admission control (call control) is a well-studied online problem. We are given a fixed graph with edge capacities, and must process a sequence of calls that arrive over time, accepting some and rejecting others in order to stay within capacity limitations of the network. In the standard theoretical formulation, this problem is analyzed as a benefit problem: the goal is to devise an online algorithm that accepts at least a reasonable fraction of the maximum number of calls that could possibly have been accepted in hindsight. This formulation, however, has the property that even algorithms with optimal competitive ratios (typically O(logn)) may end up rejecting the vast majority of calls even when it would have been possible in hindsight to reject only very few.In this paper, we instead consider the goal of approximately minimizing the number of calls rejected. This is much more natural for real-world settings in which rejections are intended to be rare events. In order to avoid trivial lower-bounds, we assume preemption is allowed and that calls are given to the algorithm as fixed paths. We show that in a number of cases, we can in fact achieve a competitive ratio of 2 for rejections (so if the optimal in hindsight rejects 0 then we reject 0; if the optimal rejects r then we reject at most 2r). For other cases we get worse but nontrivial bounds. For the most general case of fixed paths in arbitrary graphs with arbitrary edge capacities, we achieve matching Θ(√m) upper and lower bounds. We also show a connection between these problems and online versions of the vertex-cover and set-cover problems (our factor-2 results give 2-approximations to slight generalizations of the vertex cover problem, much as [AAA99] show hardness results for the benefit version based on the hardness of approximability of independent set). More... »

PAGES

155-164

Book

TITLE

Algorithms and Data Structures

ISBN

978-3-540-42423-9
978-3-540-44634-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44634-6_15

DOI

http://dx.doi.org/10.1007/3-540-44634-6_15

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Carnegie Mellon University, 15213, Pittsburgh, PA", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "Carnegie Mellon University, 15213, Pittsburgh, PA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Blum", 
        "givenName": "Avrim", 
        "id": "sg:person.010510241243.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010510241243.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Carnegie Mellon University, 15213, Pittsburgh, PA", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "Carnegie Mellon University, 15213, Pittsburgh, PA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kalai", 
        "givenName": "Adam", 
        "id": "sg:person.013013307227.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013013307227.68"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University, 14853, Ithaca, NY", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, 14853, Ithaca, NY"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kleinberg", 
        "givenName": "Jon", 
        "id": "sg:person.011522233557.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-08-02", 
    "datePublishedReg": "2001-08-02", 
    "description": "Admission control (call control) is a well-studied online problem. We are given a fixed graph with edge capacities, and must process a sequence of calls that arrive over time, accepting some and rejecting others in order to stay within capacity limitations of the network. In the standard theoretical formulation, this problem is analyzed as a benefit problem: the goal is to devise an online algorithm that accepts at least a reasonable fraction of the maximum number of calls that could possibly have been accepted in hindsight. This formulation, however, has the property that even algorithms with optimal competitive ratios (typically O(logn)) may end up rejecting the vast majority of calls even when it would have been possible in hindsight to reject only very few.In this paper, we instead consider the goal of approximately minimizing the number of calls rejected. This is much more natural for real-world settings in which rejections are intended to be rare events. In order to avoid trivial lower-bounds, we assume preemption is allowed and that calls are given to the algorithm as fixed paths. We show that in a number of cases, we can in fact achieve a competitive ratio of 2 for rejections (so if the optimal in hindsight rejects 0 then we reject 0; if the optimal rejects r then we reject at most 2r). For other cases we get worse but nontrivial bounds. For the most general case of fixed paths in arbitrary graphs with arbitrary edge capacities, we achieve matching \u0398(\u221am) upper and lower bounds. We also show a connection between these problems and online versions of the vertex-cover and set-cover problems (our factor-2 results give 2-approximations to slight generalizations of the vertex cover problem, much as [AAA99] show hardness results for the benefit version based on the hardness of approximability of independent set).", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Tamassia", 
        "givenName": "Roberto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44634-6_15", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42423-9", 
        "978-3-540-44634-7"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "admission control", 
      "competitive ratio", 
      "set-covering problem", 
      "sequence of calls", 
      "arbitrary edge capacities", 
      "edge capacities", 
      "online algorithm", 
      "optimal competitive ratio", 
      "online problem", 
      "arbitrary graphs", 
      "algorithm", 
      "benefit problem", 
      "number of calls", 
      "real-world setting", 
      "graph", 
      "online version", 
      "capacity limitations", 
      "lower bounds", 
      "maximum number", 
      "network", 
      "path", 
      "preemption", 
      "reasonable fraction", 
      "bounds", 
      "calls", 
      "goal", 
      "nontrivial bounds", 
      "general case", 
      "order", 
      "version", 
      "number", 
      "limitations", 
      "hindsight", 
      "connection", 
      "control", 
      "formulation", 
      "theoretical formulation", 
      "time", 
      "sequence", 
      "rare event", 
      "fact", 
      "cases", 
      "capacity", 
      "setting", 
      "vast majority", 
      "events", 
      "number of cases", 
      "properties", 
      "rejection", 
      "ratio", 
      "majority", 
      "fraction", 
      "problem", 
      "paper", 
      "standard theoretical formulation"
    ], 
    "name": "Admission Control to Minimize Rejections", 
    "pagination": "155-164", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1023674652"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44634-6_15"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44634-6_15", 
      "https://app.dimensions.ai/details/publication/pub.1023674652"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_294.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44634-6_15"
  }
]
 

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-44634-6_15'

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-44634-6_15'

Turtle is a human-readable linked data format.

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

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-44634-6_15'


 

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

142 TRIPLES      23 PREDICATES      80 URIs      73 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44634-6_15 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N24f6600c87d74b51adbae0557e2fea34
4 schema:datePublished 2001-08-02
5 schema:datePublishedReg 2001-08-02
6 schema:description Admission control (call control) is a well-studied online problem. We are given a fixed graph with edge capacities, and must process a sequence of calls that arrive over time, accepting some and rejecting others in order to stay within capacity limitations of the network. In the standard theoretical formulation, this problem is analyzed as a benefit problem: the goal is to devise an online algorithm that accepts at least a reasonable fraction of the maximum number of calls that could possibly have been accepted in hindsight. This formulation, however, has the property that even algorithms with optimal competitive ratios (typically O(logn)) may end up rejecting the vast majority of calls even when it would have been possible in hindsight to reject only very few.In this paper, we instead consider the goal of approximately minimizing the number of calls rejected. This is much more natural for real-world settings in which rejections are intended to be rare events. In order to avoid trivial lower-bounds, we assume preemption is allowed and that calls are given to the algorithm as fixed paths. We show that in a number of cases, we can in fact achieve a competitive ratio of 2 for rejections (so if the optimal in hindsight rejects 0 then we reject 0; if the optimal rejects r then we reject at most 2r). For other cases we get worse but nontrivial bounds. For the most general case of fixed paths in arbitrary graphs with arbitrary edge capacities, we achieve matching Θ(√m) upper and lower bounds. We also show a connection between these problems and online versions of the vertex-cover and set-cover problems (our factor-2 results give 2-approximations to slight generalizations of the vertex cover problem, much as [AAA99] show hardness results for the benefit version based on the hardness of approximability of independent set).
7 schema:editor Nc42137ef8ff14809bc1dcb2c3712d397
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N875ec9cf869d460b96e7a38aef67b8d6
12 schema:keywords admission control
13 algorithm
14 arbitrary edge capacities
15 arbitrary graphs
16 benefit problem
17 bounds
18 calls
19 capacity
20 capacity limitations
21 cases
22 competitive ratio
23 connection
24 control
25 edge capacities
26 events
27 fact
28 formulation
29 fraction
30 general case
31 goal
32 graph
33 hindsight
34 limitations
35 lower bounds
36 majority
37 maximum number
38 network
39 nontrivial bounds
40 number
41 number of calls
42 number of cases
43 online algorithm
44 online problem
45 online version
46 optimal competitive ratio
47 order
48 paper
49 path
50 preemption
51 problem
52 properties
53 rare event
54 ratio
55 real-world setting
56 reasonable fraction
57 rejection
58 sequence
59 sequence of calls
60 set-covering problem
61 setting
62 standard theoretical formulation
63 theoretical formulation
64 time
65 vast majority
66 version
67 schema:name Admission Control to Minimize Rejections
68 schema:pagination 155-164
69 schema:productId Nc6f250b5f14b4fa0a13a7694c8d7bea9
70 Nedd8c2292cdc446493ff65e584e7e547
71 schema:publisher N0f4ab1adf79d4030be48789456a1b216
72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023674652
73 https://doi.org/10.1007/3-540-44634-6_15
74 schema:sdDatePublished 2022-01-01T19:16
75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
76 schema:sdPublisher N441c3663b2b24684b71b5c18cfa4c6b9
77 schema:url https://doi.org/10.1007/3-540-44634-6_15
78 sgo:license sg:explorer/license/
79 sgo:sdDataset chapters
80 rdf:type schema:Chapter
81 N0527c2cc57b34510a9ab8d78f730ab79 rdf:first Nd5a0f93356f940b6824381fccadced1e
82 rdf:rest Na225339c309b412e95a0b659d3b93f5f
83 N0f4ab1adf79d4030be48789456a1b216 schema:name Springer Nature
84 rdf:type schema:Organisation
85 N24f6600c87d74b51adbae0557e2fea34 rdf:first sg:person.010510241243.49
86 rdf:rest N37c6d33ea87a4b29b332dba6e2fc939a
87 N37c6d33ea87a4b29b332dba6e2fc939a rdf:first sg:person.013013307227.68
88 rdf:rest Ne6aea22af50747608b5ab50d59aa2518
89 N441c3663b2b24684b71b5c18cfa4c6b9 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 N546a869594f14bf98d9b7f2d5f1199b0 schema:familyName Tamassia
92 schema:givenName Roberto
93 rdf:type schema:Person
94 N875ec9cf869d460b96e7a38aef67b8d6 schema:isbn 978-3-540-42423-9
95 978-3-540-44634-7
96 schema:name Algorithms and Data Structures
97 rdf:type schema:Book
98 N9263ac4fb73c44b38a0ec2bd94ed85d6 schema:familyName Dehne
99 schema:givenName Frank
100 rdf:type schema:Person
101 Na225339c309b412e95a0b659d3b93f5f rdf:first N546a869594f14bf98d9b7f2d5f1199b0
102 rdf:rest rdf:nil
103 Nc42137ef8ff14809bc1dcb2c3712d397 rdf:first N9263ac4fb73c44b38a0ec2bd94ed85d6
104 rdf:rest N0527c2cc57b34510a9ab8d78f730ab79
105 Nc6f250b5f14b4fa0a13a7694c8d7bea9 schema:name doi
106 schema:value 10.1007/3-540-44634-6_15
107 rdf:type schema:PropertyValue
108 Nd5a0f93356f940b6824381fccadced1e schema:familyName Sack
109 schema:givenName Jörg-Rüdiger
110 rdf:type schema:Person
111 Ne6aea22af50747608b5ab50d59aa2518 rdf:first sg:person.011522233557.04
112 rdf:rest rdf:nil
113 Nedd8c2292cdc446493ff65e584e7e547 schema:name dimensions_id
114 schema:value pub.1023674652
115 rdf:type schema:PropertyValue
116 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
117 schema:name Information and Computing Sciences
118 rdf:type schema:DefinedTerm
119 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
120 schema:name Artificial Intelligence and Image Processing
121 rdf:type schema:DefinedTerm
122 sg:person.010510241243.49 schema:affiliation grid-institutes:grid.147455.6
123 schema:familyName Blum
124 schema:givenName Avrim
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010510241243.49
126 rdf:type schema:Person
127 sg:person.011522233557.04 schema:affiliation grid-institutes:grid.5386.8
128 schema:familyName Kleinberg
129 schema:givenName Jon
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04
131 rdf:type schema:Person
132 sg:person.013013307227.68 schema:affiliation grid-institutes:grid.147455.6
133 schema:familyName Kalai
134 schema:givenName Adam
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013013307227.68
136 rdf:type schema:Person
137 grid-institutes:grid.147455.6 schema:alternateName Carnegie Mellon University, 15213, Pittsburgh, PA
138 schema:name Carnegie Mellon University, 15213, Pittsburgh, PA
139 rdf:type schema:Organization
140 grid-institutes:grid.5386.8 schema:alternateName Cornell University, 14853, Ithaca, NY
141 schema:name Cornell University, 14853, Ithaca, NY
142 rdf:type schema:Organization
 




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


...