Publication Information

{'id': 'https://openalex.org/W3049110439', 'doi': 'https://doi.org/10.1142/s1793830921500087', 'title': 'Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree', 'display_name': 'Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree', 'publication_year': 2020, 'publication_date': '2020-08-16', 'ids': {'openalex': 'https://openalex.org/W3049110439', 'doi': 'https://doi.org/10.1142/s1793830921500087', 'mag': '3049110439'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1142/s1793830921500087', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S178434951', 'display_name': 'Discrete Mathematics Algorithms and Applications', 'issn_l': '1793-8309', 'issn': ['1793-8309', '1793-8317'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319815', 'host_organization_name': 'World Scientific', 'host_organization_lineage': ['https://openalex.org/P4310319815'], 'host_organization_lineage_names': ['World Scientific'], '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': True, 'oa_status': 'green', 'oa_url': 'https://arxiv.org/pdf/1710.07040', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5077975268', 'display_name': 'Parikshit Saikia', 'orcid': 'https://orcid.org/0000-0001-6306-9994'}, 'institutions': [{'id': 'https://openalex.org/I1317621060', 'display_name': 'Indian Institute of Technology Guwahati', 'ror': 'https://ror.org/0022nd079', 'country_code': 'IN', 'type': 'education', 'lineage': ['https://openalex.org/I1317621060']}], 'countries': ['IN'], 'is_corresponding': True, 'raw_author_name': 'Parikshit Saikia', 'raw_affiliation_strings': ['Department of Computer Science and Engineering, Indian Institute of Technology Guwahati, 781039 India'], 'affiliations': [{'raw_affiliation_string': 'Department of Computer Science and Engineering, Indian Institute of Technology Guwahati, 781039 India', 'institution_ids': ['https://openalex.org/I1317621060']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5105142501', 'display_name': 'Sushanta Karmakar', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I1317621060', 'display_name': 'Indian Institute of Technology Guwahati', 'ror': 'https://ror.org/0022nd079', 'country_code': 'IN', 'type': 'education', 'lineage': ['https://openalex.org/I1317621060']}], 'countries': ['IN'], 'is_corresponding': False, 'raw_author_name': 'Sushanta Karmakar', 'raw_affiliation_strings': ['Department of Computer Science and Engineering, Indian Institute of Technology Guwahati, 781039 India'], 'affiliations': [{'raw_affiliation_string': 'Department of Computer Science and Engineering, Indian Institute of Technology Guwahati, 781039 India', 'institution_ids': ['https://openalex.org/I1317621060']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5091546742', 'display_name': 'Aris Pagourtzis', 'orcid': 'https://orcid.org/0000-0002-6220-3722'}, 'institutions': [{'id': 'https://openalex.org/I174458059', 'display_name': 'National Technical University of Athens', 'ror': 'https://ror.org/03cx6bg69', 'country_code': 'GR', 'type': 'education', 'lineage': ['https://openalex.org/I174458059']}], 'countries': ['GR'], 'is_corresponding': False, 'raw_author_name': 'Aris Pagourtzis', 'raw_affiliation_strings': ['National Technical University of Athens, School of Electrical and Computer Engineering, Department of Computer Science, Heroon Politechniou, 9 GR-15780 Zographou, Greece'], 'affiliations': [{'raw_affiliation_string': 'National Technical University of Athens, School of Electrical and Computer Engineering, Department of Computer Science, Heroon Politechniou, 9 GR-15780 Zographou, Greece', 'institution_ids': ['https://openalex.org/I174458059']}]}], 'institution_assertions': [], 'countries_distinct_count': 2, 'institutions_distinct_count': 2, 'corresponding_author_ids': ['https://openalex.org/A5077975268'], 'corresponding_institution_ids': ['https://openalex.org/I1317621060'], 'apc_list': None, 'apc_paid': None, 'fwci': 0.114, 'has_fulltext': False, 'cited_by_count': 1, 'citation_normalized_percentile': {'value': 0.381187, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 60, 'max': 69}, 'biblio': {'volume': '13', 'issue': '02', 'first_page': '2150008', 'last_page': '2150008'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9986, '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.9986, '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/T11704', 'display_name': 'Mobile Crowdsensing and Crowdsourcing', 'score': 0.9954, 'subfield': {'id': 'https://openalex.org/subfields/1706', 'display_name': 'Computer Science Applications'}, '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/T11612', 'display_name': 'Stochastic Gradient Optimization Techniques', 'score': 0.9895, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, '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/steiner-tree-problem', 'display_name': 'Steiner tree problem', 'score': 0.9198476}, {'id': 'https://openalex.org/keywords/tree', 'display_name': 'Tree (set theory)', 'score': 0.44035834}], 'concepts': [{'id': 'https://openalex.org/C76220878', 'wikidata': 'https://www.wikidata.org/wiki/Q1764144', 'display_name': 'Steiner tree problem', 'level': 2, 'score': 0.9198476}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.6507051}, {'id': 'https://openalex.org/C175859090', 'wikidata': 'https://www.wikidata.org/wiki/Q322212', 'display_name': 'Travelling salesman problem', 'level': 2, 'score': 0.5932701}, {'id': 'https://openalex.org/C148764684', 'wikidata': 'https://www.wikidata.org/wiki/Q621751', 'display_name': 'Approximation algorithm', 'level': 2, 'score': 0.5930188}, {'id': 'https://openalex.org/C177148314', 'wikidata': 'https://www.wikidata.org/wiki/Q170084', 'display_name': 'Generalization', 'level': 2, 'score': 0.5371936}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.5265517}, {'id': 'https://openalex.org/C113174947', 'wikidata': 'https://www.wikidata.org/wiki/Q2859736', 'display_name': 'Tree (set theory)', 'level': 2, 'score': 0.44035834}, {'id': 'https://openalex.org/C130120984', 'wikidata': 'https://www.wikidata.org/wiki/Q2835898', 'display_name': 'Distributed algorithm', 'level': 2, 'score': 0.43209383}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.40304038}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.40236965}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.3747666}, {'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/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 2, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1142/s1793830921500087', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S178434951', 'display_name': 'Discrete Mathematics Algorithms and Applications', 'issn_l': '1793-8309', 'issn': ['1793-8309', '1793-8317'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319815', 'host_organization_name': 'World Scientific', 'host_organization_lineage': ['https://openalex.org/P4310319815'], 'host_organization_lineage_names': ['World Scientific'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1710.07040', 'pdf_url': 'https://arxiv.org/pdf/1710.07040', 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell 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://arxiv.org/abs/1710.07040', 'pdf_url': 'https://arxiv.org/pdf/1710.07040', 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'sustainable_development_goals': [{'score': 0.66, 'display_name': 'Life on land', 'id': 'https://metadata.un.org/sdg/15'}], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 30, 'referenced_works': ['https://openalex.org/W132245160', 'https://openalex.org/W1568087609', 'https://openalex.org/W1578705518', 'https://openalex.org/W1881248737', 'https://openalex.org/W1928638915', 'https://openalex.org/W1968304853', 'https://openalex.org/W1984090926', 'https://openalex.org/W1986056047', 'https://openalex.org/W1991055327', 'https://openalex.org/W1991107961', 'https://openalex.org/W2011823863', 'https://openalex.org/W2015819397', 'https://openalex.org/W2030825457', 'https://openalex.org/W2040273581', 'https://openalex.org/W2042437235', 'https://openalex.org/W2044119054', 'https://openalex.org/W2048013200', 'https://openalex.org/W2056399203', 'https://openalex.org/W2058191123', 'https://openalex.org/W2062310236', 'https://openalex.org/W2071057992', 'https://openalex.org/W2074613642', 'https://openalex.org/W2077371116', 'https://openalex.org/W2087987937', 'https://openalex.org/W2099618932', 'https://openalex.org/W2107338086', 'https://openalex.org/W2118486696', 'https://openalex.org/W2123087902', 'https://openalex.org/W2401610261', 'https://openalex.org/W4205300528'], 'related_works': ['https://openalex.org/W328736688', 'https://openalex.org/W3184075718', 'https://openalex.org/W2995411114', 'https://openalex.org/W2404561224', 'https://openalex.org/W2367195720', 'https://openalex.org/W2009976792', 'https://openalex.org/W2004321562', 'https://openalex.org/W1998126097', 'https://openalex.org/W1980288485', 'https://openalex.org/W1968497507'], 'abstract_inverted_index': {'The': [0, 87, 247], 'Prize-collecting': [1], 'Steiner': [2, 11, 90, 123, 177], 'tree': [3, 12, 91, 124, 178], '(PCST)': [4], 'problem': [5, 13, 140], 'is': [6, 201, 250, 352, 399], 'a': [7, 28, 193, 210, 223, 226, 258, 265, 325, 404], 'generalization': [8], 'of': [9, 153, 183, 188, 231, 260, 272, 276, 291, 356, 378, 390, 403], 'the': [10, 46, 135, 139, 147, 151, 156, 174, 198, 253, 273, 277, 286, 292, 296, 319, 345, 353, 366, 373, 379, 383, 400, 407], 'that': [14, 221, 324], 'finds': [15], 'applications': [16], 'in': [17, 96, 146, 264, 295, 344, 376, 392, 406], 'network': [18], 'design,': [19], 'content': [20], 'distribution': [21], 'networks,': [22], 'and': [23, 40, 60, 84, 94, 114, 125, 240, 256, 288, 303, 312, 322, 339], 'many': [24], 'more.': [25], 'There': [26], 'are': [27, 163, 299], 'few': [29], 'centralized': [30], 'approximation': [31, 66, 119, 195, 217], 'algorithms': [32, 120, 159, 384], '[D.': [33], 'Bienstock,': [34], 'M.': [35, 57, 82, 111, 115], 'X.': [36, 58], 'Goemans,': [37], 'D.': [38, 41, 61, 79], 'Simchi-Levi': [39], 'Williamson,': [42, 63], 'A': [43, 64, 170], 'note': [44], 'on': [45, 173, 252, 270], 'prize': [47, 88, 242], 'collecting': [48, 89], 'traveling': [49], 'salesman': [50], 'problem.': [51, 137], 'Math.': [52, 75], 'Program.': [53], '59': [54], '(1993)': [55], '413–420;': [56], 'Goemans': [59], 'E.': [62], 'general': [65], 'technique': [67, 259], 'for': [68, 121, 133, 225, 244], 'constrained': [69], 'forest': [70], 'problems,': [71], 'SIAM': [72, 127], 'J.': [73, 128], 'Appl.': [74], '24(2)': [76], '(1995)': [77], '296–317;': [78], 'S.': [80, 85], 'Johnson,': [81], 'Minkoff': [83], 'Phillips,': [86], 'problem:': [92], 'Theory': [93], 'practice,': [95], 'Proc.': [97], 'Eleventh': [98], 'Annual': [99], 'ACM-SIAM': [100], 'Symp.': [101], 'Discrete': [102], 'Algorithms,': [103], 'SODA': [104], '’00': [105], '(2000),': [106], 'pp.': [107], '760–769;': [108], 'A.': [109], 'Archer,': [110], 'Hossein': [112], 'Bateni': [113], 'Taghi': [116], 'Hajiaghayi,': [117], 'Improved': [118], 'prize-collecting': [122, 176], 'TSP,': [126], 'Comput.': [129], '40(2)': [130], '(2011)': [131], '309–332]': [132], 'solving': [134], 'PCST': [136, 224, 329], 'However,': [138], 'has': [141], 'seen': [142], 'very': [143], 'little': [144], 'progress': [145], 'distributed': [148, 158, 175, 216, 266], 'setting;': [149], 'to': [150, 165, 191], 'best': [152], 'our': [154], 'knowledge,': [155], 'only': [157], 'proposed': [160], 'so': [161], 'far': [162], 'due': [164], 'Rossetti': [166], '[N.': [167], 'G.': [168], 'Rossetti,': [169], 'first': [171], 'attempt': [172], 'problem,': [179], 'M.Sc.': [180], 'thesis,': [181], 'University': [182], 'Iceland,': [184], 'Reykjavik': [185], '(2015)]:': [186], 'one': [187, 200, 375], 'them': [189], 'fails': [190], 'guarantee': [192], 'constant': [194], 'factor': [196, 215], 'while': [197], 'other': [199], 'essentially': [202], 'centralized.': [203], 'In': [204], 'this': [205], 'work,': [206], 'first,': [207], 'we': [208, 317], 'present': [209], 'deterministic': [211], '[Formula:': [212, 232, 283, 300, 304, 309, 313, 326, 335, 340, 349, 357, 363, 386, 396], 'see': [213, 233, 284, 301, 305, 310, 314, 327, 336, 341, 350, 358, 364, 387, 397], 'text]': [214, 234, 302, 306, 311, 337, 342, 351, 388, 398], 'algorithm': [218, 249, 294, 321, 369], '(D-PCST': [219], 'algorithm)': [220], 'constructs': [222], 'given': [227], 'connected': [228], 'undirected': [229], 'graph': [230, 282], 'nodes': [235], 'with': [236, 362], 'non-negative': [237, 241], 'edge': [238], 'weights': [239], 'value': [243], 'each': [245, 393], 'node.': [246], 'D-PCST': [248, 293, 320, 368], 'based': [251], 'primal-dual': [254], 'method': [255], 'uses': [257], 'preserving': [261], 'dual': [262], 'constraints': [263], 'manner,': [267], 'without': [268], 'relying': [269], 'knowledge': [271], 'global': [274], 'structure': [275], 'network.': [278], 'For': [279, 360], 'an': [280], 'input': [281], 'text],': [285, 365], 'round': [287, 380], 'message': [289], 'complexities': [290], 'CONGEST': [297, 346], 'model': [298], 'respectively,': [307], 'where': [308, 348, 395], 'text].': [315, 359], 'Furthermore,': [316], 'modify': [318], 'show': [323], 'text]-approximate': [328], 'can': [330], 'be': [331], 'deterministically': [332], 'computed': [333], 'using': [334], 'rounds': [338], 'messages': [343], 'model,': [347], 'unweighted': [354], 'diameter': [355], 'networks': [361], 'modified': [367], 'performs': [370], 'better': [371], 'than': [372], 'original': [374], 'terms': [377], 'complexity.': [381], 'Both': [382], 'require': [385], 'bits': [389], 'memory': [391], 'node,': [394], 'maximum': [401], 'degree': [402], 'node': [405], 'graph.': [408]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W3049110439', 'counts_by_year': [{'year': 2021, 'cited_by_count': 1}], 'updated_date': '2024-12-27T05:16:22.595984', 'created_date': '2020-08-21'}