Publication Information

{'id': 'https://openalex.org/W2167197687', 'doi': 'https://doi.org/10.1145/1082036.1082041', 'title': 'Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs', 'display_name': 'Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs', 'publication_year': 2005, 'publication_date': '2005-07-01', 'ids': {'openalex': 'https://openalex.org/W2167197687', 'doi': 'https://doi.org/10.1145/1082036.1082041', 'mag': '2167197687'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/1082036.1082041', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S118992489', 'display_name': 'Journal of the ACM', 'issn_l': '0004-5411', 'issn': ['0004-5411', '1557-735X'], '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/A5006699796', 'display_name': 'Haim Kaplan', 'orcid': 'https://orcid.org/0000-0001-9586-8002'}, 'institutions': [{'id': 'https://openalex.org/I16391192', 'display_name': 'Tel Aviv University', 'ror': 'https://ror.org/04mhzgx49', 'country_code': 'IL', 'type': 'education', 'lineage': ['https://openalex.org/I16391192']}], 'countries': ['IL'], 'is_corresponding': False, 'raw_author_name': 'Haim Kaplan', 'raw_affiliation_strings': ['Tel-Aviv University, Tel-Aviv, Israel'], 'affiliations': [{'raw_affiliation_string': 'Tel-Aviv University, Tel-Aviv, Israel', 'institution_ids': ['https://openalex.org/I16391192']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5012404981', 'display_name': 'Moshe Lewenstein', 'orcid': 'https://orcid.org/0000-0002-8272-244X'}, 'institutions': [{'id': 'https://openalex.org/I13955877', 'display_name': 'Bar-Ilan University', 'ror': 'https://ror.org/03kgsv495', 'country_code': 'IL', 'type': 'education', 'lineage': ['https://openalex.org/I13955877']}], 'countries': ['IL'], 'is_corresponding': False, 'raw_author_name': 'Moshe Lewenstein', 'raw_affiliation_strings': ['Bar-Ilan University, Ramat-Gan, Israel'], 'affiliations': [{'raw_affiliation_string': 'Bar-Ilan University, Ramat-Gan, Israel', 'institution_ids': ['https://openalex.org/I13955877']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5067943969', 'display_name': 'Nira Shafrir', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I16391192', 'display_name': 'Tel Aviv University', 'ror': 'https://ror.org/04mhzgx49', 'country_code': 'IL', 'type': 'education', 'lineage': ['https://openalex.org/I16391192']}], 'countries': ['IL'], 'is_corresponding': False, 'raw_author_name': 'Nira Shafrir', 'raw_affiliation_strings': ['Tel-Aviv University, Tel-Aviv, Israel'], 'affiliations': [{'raw_affiliation_string': 'Tel-Aviv University, Tel-Aviv, Israel', 'institution_ids': ['https://openalex.org/I16391192']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5111449864', 'display_name': 'Maxim Sviridenko', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I4210114115', 'display_name': 'IBM Research - Thomas J. Watson Research Center', 'ror': 'https://ror.org/0265w5591', 'country_code': 'US', 'type': 'facility', 'lineage': ['https://openalex.org/I1341412227', 'https://openalex.org/I4210114115']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Maxim Sviridenko', 'raw_affiliation_strings': ['IBM T.J. Watson Research Center, Yorktown Heights, New York'], 'affiliations': [{'raw_affiliation_string': 'IBM T.J. Watson Research Center, Yorktown Heights, New York', 'institution_ids': ['https://openalex.org/I4210114115']}]}], 'institution_assertions': [], 'countries_distinct_count': 2, 'institutions_distinct_count': 3, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 14.459, 'has_fulltext': False, 'cited_by_count': 184, 'citation_normalized_percentile': {'value': 0.999937, 'is_in_top_1_percent': True, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 98, 'max': 99}, 'biblio': {'volume': '52', 'issue': '4', 'first_page': '602', 'last_page': '626'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9853, '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.9853, '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/T10567', 'display_name': 'Vehicle Routing Optimization Methods', 'score': 0.9839, '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/T12176', 'display_name': 'Optimization and Packing Problems', 'score': 0.9709, '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'}}], 'keywords': [{'id': 'https://openalex.org/keywords/multigraph', 'display_name': 'Multigraph', 'score': 0.91034454}, {'id': 'https://openalex.org/keywords/cycle-basis', 'display_name': 'Cycle basis', 'score': 0.542771}, {'id': 'https://openalex.org/keywords/minimum-weight', 'display_name': 'Minimum weight', 'score': 0.49118826}], 'concepts': [{'id': 'https://openalex.org/C17758045', 'wikidata': 'https://www.wikidata.org/wiki/Q2642629', 'display_name': 'Multigraph', 'level': 3, 'score': 0.91034454}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.71263427}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.69042987}, {'id': 'https://openalex.org/C26752605', 'wikidata': 'https://www.wikidata.org/wiki/Q16766188', 'display_name': 'Cycle basis', 'level': 5, 'score': 0.542771}, {'id': 'https://openalex.org/C175859090', 'wikidata': 'https://www.wikidata.org/wiki/Q322212', 'display_name': 'Travelling salesman problem', 'level': 2, 'score': 0.53956515}, {'id': 'https://openalex.org/C2778945305', 'wikidata': 'https://www.wikidata.org/wiki/Q6865502', 'display_name': 'Minimum weight', 'level': 2, 'score': 0.49118826}, {'id': 'https://openalex.org/C80899671', 'wikidata': 'https://www.wikidata.org/wiki/Q1304193', 'display_name': 'Vertex (graph theory)', 'level': 3, 'score': 0.46291023}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.4436487}, {'id': 'https://openalex.org/C148764684', 'wikidata': 'https://www.wikidata.org/wiki/Q621751', 'display_name': 'Approximation algorithm', 'level': 2, 'score': 0.41411448}, {'id': 'https://openalex.org/C86524685', 'wikidata': 'https://www.wikidata.org/wiki/Q273037', 'display_name': 'Hamiltonian path', 'level': 3, 'score': 0.41155517}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.3623981}, {'id': 'https://openalex.org/C132525143', 'wikidata': 'https://www.wikidata.org/wiki/Q141488', 'display_name': 'Graph', 'level': 2, 'score': 0.16181836}, {'id': 'https://openalex.org/C203776342', 'wikidata': 'https://www.wikidata.org/wiki/Q1378376', 'display_name': 'Line graph', 'level': 3, 'score': 0.0}, {'id': 'https://openalex.org/C149530733', 'wikidata': 'https://www.wikidata.org/wiki/Q5597091', 'display_name': 'Graph power', 'level': 4, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/1082036.1082041', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S118992489', 'display_name': 'Journal of the ACM', 'issn_l': '0004-5411', 'issn': ['0004-5411', '1557-735X'], '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': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 31, 'referenced_works': ['https://openalex.org/W107646379', 'https://openalex.org/W1482447760', 'https://openalex.org/W1488861257', 'https://openalex.org/W1490932874', 'https://openalex.org/W1521148214', 'https://openalex.org/W1553729051', 'https://openalex.org/W1915280757', 'https://openalex.org/W1977006915', 'https://openalex.org/W1989048084', 'https://openalex.org/W2008217702', 'https://openalex.org/W2009803313', 'https://openalex.org/W2017314050', 'https://openalex.org/W2021625223', 'https://openalex.org/W2033530135', 'https://openalex.org/W2035610952', 'https://openalex.org/W2037050365', 'https://openalex.org/W2052352992', 'https://openalex.org/W2058748455', 'https://openalex.org/W2061753037', 'https://openalex.org/W2080721852', 'https://openalex.org/W2090223576', 'https://openalex.org/W2101468281', 'https://openalex.org/W2102403605', 'https://openalex.org/W2102706148', 'https://openalex.org/W2117226423', 'https://openalex.org/W2130200244', 'https://openalex.org/W2134761228', 'https://openalex.org/W2141355868', 'https://openalex.org/W2152453230', 'https://openalex.org/W2769376643', 'https://openalex.org/W2914372558'], 'related_works': ['https://openalex.org/W4381707782', 'https://openalex.org/W4300697888', 'https://openalex.org/W4241541331', 'https://openalex.org/W2963726052', 'https://openalex.org/W2952621743', 'https://openalex.org/W2896710021', 'https://openalex.org/W2769159583', 'https://openalex.org/W2259723333', 'https://openalex.org/W2016168023', 'https://openalex.org/W1002323541'], 'abstract_inverted_index': {'A': [0], 'directed': [1], 'multigraph': [2, 29, 53], 'is': [3, 17, 94, 120, 207, 250, 301], 'said': [4], 'to': [5, 101, 136, 196, 235, 289], 'be': [6], 'd': [7, 19, 51], '-regular': [8, 52], 'if': [9, 49], 'the': [10, 50, 123, 157, 168, 186, 189, 201, 212, 215, 221, 236, 246, 255, 261, 277, 280, 330], 'indegree': [11], 'and': [12, 96, 344], 'outdegree': [13], 'of': [14, 33, 63, 77, 89, 115, 126, 152, 156, 167, 188, 211, 214, 279, 294, 321, 329], 'every': [15], 'vertex': [16], 'exactly': [18], '.': [20, 326], 'By': [21], "Hall's": [22], 'theorem,': [23], 'one': [24, 87, 111], 'can': [25, 68], 'represent': [26], 'such': [27, 103, 112, 140], 'a': [28, 31, 70, 98, 104, 113, 138, 149, 179, 198, 226, 230, 242, 270, 297, 314], 'as': [30], 'combination': [32], 'at': [34, 85, 121, 183, 208, 274, 302], 'most': [35, 86, 275, 303], 'n': [36, 74, 307, 325], '2': [37, 75, 202, 306, 324], 'cycle': [38, 78, 116, 173, 203, 266, 295], 'covers,': [39, 204, 267], 'each': [40, 81, 90], 'taken': [41], 'with': [42, 181, 225, 272, 318, 348], 'an': [43, 132, 153], 'appropriate': [44], 'multiplicity.': [45], 'We': [46], 'prove': [47], 'that': [48, 175], 'does': [54], 'not': [55, 177, 268], 'contain': [56], 'more': [57], 'than': [58, 254, 309], '⌊': [59], 'd/2': [60], '⌋': [61], 'copies': [62], 'any': [64], '2-cycle': [65, 82, 180], 'then': [66, 144, 286], 'we': [67, 129, 193, 240, 285], 'find': [69, 102], 'similar': [71], 'decomposition': [72], 'into': [73], 'pairs': [76], 'covers': [79, 117, 174, 296], 'where': [80], 'occurs': [83], 'in': [84, 147], 'component': [88], 'pair.': [91], 'Our': [92], 'proof': [93], 'constructive': [95], 'gives': [97, 264], 'polynomial': [99], 'algorithm': [100, 135, 244, 317], 'decomposition.': [105], 'Since': [106], 'our': [107], 'applications': [108, 328], 'only': [109], 'need': [110], 'pair': [114, 293], 'whose': [118, 205, 299], 'weight': [119, 125, 182, 187, 206, 213, 273, 278, 300], 'least': [122, 184, 209], 'average': [124], 'all': [127], 'pairs,': [128], 'also': [130], 'give': [131], 'alternative,': [133], 'simpler': [134, 227, 253], 'extract': [137, 197], 'single': [139], 'pair.This': [141], 'combinatorial': [142], 'theorem': [143], 'comes': [145], 'handy': [146], 'rounding': [148, 169, 331], 'fractional': [150], 'solution': [151], 'LP': [154], 'relaxation': [155], 'maximum': [158, 233, 337, 345], 'Traveling': [159], 'Salesman': [160], 'Problem': [161], '(TSP)': [162], 'problem.': [163], 'The': [164], 'first': [165], 'stage': [166], 'procedure': [170, 332], 'obtains': [171], 'two': [172, 265], 'do': [176], 'share': [178], 'twice': [185, 276], 'optimal': [190], 'solution.': [191], 'Then': [192], 'show': [194, 287], 'how': [195, 288], 'tour': [199, 298], 'from': [200, 232, 291], '2/3': [210], 'longest': [216], 'tour.': [217], 'This': [218, 311], 'improves': [219, 312], 'upon': [220, 313], 'previous': [222, 256, 315], '5/8': [223], 'approximation': [224, 316, 319, 334], 'algorithm.': [228], 'Utilizing': [229], 'reduction': [231], 'TSP': [234, 347], 'shortest': [237], 'superstring': [238], 'problem,': [239, 248], 'obtain': [241, 290], '2.5-approximation': [243], 'for': [245, 336], 'latter': [247], 'which': [249], 'again': [251], 'much': [252], 'one.For': [257], 'minimum': [258], 'asymmetric': [259, 346], 'TSP,': [260], 'same': [262], 'technique': [263], 'sharing': [269], '2-cycle,': [271], 'optimum.': [281], 'Assuming': [282], 'triangle': [283, 349], 'inequality,': [284], 'this': [292], '0.842': [304], 'log': [305, 323], 'larger': [308], 'optimal.': [310], 'guarantee': [320], '0.999': [322], 'Other': [327], 'are': [333], 'algorithms': [335], '3-cycle': [338], 'cover': [339], '(factor': [340, 351], '2/3,': [341], 'previously': [342, 353], '3/5)': [343], 'inequality': [350], '10/13,': [352], '3/4).': [354]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2167197687', 'counts_by_year': [{'year': 2024, 'cited_by_count': 2}, {'year': 2023, 'cited_by_count': 1}, {'year': 2022, 'cited_by_count': 2}, {'year': 2021, 'cited_by_count': 3}, {'year': 2020, 'cited_by_count': 6}, {'year': 2019, 'cited_by_count': 5}, {'year': 2018, 'cited_by_count': 6}, {'year': 2017, 'cited_by_count': 5}, {'year': 2016, 'cited_by_count': 5}, {'year': 2015, 'cited_by_count': 12}, {'year': 2014, 'cited_by_count': 16}, {'year': 2013, 'cited_by_count': 23}, {'year': 2012, 'cited_by_count': 10}], 'updated_date': '2024-12-31T11:41:01.141280', 'created_date': '2016-06-24'}