A constant-factor approximation algorithm for the <i>k</i> MST problem (extended abstract)

Name: Work Video:
Duration: 3 min 30 s
Avrim Blum; R. Ravi; Santosh Vempala
{'id': 'https://openalex.org/W2088761355', 'doi': 'https://doi.org/10.1145/237814.237992', 'title': 'A constant-factor approximation algorithm for the <i>k</i> MST problem (extended abstract)', 'display_name': 'A constant-factor approximation algorithm for the <i>k</i> MST problem (extended abstract)', 'publication_year': 1996, 'publication_date': '1996-01-01', 'ids': {'openalex': 'https://openalex.org/W2088761355', 'doi': 'https://doi.org/10.1145/237814.237992', 'mag': '2088761355'}, 'language': 'en', 'primary_location': {'is_oa': True, 'landing_page_url': 'https://doi.org/10.1145/237814.237992', 'pdf_url': 'https://dl.acm.org/doi/pdf/10.1145/237814.237992', 'source': None, 'license': None, 'license_id': None, 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, 'type': 'article', 'type_crossref': 'proceedings-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': True, 'oa_status': 'bronze', 'oa_url': 'https://dl.acm.org/doi/pdf/10.1145/237814.237992', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5024803432', 'display_name': 'Avrim Blum', 'orcid': 'https://orcid.org/0000-0003-2450-5102'}, 'institutions': [{'id': 'https://openalex.org/I74973139', 'display_name': 'Carnegie Mellon University', 'ror': 'https://ror.org/05x2bcf33', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I74973139']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Avrim Blum', 'raw_affiliation_strings': ['School of Computer Science, Carnegie Mellon University, Pittsburgh, PA'], 'affiliations': [{'raw_affiliation_string': 'School of Computer Science, Carnegie Mellon University, Pittsburgh, PA', 'institution_ids': ['https://openalex.org/I74973139']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5087844619', 'display_name': 'R. Ravi', 'orcid': 'https://orcid.org/0000-0001-7603-1207'}, 'institutions': [{'id': 'https://openalex.org/I74973139', 'display_name': 'Carnegie Mellon University', 'ror': 'https://ror.org/05x2bcf33', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I74973139']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'R. Ravi', 'raw_affiliation_strings': ['Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh PA'], 'affiliations': [{'raw_affiliation_string': 'Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh PA', 'institution_ids': ['https://openalex.org/I74973139']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5101983359', 'display_name': 'Santosh Vempala', 'orcid': 'https://orcid.org/0000-0002-3779-433X'}, 'institutions': [{'id': 'https://openalex.org/I74973139', 'display_name': 'Carnegie Mellon University', 'ror': 'https://ror.org/05x2bcf33', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I74973139']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Santosh Vempala', 'raw_affiliation_strings': ['School of Computer Science, Carnegie Mellon University, Pittsburgh, PA'], 'affiliations': [{'raw_affiliation_string': 'School of Computer Science, Carnegie Mellon University, Pittsburgh, PA', 'institution_ids': ['https://openalex.org/I74973139']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 1.206, 'has_fulltext': True, 'fulltext_origin': 'pdf', 'cited_by_count': 40, 'citation_normalized_percentile': {'value': 0.924848, 'is_in_top_1_percent': False, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 90, 'max': 91}, 'biblio': {'volume': None, 'issue': None, 'first_page': None, 'last_page': None}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9992, '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'}}, 'topics': [{'id': 'https://openalex.org/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9992, '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'}}, {'id': 'https://openalex.org/T12176', 'display_name': 'Optimization and Packing Problems', 'score': 0.9991, 'subfield': {'id': 'https://openalex.org/subfields/2209', 'display_name': 'Industrial and Manufacturing Engineering'}, 'field': {'id': 'https://openalex.org/fields/22', 'display_name': 'Engineering'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.998, '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'}}], 'keywords': [{'id': 'https://openalex.org/keywords/constant', 'display_name': 'Constant (computer programming)', 'score': 0.47802958}], 'concepts': [{'id': 'https://openalex.org/C2778805511', 'wikidata': 'https://www.wikidata.org/wiki/Q1713', 'display_name': 'Citation', 'level': 2, 'score': 0.68024254}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.60885394}, {'id': 'https://openalex.org/C2777027219', 'wikidata': 'https://www.wikidata.org/wiki/Q1284190', 'display_name': 'Constant (computer programming)', 'level': 2, 'score': 0.47802958}, {'id': 'https://openalex.org/C161191863', 'wikidata': 'https://www.wikidata.org/wiki/Q199655', 'display_name': 'Library science', 'level': 1, 'score': 0.3688363}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.3596887}, {'id': 'https://openalex.org/C154945302', 'wikidata': 'https://www.wikidata.org/wiki/Q11660', 'display_name': 'Artificial intelligence', 'level': 1, 'score': 0.3250088}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.13894463}], 'mesh': [], 'locations_count': 2, 'locations': [{'is_oa': True, 'landing_page_url': 'https://doi.org/10.1145/237814.237992', 'pdf_url': 'https://dl.acm.org/doi/pdf/10.1145/237814.237992', 'source': None, 'license': None, 'license_id': None, 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, {'is_oa': True, 'landing_page_url': 'http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.9699', 'pdf_url': 'http://www.ams.sunysb.edu/~jsbm/papers/tspn09.pdf', 'source': {'id': 'https://openalex.org/S4306400349', 'display_name': 'CiteSeer X (The Pennsylvania State University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I130769515', 'host_organization_name': 'Pennsylvania State University', 'host_organization_lineage': ['https://openalex.org/I130769515'], 'host_organization_lineage_names': ['Pennsylvania State University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'https://doi.org/10.1145/237814.237992', 'pdf_url': 'https://dl.acm.org/doi/pdf/10.1145/237814.237992', 'source': None, 'license': None, 'license_id': None, 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, 'sustainable_development_goals': [{'id': 'https://metadata.un.org/sdg/9', 'display_name': 'Industry, innovation and infrastructure', 'score': 0.42}], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 11, 'referenced_works': ['https://openalex.org/W1966793805', 'https://openalex.org/W1986056047', 'https://openalex.org/W1992490235', 'https://openalex.org/W2001139415', 'https://openalex.org/W2003281104', 'https://openalex.org/W2024666707', 'https://openalex.org/W2032389500', 'https://openalex.org/W2043250424', 'https://openalex.org/W2044718761', 'https://openalex.org/W2088812877', 'https://openalex.org/W2949867427'], 'related_works': ['https://openalex.org/W4317642157', 'https://openalex.org/W4239542068', 'https://openalex.org/W2544423928', 'https://openalex.org/W2363440148', 'https://openalex.org/W2317510431', 'https://openalex.org/W2073681303', 'https://openalex.org/W2053286651', 'https://openalex.org/W2052122378', 'https://openalex.org/W2051487156', 'https://openalex.org/W134931362'], 'abstract_inverted_index': {'Article': [0], 'Free': [1], 'Access': [2], 'Share': [3], 'on': [4, 97, 148], 'A': [5], 'constant-factor': [6], 'approximation': [7], 'algorithm': [8], 'for': [9], 'the': [10, 92, 149], 'k': [11], 'MST': [12], 'problem': [13], '(extended': [14], 'abstract)': [15], 'Authors:': [16], 'Avrim': [17], 'Blum': [18], 'School': [19, 28, 42, 52, 65, 74], 'of': [20, 29, 43, 53, 66, 75, 91, 99], 'Computer': [21, 30, 67, 76], 'Science,': [22, 31, 68, 77], 'Carnegie': [23, 32, 46, 56, 69, 78], 'Mellon': [24, 33, 47, 57, 70, 79], 'University,': [25, 34, 48, 58, 71, 80], 'Pittsburgh,': [26, 35, 72, 81], 'PA': [27, 50, 73], 'PAView': [36, 60, 82], 'Profile': [37, 61, 83], ',': [38, 62], 'R.': [39], 'Ravi': [40], 'Graduate': [41, 51], 'Industrial': [44, 54], 'Administration,': [45, 55], 'Pittsburgh': [49, 59], 'Santosh': [63], 'Vempala': [64], 'Authors': [84], 'Info': [85], '&': [86], 'Claims': [87], 'STOC': [88], "'96:": [89], 'Proceedings': [90], 'twenty-eighth': [93], 'annual': [94], 'ACM': [95], 'symposium': [96], 'Theory': [98], 'ComputingJuly': [100], '1996': [101], 'Pages': [102], '442–448https://doi.org/10.1145/237814.237992Online:01': [103], 'July': [104], '1996Publication': [105], 'History': [106], '29citation579DownloadsMetricsTotal': [107], 'Citations29Total': [108], 'Downloads579Last': [109], '12': [110], 'Months25Last': [111], '6': [112], 'weeks1': [113], 'Get': [114], 'Citation': [115, 117, 154], 'AlertsNew': [116, 153], 'Alert': [118], 'added!This': [119], 'alert': [120, 145], 'has': [121, 140], 'been': [122, 141], 'successfully': [123], 'added': [124], 'and': [125], 'will': [126, 130], 'be': [127, 131], 'sent': [128], 'to:You': [129], 'notified': [132], 'whenever': [133], 'a': [134, 166], 'record': [135], 'that': [136], 'you': [137], 'have': [138], 'chosen': [139], 'cited.To': [142], 'manage': [143], 'your': [144, 159], 'preferences,': [146], 'click': [147], 'button': [150], 'below.Manage': [151], 'my': [152], 'Alert!Please': [155], 'log': [156], 'in': [157], 'to': [158, 162, 164], 'account': [160], 'Save': [161], 'BinderSave': [163], 'BinderCreate': [165], 'New': [167], 'BinderNameCancelCreateExport': [168], 'CitationPublisher': [169], 'SiteeReaderPDF': [170]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2088761355', 'counts_by_year': [{'year': 2023, 'cited_by_count': 2}, {'year': 2021, 'cited_by_count': 1}, {'year': 2020, 'cited_by_count': 1}, {'year': 2019, 'cited_by_count': 2}, {'year': 2018, 'cited_by_count': 1}, {'year': 2017, 'cited_by_count': 2}, {'year': 2014, 'cited_by_count': 2}, {'year': 2013, 'cited_by_count': 1}], 'updated_date': '2024-12-14T09:14:11.850399', 'created_date': '2016-06-24'}
Publication Information

Basic Information

Access and Citation

AI Researcher Chatbot

Primary Location

Authors

Topics

Keywords

Related Works
