Scheduling with Calibrations for Multi-Interval Jobs Article Swipe
Vincent Chau
,
Christoph Damerius
,
Peter Kling
,
Minming Li
,
Florian Schneider
,
Ruilong Zhang
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.1287/ijoc.2023.0430
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.1287/ijoc.2023.0430
This paper studies a scheduling problem with machine calibrations for multi-interval jobs. More exactly, there are n (possibly weighted) jobs of unit size that must be scheduled on a single initially uncalibrated machine. The machine can process jobs only when calibrated, and such a calibration lasts for T time slots. The standard model by Bender et al. [Bender MA, Bunde DP, Leung VJ, McCauley S, Phillips CA (2013) Efficient scheduling to minimize calibrations. Blelloch GE, Vöcking B, eds. 25th ACM Sympos. Parallelism Algorithms Architectures SPAA ‘13 (ACM, New York), 280–287] assumes that each job has a release time and deadline between which it must be processed. We study a generalization in which each job must be processed during one of possibly many job-dependent time intervals. We consider two objectives: In the minimization version, our goal is to minimize the number of calibrations while scheduling all jobs. In the maximization version, our goal is to maximize the total weight of scheduled jobs while using at most B calibrations. For the minimization version, we present a logarithmic approximation algorithm. We also prove that the problem is set-cover hard, implying that our algorithm is optimal up to a constant factor unless P = NP. The special case when each job may be scheduled in at most two time slots is shown to be vertex-cover hard, implying that there is no [Formula: see text]-approximation algorithm based on the unique game conjecture. For the maximization version, we give an algorithm with approximation ratio [Formula: see text]. This improves upon the previously best-known algorithm, which has an approximation ratio of 1/3 [Chau V, Feng S, Li M, Wang Y, Zhang G, Zhang Y (2019) Weighted throughput maximization with calibrations. Friggstad Z, Sack JR, Salavatipour MR, eds. Algorithms Data Structures 16th Internat. Sympos. WADS 2019 Proc., Lecture Notes in Computer Science, vol. 11646 (Springer, New York), 311–324]. Moreover, we also prove that our bound on the approximation ratio is tight. Although all hardness results mentioned above hold for any [Formula: see text], we provide optimal polynomial-time algorithms for T = 2 in both the minimization version and the maximization version. Finally, we show that our methods can be extended into the m identical machines case by losing some running time, whereas all algorithmic results remain the same in both versions. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.0430 .
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1287/ijoc.2023.0430
- OA Status
- bronze
- References
- 16
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4409141242
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4409141242Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1287/ijoc.2023.0430Digital Object Identifier
- Title
-
Scheduling with Calibrations for Multi-Interval JobsWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-04-03Full publication date if available
- Authors
-
Vincent Chau, Christoph Damerius, Peter Kling, Minming Li, Florian Schneider, Ruilong ZhangList of authors in order
- Landing page
-
https://doi.org/10.1287/ijoc.2023.0430Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
bronzeOpen access status per OpenAlex
- OA URL
-
https://scholars.cityu.edu.hk/en/publications/scheduling-with-calibrations-for-multi-interval-jobsDirect OA link when available
- Concepts
-
Scheduling (production processes), Computer science, Mathematical optimization, Operations research, MathematicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- References (count)
-
16Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4409141242 |
|---|---|
| doi | https://doi.org/10.1287/ijoc.2023.0430 |
| ids.doi | https://doi.org/10.1287/ijoc.2023.0430 |
| ids.openalex | https://openalex.org/W4409141242 |
| fwci | 0.0 |
| type | article |
| title | Scheduling with Calibrations for Multi-Interval Jobs |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10551 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9998000264167786 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2209 |
| topics[0].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[0].display_name | Scheduling and Optimization Algorithms |
| topics[1].id | https://openalex.org/T12288 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9919999837875366 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | Optimization and Search Problems |
| topics[2].id | https://openalex.org/T12401 |
| topics[2].field.id | https://openalex.org/fields/18 |
| topics[2].field.display_name | Decision Sciences |
| topics[2].score | 0.9850999712944031 |
| topics[2].domain.id | https://openalex.org/domains/2 |
| topics[2].domain.display_name | Social Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1803 |
| topics[2].subfield.display_name | Management Science and Operations Research |
| topics[2].display_name | Scheduling and Timetabling Solutions |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C206729178 |
| concepts[0].level | 2 |
| concepts[0].score | 0.5969316363334656 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q2271896 |
| concepts[0].display_name | Scheduling (production processes) |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.5911062955856323 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C126255220 |
| concepts[2].level | 1 |
| concepts[2].score | 0.4456595778465271 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[2].display_name | Mathematical optimization |
| concepts[3].id | https://openalex.org/C42475967 |
| concepts[3].level | 1 |
| concepts[3].score | 0.4026905298233032 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q194292 |
| concepts[3].display_name | Operations research |
| concepts[4].id | https://openalex.org/C33923547 |
| concepts[4].level | 0 |
| concepts[4].score | 0.2336815893650055 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[4].display_name | Mathematics |
| keywords[0].id | https://openalex.org/keywords/scheduling |
| keywords[0].score | 0.5969316363334656 |
| keywords[0].display_name | Scheduling (production processes) |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.5911062955856323 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[2].score | 0.4456595778465271 |
| keywords[2].display_name | Mathematical optimization |
| keywords[3].id | https://openalex.org/keywords/operations-research |
| keywords[3].score | 0.4026905298233032 |
| keywords[3].display_name | Operations research |
| keywords[4].id | https://openalex.org/keywords/mathematics |
| keywords[4].score | 0.2336815893650055 |
| keywords[4].display_name | Mathematics |
| language | en |
| locations[0].id | doi:10.1287/ijoc.2023.0430 |
| locations[0].is_oa | False |
| locations[0].source.id | https://openalex.org/S165318533 |
| locations[0].source.issn | 1091-9856, 1526-5528 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | 1091-9856 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | INFORMS journal on computing |
| locations[0].source.host_organization | https://openalex.org/P4310315699 |
| locations[0].source.host_organization_name | Institute for Operations Research and the Management Sciences |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310315699 |
| locations[0].source.host_organization_lineage_names | Institute for Operations Research and the Management Sciences |
| locations[0].license | |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | INFORMS Journal on Computing |
| locations[0].landing_page_url | https://doi.org/10.1287/ijoc.2023.0430 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S165318533 |
| locations[1].source.issn | 1091-9856, 1526-5528 |
| locations[1].source.type | journal |
| locations[1].source.is_oa | False |
| locations[1].source.issn_l | 1091-9856 |
| locations[1].source.is_core | True |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | INFORMS journal on computing |
| locations[1].source.host_organization | https://openalex.org/P4310315699 |
| locations[1].source.host_organization_name | Institute for Operations Research and the Management Sciences |
| locations[1].source.host_organization_lineage | https://openalex.org/P4310315699 |
| locations[1].source.host_organization_lineage_names | Institute for Operations Research and the Management Sciences |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | publishedVersion |
| locations[1].raw_type | journal-article |
| locations[1].license_id | |
| locations[1].is_accepted | True |
| locations[1].is_published | True |
| locations[1].raw_source_name | INFORMS Journal on Computing |
| locations[1].landing_page_url | https://scholars.cityu.edu.hk/en/publications/scheduling-with-calibrations-for-multi-interval-jobs |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5023216979 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-3362-2063 |
| authorships[0].author.display_name | Vincent Chau |
| authorships[0].countries | CN |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I76569877 |
| authorships[0].affiliations[0].raw_affiliation_string | School of Computer Science and Engineering, Southeast University, Nanjing 211189, China |
| authorships[0].institutions[0].id | https://openalex.org/I76569877 |
| authorships[0].institutions[0].ror | https://ror.org/04ct4d772 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I76569877 |
| authorships[0].institutions[0].country_code | CN |
| authorships[0].institutions[0].display_name | Southeast University |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Vincent Chau |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | School of Computer Science and Engineering, Southeast University, Nanjing 211189, China |
| authorships[1].author.id | https://openalex.org/A5073258279 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Christoph Damerius |
| authorships[1].countries | DE |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I159176309 |
| authorships[1].affiliations[0].raw_affiliation_string | Department of Informatics, Universität Hamburg, 22527 Hamburg, Germany |
| authorships[1].institutions[0].id | https://openalex.org/I159176309 |
| authorships[1].institutions[0].ror | https://ror.org/00g30e956 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I159176309 |
| authorships[1].institutions[0].country_code | DE |
| authorships[1].institutions[0].display_name | Universität Hamburg |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Christoph Damerius |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Department of Informatics, Universität Hamburg, 22527 Hamburg, Germany |
| authorships[2].author.id | https://openalex.org/A5007675663 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-0000-8689 |
| authorships[2].author.display_name | Peter Kling |
| authorships[2].countries | DE |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I159176309 |
| authorships[2].affiliations[0].raw_affiliation_string | Department of Informatics, Universität Hamburg, 22527 Hamburg, Germany |
| authorships[2].institutions[0].id | https://openalex.org/I159176309 |
| authorships[2].institutions[0].ror | https://ror.org/00g30e956 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I159176309 |
| authorships[2].institutions[0].country_code | DE |
| authorships[2].institutions[0].display_name | Universität Hamburg |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Peter Kling |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | Department of Informatics, Universität Hamburg, 22527 Hamburg, Germany |
| authorships[3].author.id | https://openalex.org/A5085884127 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-7370-6237 |
| authorships[3].author.display_name | Minming Li |
| authorships[3].countries | HK |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I168719708 |
| authorships[3].affiliations[0].raw_affiliation_string | Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong |
| authorships[3].institutions[0].id | https://openalex.org/I168719708 |
| authorships[3].institutions[0].ror | https://ror.org/03q8dnn23 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I168719708 |
| authorships[3].institutions[0].country_code | HK |
| authorships[3].institutions[0].display_name | City University of Hong Kong |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Minming Li |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong |
| authorships[4].author.id | https://openalex.org/A5070253689 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-7052-8404 |
| authorships[4].author.display_name | Florian Schneider |
| authorships[4].countries | DE |
| authorships[4].affiliations[0].institution_ids | https://openalex.org/I159176309 |
| authorships[4].affiliations[0].raw_affiliation_string | Department of Informatics, Universität Hamburg, 22527 Hamburg, Germany |
| authorships[4].institutions[0].id | https://openalex.org/I159176309 |
| authorships[4].institutions[0].ror | https://ror.org/00g30e956 |
| authorships[4].institutions[0].type | education |
| authorships[4].institutions[0].lineage | https://openalex.org/I159176309 |
| authorships[4].institutions[0].country_code | DE |
| authorships[4].institutions[0].display_name | Universität Hamburg |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Florian Schneider |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | Department of Informatics, Universität Hamburg, 22527 Hamburg, Germany |
| authorships[5].author.id | https://openalex.org/A5014987921 |
| authorships[5].author.orcid | https://orcid.org/0000-0002-4859-2661 |
| authorships[5].author.display_name | Ruilong Zhang |
| authorships[5].countries | HK |
| authorships[5].affiliations[0].institution_ids | https://openalex.org/I168719708 |
| authorships[5].affiliations[0].raw_affiliation_string | Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong |
| authorships[5].institutions[0].id | https://openalex.org/I168719708 |
| authorships[5].institutions[0].ror | https://ror.org/03q8dnn23 |
| authorships[5].institutions[0].type | education |
| authorships[5].institutions[0].lineage | https://openalex.org/I168719708 |
| authorships[5].institutions[0].country_code | HK |
| authorships[5].institutions[0].display_name | City University of Hong Kong |
| authorships[5].author_position | last |
| authorships[5].raw_author_name | Ruilong Zhang |
| authorships[5].is_corresponding | False |
| authorships[5].raw_affiliation_strings | Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://scholars.cityu.edu.hk/en/publications/scheduling-with-calibrations-for-multi-interval-jobs |
| open_access.oa_status | bronze |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Scheduling with Calibrations for Multi-Interval Jobs |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T10551 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9998000264167786 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2209 |
| primary_topic.subfield.display_name | Industrial and Manufacturing Engineering |
| primary_topic.display_name | Scheduling and Optimization Algorithms |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W2390279801, https://openalex.org/W4391913857, https://openalex.org/W2358668433, https://openalex.org/W4396701345, https://openalex.org/W2376932109, https://openalex.org/W2025955409, https://openalex.org/W1577301438 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S165318533 |
| best_oa_location.source.issn | 1091-9856, 1526-5528 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | 1091-9856 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | INFORMS journal on computing |
| best_oa_location.source.host_organization | https://openalex.org/P4310315699 |
| best_oa_location.source.host_organization_name | Institute for Operations Research and the Management Sciences |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310315699 |
| best_oa_location.source.host_organization_lineage_names | Institute for Operations Research and the Management Sciences |
| best_oa_location.license | |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | INFORMS Journal on Computing |
| best_oa_location.landing_page_url | https://scholars.cityu.edu.hk/en/publications/scheduling-with-calibrations-for-multi-interval-jobs |
| primary_location.id | doi:10.1287/ijoc.2023.0430 |
| primary_location.is_oa | False |
| primary_location.source.id | https://openalex.org/S165318533 |
| primary_location.source.issn | 1091-9856, 1526-5528 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | 1091-9856 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | INFORMS journal on computing |
| primary_location.source.host_organization | https://openalex.org/P4310315699 |
| primary_location.source.host_organization_name | Institute for Operations Research and the Management Sciences |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310315699 |
| primary_location.source.host_organization_lineage_names | Institute for Operations Research and the Management Sciences |
| primary_location.license | |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | INFORMS Journal on Computing |
| primary_location.landing_page_url | https://doi.org/10.1287/ijoc.2023.0430 |
| publication_date | 2025-04-03 |
| publication_year | 2025 |
| referenced_works | https://openalex.org/W3167631951, https://openalex.org/W2006064572, https://openalex.org/W2963676906, https://openalex.org/W3184938801, https://openalex.org/W2112112676, https://openalex.org/W2964745183, https://openalex.org/W3128375896, https://openalex.org/W4386141354, https://openalex.org/W1680189815, https://openalex.org/W1966876326, https://openalex.org/W2112230387, https://openalex.org/W1967354512, https://openalex.org/W3014711981, https://openalex.org/W2029828838, https://openalex.org/W2167667767, https://openalex.org/W1977545325 |
| referenced_works_count | 16 |
| abstract_inverted_index.. | 405 |
| abstract_inverted_index.2 | 343 |
| abstract_inverted_index.= | 199, 342 |
| abstract_inverted_index.B | 165 |
| abstract_inverted_index.P | 198 |
| abstract_inverted_index.T | 47, 341 |
| abstract_inverted_index.Y | 276 |
| abstract_inverted_index.a | 3, 28, 43, 95, 108, 173, 194 |
| abstract_inverted_index.m | 364 |
| abstract_inverted_index.n | 16 |
| abstract_inverted_index.B, | 76 |
| abstract_inverted_index.CA | 66 |
| abstract_inverted_index.G, | 274 |
| abstract_inverted_index.In | 129, 146 |
| abstract_inverted_index.Li | 269 |
| abstract_inverted_index.M, | 270 |
| abstract_inverted_index.S, | 64, 268 |
| abstract_inverted_index.V, | 266 |
| abstract_inverted_index.We | 106, 125, 177 |
| abstract_inverted_index.Y, | 272 |
| abstract_inverted_index.Z, | 284 |
| abstract_inverted_index.an | 243, 260 |
| abstract_inverted_index.at | 163, 211, 403 |
| abstract_inverted_index.be | 25, 104, 115, 208, 219, 360 |
| abstract_inverted_index.by | 53, 368, 385 |
| abstract_inverted_index.et | 55 |
| abstract_inverted_index.in | 110, 210, 301, 344, 380 |
| abstract_inverted_index.is | 135, 152, 183, 190, 216, 225, 321, 401 |
| abstract_inverted_index.it | 102 |
| abstract_inverted_index.no | 226 |
| abstract_inverted_index.of | 20, 119, 140, 158, 263 |
| abstract_inverted_index.on | 27, 232, 317 |
| abstract_inverted_index.to | 70, 136, 153, 193, 218 |
| abstract_inverted_index.up | 192 |
| abstract_inverted_index.we | 171, 241, 311, 335, 354 |
| abstract_inverted_index.1/3 | 264 |
| abstract_inverted_index.ACM | 79 |
| abstract_inverted_index.DP, | 60 |
| abstract_inverted_index.For | 167, 237 |
| abstract_inverted_index.GE, | 74 |
| abstract_inverted_index.JR, | 286 |
| abstract_inverted_index.MA, | 58 |
| abstract_inverted_index.MR, | 288 |
| abstract_inverted_index.NP. | 200 |
| abstract_inverted_index.New | 87, 307 |
| abstract_inverted_index.The | 33, 50, 201, 398 |
| abstract_inverted_index.VJ, | 62 |
| abstract_inverted_index.al. | 56 |
| abstract_inverted_index.all | 144, 324, 374 |
| abstract_inverted_index.and | 41, 98, 349 |
| abstract_inverted_index.any | 331 |
| abstract_inverted_index.are | 15 |
| abstract_inverted_index.can | 35, 359 |
| abstract_inverted_index.for | 9, 46, 330, 340, 390 |
| abstract_inverted_index.has | 94, 259 |
| abstract_inverted_index.job | 93, 113, 206 |
| abstract_inverted_index.may | 207 |
| abstract_inverted_index.one | 118 |
| abstract_inverted_index.our | 133, 150, 188, 315, 357 |
| abstract_inverted_index.see | 228, 249, 333 |
| abstract_inverted_index.the | 130, 138, 147, 155, 168, 181, 233, 238, 254, 318, 346, 350, 363, 378 |
| abstract_inverted_index.two | 127, 213 |
| abstract_inverted_index.16th | 293 |
| abstract_inverted_index.2019 | 297 |
| abstract_inverted_index.25th | 78 |
| abstract_inverted_index.Area | 388 |
| abstract_inverted_index.Data | 291 |
| abstract_inverted_index.Feng | 267 |
| abstract_inverted_index.More | 12 |
| abstract_inverted_index.SPAA | 84 |
| abstract_inverted_index.Sack | 285 |
| abstract_inverted_index.This | 0, 251 |
| abstract_inverted_index.WADS | 296 |
| abstract_inverted_index.Wang | 271 |
| abstract_inverted_index.also | 178, 312 |
| abstract_inverted_index.both | 345, 381 |
| abstract_inverted_index.case | 203, 367 |
| abstract_inverted_index.each | 92, 112, 205 |
| abstract_inverted_index.eds. | 77, 289 |
| abstract_inverted_index.game | 235 |
| abstract_inverted_index.give | 242 |
| abstract_inverted_index.goal | 134, 151 |
| abstract_inverted_index.hold | 329 |
| abstract_inverted_index.into | 362 |
| abstract_inverted_index.jobs | 19, 37, 160 |
| abstract_inverted_index.many | 121 |
| abstract_inverted_index.most | 164, 212 |
| abstract_inverted_index.must | 24, 103, 114 |
| abstract_inverted_index.only | 38 |
| abstract_inverted_index.same | 379 |
| abstract_inverted_index.show | 355 |
| abstract_inverted_index.size | 22 |
| abstract_inverted_index.some | 370 |
| abstract_inverted_index.such | 42 |
| abstract_inverted_index.that | 23, 91, 180, 187, 223, 314, 356 |
| abstract_inverted_index.time | 48, 97, 123, 214 |
| abstract_inverted_index.unit | 21 |
| abstract_inverted_index.upon | 253 |
| abstract_inverted_index.vol. | 304 |
| abstract_inverted_index.when | 39, 204 |
| abstract_inverted_index.with | 6, 245, 281 |
| abstract_inverted_index.& | 393 |
| abstract_inverted_index.(ACM, | 86 |
| abstract_inverted_index.11646 | 305 |
| abstract_inverted_index.Bunde | 59 |
| abstract_inverted_index.Erwin | 386 |
| abstract_inverted_index.Leung | 61 |
| abstract_inverted_index.Notes | 300 |
| abstract_inverted_index.Zhang | 273, 275 |
| abstract_inverted_index.[Chau | 265 |
| abstract_inverted_index.above | 328 |
| abstract_inverted_index.based | 231 |
| abstract_inverted_index.bound | 316 |
| abstract_inverted_index.hard, | 185, 221 |
| abstract_inverted_index.jobs. | 11, 145 |
| abstract_inverted_index.lasts | 45 |
| abstract_inverted_index.model | 52 |
| abstract_inverted_index.paper | 1 |
| abstract_inverted_index.prove | 179, 313 |
| abstract_inverted_index.ratio | 247, 262, 320 |
| abstract_inverted_index.shown | 217 |
| abstract_inverted_index.slots | 215 |
| abstract_inverted_index.study | 107 |
| abstract_inverted_index.there | 14, 224 |
| abstract_inverted_index.time, | 372 |
| abstract_inverted_index.total | 156 |
| abstract_inverted_index.using | 162 |
| abstract_inverted_index.which | 101, 111, 258 |
| abstract_inverted_index.while | 142, 161 |
| abstract_inverted_index.‘13 | 85 |
| abstract_inverted_index.(2013) | 67 |
| abstract_inverted_index.(2019) | 277 |
| abstract_inverted_index.Bender | 54 |
| abstract_inverted_index.Editor | 389 |
| abstract_inverted_index.Pesch, | 387 |
| abstract_inverted_index.Proc., | 298 |
| abstract_inverted_index.Search | 392 |
| abstract_inverted_index.York), | 88, 308 |
| abstract_inverted_index.during | 117 |
| abstract_inverted_index.factor | 196 |
| abstract_inverted_index.losing | 369 |
| abstract_inverted_index.number | 139 |
| abstract_inverted_index.online | 399 |
| abstract_inverted_index.remain | 377 |
| abstract_inverted_index.single | 29 |
| abstract_inverted_index.slots. | 49 |
| abstract_inverted_index.text], | 334 |
| abstract_inverted_index.text]. | 250 |
| abstract_inverted_index.tight. | 322 |
| abstract_inverted_index.unique | 234 |
| abstract_inverted_index.unless | 197 |
| abstract_inverted_index.weight | 157 |
| abstract_inverted_index.Lecture | 299 |
| abstract_inverted_index.Sympos. | 80, 295 |
| abstract_inverted_index.[Bender | 57 |
| abstract_inverted_index.assumes | 90 |
| abstract_inverted_index.between | 100 |
| abstract_inverted_index.machine | 7, 34 |
| abstract_inverted_index.methods | 358 |
| abstract_inverted_index.optimal | 191, 337 |
| abstract_inverted_index.present | 172 |
| abstract_inverted_index.problem | 5, 182 |
| abstract_inverted_index.process | 36 |
| abstract_inverted_index.provide | 336 |
| abstract_inverted_index.release | 96 |
| abstract_inverted_index.results | 326, 376 |
| abstract_inverted_index.running | 371 |
| abstract_inverted_index.special | 202 |
| abstract_inverted_index.studies | 2 |
| abstract_inverted_index.version | 348 |
| abstract_inverted_index.whereas | 373 |
| abstract_inverted_index.Accepted | 384 |
| abstract_inverted_index.Although | 323 |
| abstract_inverted_index.Blelloch | 73 |
| abstract_inverted_index.Computer | 302 |
| abstract_inverted_index.Finally, | 353 |
| abstract_inverted_index.History: | 383 |
| abstract_inverted_index.McCauley | 63 |
| abstract_inverted_index.Phillips | 65 |
| abstract_inverted_index.Science, | 303 |
| abstract_inverted_index.Vöcking | 75 |
| abstract_inverted_index.Weighted | 278 |
| abstract_inverted_index.appendix | 400 |
| abstract_inverted_index.consider | 126 |
| abstract_inverted_index.constant | 195 |
| abstract_inverted_index.deadline | 99 |
| abstract_inverted_index.exactly, | 13 |
| abstract_inverted_index.extended | 361 |
| abstract_inverted_index.hardness | 325 |
| abstract_inverted_index.implying | 186, 222 |
| abstract_inverted_index.improves | 252 |
| abstract_inverted_index.machine. | 32 |
| abstract_inverted_index.machines | 366 |
| abstract_inverted_index.maximize | 154 |
| abstract_inverted_index.minimize | 71, 137 |
| abstract_inverted_index.possibly | 120 |
| abstract_inverted_index.standard | 51 |
| abstract_inverted_index.version, | 132, 149, 170, 240 |
| abstract_inverted_index.version. | 352 |
| abstract_inverted_index.(possibly | 17 |
| abstract_inverted_index.Efficient | 68 |
| abstract_inverted_index.Friggstad | 283 |
| abstract_inverted_index.Heuristic | 391 |
| abstract_inverted_index.Internat. | 294 |
| abstract_inverted_index.Material: | 397 |
| abstract_inverted_index.Moreover, | 310 |
| abstract_inverted_index.[Formula: | 227, 248, 332 |
| abstract_inverted_index.algorithm | 189, 230, 244 |
| abstract_inverted_index.available | 402 |
| abstract_inverted_index.identical | 365 |
| abstract_inverted_index.initially | 30 |
| abstract_inverted_index.mentioned | 327 |
| abstract_inverted_index.processed | 116 |
| abstract_inverted_index.scheduled | 26, 159, 209 |
| abstract_inverted_index.set-cover | 184 |
| abstract_inverted_index.versions. | 382 |
| abstract_inverted_index.weighted) | 18 |
| abstract_inverted_index.(Springer, | 306 |
| abstract_inverted_index.280–287] | 89 |
| abstract_inverted_index.Algorithms | 82, 290 |
| abstract_inverted_index.Structures | 292 |
| abstract_inverted_index.algorithm, | 257 |
| abstract_inverted_index.algorithm. | 176 |
| abstract_inverted_index.algorithms | 339 |
| abstract_inverted_index.best-known | 256 |
| abstract_inverted_index.intervals. | 124 |
| abstract_inverted_index.previously | 255 |
| abstract_inverted_index.processed. | 105 |
| abstract_inverted_index.scheduling | 4, 69, 143 |
| abstract_inverted_index.throughput | 279 |
| abstract_inverted_index.311–324]. | 309 |
| abstract_inverted_index.Algorithms. | 395 |
| abstract_inverted_index.Parallelism | 81 |
| abstract_inverted_index.algorithmic | 375 |
| abstract_inverted_index.calibrated, | 40 |
| abstract_inverted_index.calibration | 44 |
| abstract_inverted_index.conjecture. | 236 |
| abstract_inverted_index.logarithmic | 174 |
| abstract_inverted_index.objectives: | 128 |
| abstract_inverted_index.Salavatipour | 287 |
| abstract_inverted_index.Supplemental | 396 |
| abstract_inverted_index.calibrations | 8, 141 |
| abstract_inverted_index.maximization | 148, 239, 280, 351 |
| abstract_inverted_index.minimization | 131, 169, 347 |
| abstract_inverted_index.uncalibrated | 31 |
| abstract_inverted_index.vertex-cover | 220 |
| abstract_inverted_index.Approximation | 394 |
| abstract_inverted_index.Architectures | 83 |
| abstract_inverted_index.approximation | 175, 246, 261, 319 |
| abstract_inverted_index.calibrations. | 72, 166, 282 |
| abstract_inverted_index.job-dependent | 122 |
| abstract_inverted_index.generalization | 109 |
| abstract_inverted_index.multi-interval | 10 |
| abstract_inverted_index.polynomial-time | 338 |
| abstract_inverted_index.text]-approximation | 229 |
| abstract_inverted_index.https://doi.org/10.1287/ijoc.2023.0430 | 404 |
| cited_by_percentile_year | |
| countries_distinct_count | 3 |
| institutions_distinct_count | 6 |
| citation_normalized_percentile.value | 0.1336704 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |