Publication Information

{'id': 'https://openalex.org/W3035713054', 'doi': 'https://doi.org/10.1145/3381451', 'title': 'Approximating Spanners and Directed Steiner Forest', 'display_name': 'Approximating Spanners and Directed Steiner Forest', 'publication_year': 2020, 'publication_date': '2020-06-12', 'ids': {'openalex': 'https://openalex.org/W3035713054', 'doi': 'https://doi.org/10.1145/3381451', 'mag': '3035713054'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/3381451', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S137348503', 'display_name': 'ACM Transactions on Algorithms', 'issn_l': '1549-6325', 'issn': ['1549-6325', '1549-6333'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319798', 'host_organization_name': 'Association for Computing Machinery', 'host_organization_lineage': ['https://openalex.org/P4310319798'], 'host_organization_lineage_names': ['Association for Computing Machinery'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'journal-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5043851880', 'display_name': 'Eden Chlamtáč', 'orcid': 'https://orcid.org/0000-0002-0296-0107'}, 'institutions': [{'id': 'https://openalex.org/I124227911', 'display_name': 'Ben-Gurion University of the Negev', 'ror': 'https://ror.org/05tkyf982', 'country_code': 'IL', 'type': 'education', 'lineage': ['https://openalex.org/I124227911']}], 'countries': ['IL'], 'is_corresponding': False, 'raw_author_name': 'Eden Chlamtáč', 'raw_affiliation_strings': ['Ben Gurion University, Be’er-Sheva, Israel'], 'affiliations': [{'raw_affiliation_string': 'Ben Gurion University, Be’er-Sheva, Israel', 'institution_ids': ['https://openalex.org/I124227911']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5049161363', 'display_name': 'Michael Dinitz', 'orcid': 'https://orcid.org/0000-0002-2632-966X'}, 'institutions': [{'id': 'https://openalex.org/I145311948', 'display_name': 'Johns Hopkins University', 'ror': 'https://ror.org/00za53h95', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I145311948']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Michael Dinitz', 'raw_affiliation_strings': ['Johns Hopkins University, USA'], 'affiliations': [{'raw_affiliation_string': 'Johns Hopkins University, USA', 'institution_ids': ['https://openalex.org/I145311948']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5056370891', 'display_name': 'Guy Kortsarz', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I102322142', 'display_name': 'Rutgers, The State University of New Jersey', 'ror': 'https://ror.org/05vt9qd57', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I102322142']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Guy Kortsarz', 'raw_affiliation_strings': ['Rutgers University-Camden, USA'], 'affiliations': [{'raw_affiliation_string': 'Rutgers University-Camden, USA', 'institution_ids': ['https://openalex.org/I102322142']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5005632876', 'display_name': 'Bundit Laekhanukit', 'orcid': 'https://orcid.org/0000-0002-4476-8914'}, 'institutions': [{'id': 'https://openalex.org/I181679659', 'display_name': 'Shanghai University of Finance and Economics', 'ror': 'https://ror.org/00wtvfq62', 'country_code': 'CN', 'type': 'education', 'lineage': ['https://openalex.org/I181679659']}], 'countries': ['CN'], 'is_corresponding': False, 'raw_author_name': 'Bundit Laekhanukit', 'raw_affiliation_strings': ['Shanghai University of Finance 8 Economics, China'], 'affiliations': [{'raw_affiliation_string': 'Shanghai University of Finance 8 Economics, China', 'institution_ids': ['https://openalex.org/I181679659']}]}], 'institution_assertions': [], 'countries_distinct_count': 3, 'institutions_distinct_count': 4, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 0.228, 'has_fulltext': False, 'cited_by_count': 2, 'citation_normalized_percentile': {'value': 0.549694, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 69, 'max': 73}, 'biblio': {'volume': '16', 'issue': '3', 'first_page': '1', 'last_page': '31'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9999, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9999, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10374', 'display_name': 'Advanced Graph Theory Research', 'score': 0.9973, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9945, 'subfield': {'id': 'https://openalex.org/subfields/1705', 'display_name': 'Computer Networks and Communications'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/spanner', 'display_name': 'Spanner', 'score': 0.9288792}, {'id': 'https://openalex.org/keywords/hardness-of-approximation', 'display_name': 'Hardness of approximation', 'score': 0.6379487}, {'id': 'https://openalex.org/keywords/constant', 'display_name': 'Constant (computer programming)', 'score': 0.5606457}, {'id': 'https://openalex.org/keywords/steiner-tree-problem', 'display_name': 'Steiner tree problem', 'score': 0.5496229}], 'concepts': [{'id': 'https://openalex.org/C2779585601', 'wikidata': 'https://www.wikidata.org/wiki/Q4049850', 'display_name': 'Spanner', 'level': 2, 'score': 0.9288792}, {'id': 'https://openalex.org/C42747912', 'wikidata': 'https://www.wikidata.org/wiki/Q1048447', 'display_name': 'Multiplicative function', 'level': 2, 'score': 0.8683739}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.77606803}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.71396244}, {'id': 'https://openalex.org/C148764684', 'wikidata': 'https://www.wikidata.org/wiki/Q621751', 'display_name': 'Approximation algorithm', 'level': 2, 'score': 0.68081003}, {'id': 'https://openalex.org/C112955886', 'wikidata': 'https://www.wikidata.org/wiki/Q5656275', 'display_name': 'Hardness of approximation', 'level': 3, 'score': 0.6379487}, {'id': 'https://openalex.org/C2780428219', 'wikidata': 'https://www.wikidata.org/wiki/Q16952335', 'display_name': 'Cover (algebra)', 'level': 2, 'score': 0.59295505}, {'id': 'https://openalex.org/C2777027219', 'wikidata': 'https://www.wikidata.org/wiki/Q1284190', 'display_name': 'Constant (computer programming)', 'level': 2, 'score': 0.5606457}, {'id': 'https://openalex.org/C76220878', 'wikidata': 'https://www.wikidata.org/wiki/Q1764144', 'display_name': 'Steiner tree problem', 'level': 2, 'score': 0.5496229}, {'id': 'https://openalex.org/C184898388', 'wikidata': 'https://www.wikidata.org/wiki/Q1435712', 'display_name': 'Pairwise comparison', 'level': 2, 'score': 0.50280285}, {'id': 'https://openalex.org/C77553402', 'wikidata': 'https://www.wikidata.org/wiki/Q13222579', 'display_name': 'Upper and lower bounds', 'level': 2, 'score': 0.47675595}, {'id': 'https://openalex.org/C63553672', 'wikidata': 'https://www.wikidata.org/wiki/Q581168', 'display_name': 'Binary logarithm', 'level': 2, 'score': 0.4376017}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.4104482}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.15023056}, {'id': 'https://openalex.org/C105795698', 'wikidata': 'https://www.wikidata.org/wiki/Q12483', 'display_name': 'Statistics', 'level': 1, 'score': 0.07448292}, {'id': 'https://openalex.org/C78519656', 'wikidata': 'https://www.wikidata.org/wiki/Q101333', 'display_name': 'Mechanical engineering', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C134306372', 'wikidata': 'https://www.wikidata.org/wiki/Q7754', 'display_name': 'Mathematical analysis', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C120314980', 'wikidata': 'https://www.wikidata.org/wiki/Q180634', 'display_name': 'Distributed computing', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C127413603', 'wikidata': 'https://www.wikidata.org/wiki/Q11023', 'display_name': 'Engineering', 'level': 0, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/3381451', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S137348503', 'display_name': 'ACM Transactions on Algorithms', 'issn_l': '1549-6325', 'issn': ['1549-6325', '1549-6333'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319798', 'host_organization_name': 'Association for Computing Machinery', 'host_organization_lineage': ['https://openalex.org/P4310319798'], 'host_organization_lineage_names': ['Association for Computing Machinery'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [{'display_name': 'Life on land', 'score': 0.68, 'id': 'https://metadata.un.org/sdg/15'}], 'grants': [{'funder': 'https://openalex.org/F4320309856', 'funder_display_name': 'National Youth Science Foundation', 'award_id': '1464239, 1535887, 1218620, 1540547, 1910565'}, {'funder': 'https://openalex.org/F4320320950', 'funder_display_name': 'United States-Israel Binational Science Foundation', 'award_id': '1002/14,621/12'}, {'funder': 'https://openalex.org/F4320335016', 'funder_display_name': 'Israeli Centers for Research Excellence', 'award_id': '4/11'}], 'datasets': [], 'versions': [], 'referenced_works_count': 28, 'referenced_works': ['https://openalex.org/W1906469382', 'https://openalex.org/W1965909513', 'https://openalex.org/W1972920042', 'https://openalex.org/W1986144992', 'https://openalex.org/W1986201860', 'https://openalex.org/W1988067232', 'https://openalex.org/W1997369416', 'https://openalex.org/W1998721609', 'https://openalex.org/W2002041206', 'https://openalex.org/W2005771129', 'https://openalex.org/W2017280430', 'https://openalex.org/W2031536548', 'https://openalex.org/W2049184889', 'https://openalex.org/W2057046770', 'https://openalex.org/W2060054375', 'https://openalex.org/W2080551019', 'https://openalex.org/W2146522997', 'https://openalex.org/W2221370457', 'https://openalex.org/W2486585506', 'https://openalex.org/W2508647357', 'https://openalex.org/W2568296800', 'https://openalex.org/W2620939520', 'https://openalex.org/W2750647157', 'https://openalex.org/W2963583531', 'https://openalex.org/W2963915537', 'https://openalex.org/W2997658321', 'https://openalex.org/W345196136', 'https://openalex.org/W4240054244'], 'related_works': ['https://openalex.org/W3184075718', 'https://openalex.org/W2995411114', 'https://openalex.org/W2962992394', 'https://openalex.org/W2890780287', 'https://openalex.org/W2367195720', 'https://openalex.org/W2242006561', 'https://openalex.org/W2009976792', 'https://openalex.org/W1998126097', 'https://openalex.org/W1980288485', 'https://openalex.org/W1968497507'], 'abstract_inverted_index': {'It': [0], 'was': [1], 'recently': [2], 'found': [3], 'that': [4], 'there': [5], 'are': [6, 20, 84, 89, 132], 'very': [7], 'close': [8], 'connections': [9], 'between': [10], 'the': [11, 78, 93, 121, 155, 169, 185, 195, 230, 248], 'existence': [12, 79], 'of': [13, 72, 80, 130, 157], 'additive': [14, 25, 56, 151, 158, 181], 'spanners': [15, 41, 112], '(subgraphs': [16, 29, 42], 'where': [17, 74], 'all': [18, 242], 'distances': [19], 'preserved': [21, 37, 50], 'up': [22, 51], 'to': [23, 52, 91, 134, 138, 207, 219, 259], 'an': [24, 69, 86, 99, 175, 191, 221], 'stretch),': [26], 'distance': [27, 36, 49, 108], 'preservers': [28, 109], 'in': [30, 43, 199], 'which': [31, 44, 131], 'demand': [32, 45], 'pairs': [33, 46], 'have': [34, 47, 244], 'their': [35, 48], 'exactly),': [38], 'and': [39, 88, 110, 180], 'pairwise': [40, 111], 'a': [53, 165], 'multiplicative': [54, 171, 187], 'or': [55], 'stretch)': [57], '[Abboud-Bodwin': [58], 'SODA’16': [59], '8': [60], 'J.ACM’17,': [61], 'Bodwin-Williams': [62], 'SODA’16].': [63], 'We': [64, 97, 143], 'study': [65], 'these': [66], 'problems': [67], 'from': [68], 'optimization': [70], 'point': [71], 'view,': [73], 'rather': [75], 'than': [76], 'studying': [77], 'extremal': [81], 'instances,': [82], 'we': [83, 197], 'given': [85], 'instance': [87], 'asked': [90], 'find': [92], 'sparsest': [94], 'possible': [95], 'spanner/preserver.': [96], 'give': [98, 220], 'O': [100, 176, 192, 222, 251], '(': [101, 223, 252], 'n': [102, 178, 224, 253], '3/5': [103, 225], '+': [104, 226, 255], 'ε': [105, 116, 227, 238, 256], ')-approximation': [106, 228, 257], 'for': [107, 126, 149, 154, 229, 266], '(for': [113, 235], 'arbitrary': [114, 236], 'constant': [115, 237], '>': [117, 239], '0).': [118], 'This': [119], 'is': [120], 'first': [122], 'nontrivial': [123], 'upper': [124], 'bound': [125], 'either': [127], 'problem,': [128], 'both': [129], 'known': [133], 'be': [135], 'as': [136, 140], 'hard': [137], 'approximate': [139], 'Label': [141, 146], 'Cover.': [142], 'also': [144], 'prove': [145], 'Cover': [147], 'hardness': [148], 'approximating': [150], 'spanners,': [152], 'even': [153], 'cases': [156], '1': [159], 'stretch': [160, 183], '(where': [161, 184], 'one': [162], 'might': [163], 'expect': [164], 'polylogarithmic': [166, 182], 'approximation,': [167], 'since': [168], 'related': [170, 186], '2-spanner': [172], 'problem': [173, 189, 206, 234], 'admits': [174], '(log': [177], ')-approximation)': [179], 'spanner': [188], 'has': [190], '(1)-approximation).': [193], 'Interestingly,': [194], 'techniques': [196, 216], 'use': [198], 'our': [200, 215], 'approximation': [201], 'algorithm': [202], 'extend': [203], 'beyond': [204], 'distance-based': [205], 'pure': [208], 'connectivity': [209], 'network': [210], 'design': [211], 'problems.': [212], 'In': [213], 'particular,': [214], 'allow': [217], 'us': [218], 'Directed': [231], 'Steiner': [232], 'Forest': [233], '0)': [240], 'when': [241], 'edges': [243], 'uniform': [245], 'costs,': [246], 'improving': [247], 'previous': [249], 'best': [250], '2/3': [254], 'due': [258], 'Berman': [260], 'et': [261], 'al.': [262], '[ICALP’11]': [263], '(which': [264], 'holds': [265], 'general': [267], 'edge': [268], 'costs).': [269]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W3035713054', 'counts_by_year': [{'year': 2023, 'cited_by_count': 1}, {'year': 2021, 'cited_by_count': 1}], 'updated_date': '2024-12-31T14:51:08.453250', 'created_date': '2020-06-19'}