Get quick answers to your questions about the article from our AI researcher chatbot
{'id': 'https://openalex.org/W159504299', 'doi': 'https://doi.org/10.1007/978-3-642-45278-9_39', 'title': 'New Approximation Algorithms for the Vertex Cover Problem', 'display_name': 'New Approximation Algorithms for the Vertex Cover Problem', 'publication_year': 2013, 'publication_date': '2013-01-01', 'ids': {'openalex': 'https://openalex.org/W159504299', 'doi': 'https://doi.org/10.1007/978-3-642-45278-9_39', 'mag': '159504299'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1007/978-3-642-45278-9_39', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S106296714', 'display_name': 'Lecture notes in computer science', 'issn_l': '0302-9743', 'issn': ['0302-9743', '1611-3349'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319900', 'host_organization_name': 'Springer Science+Business Media', 'host_organization_lineage': ['https://openalex.org/P4310319965', 'https://openalex.org/P4310319900'], 'host_organization_lineage_names': ['Springer Nature', 'Springer Science+Business Media'], 'type': 'book series'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'book-chapter', 'type_crossref': 'book-chapter', '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/A5061511897', 'display_name': 'François Delbot', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I1294671590', 'display_name': 'Centre National de la Recherche Scientifique', 'ror': 'https://ror.org/02feahw73', 'country_code': 'FR', 'type': 'government', 'lineage': ['https://openalex.org/I1294671590']}, {'id': 'https://openalex.org/I40434647', 'display_name': 'Université Paris Nanterre', 'ror': 'https://ror.org/013bkhk48', 'country_code': 'FR', 'type': 'education', 'lineage': ['https://openalex.org/I40434647']}], 'countries': ['FR'], 'is_corresponding': False, 'raw_author_name': 'Franc̨ois Delbot', 'raw_affiliation_strings': ['LIP6, CNRS UMR7606, Université Paris Ouest Nanterre, 4 place Jussieu, 75005, Paris, France'], 'affiliations': [{'raw_affiliation_string': 'LIP6, CNRS UMR7606, Université Paris Ouest Nanterre, 4 place Jussieu, 75005, Paris, France', 'institution_ids': ['https://openalex.org/I1294671590', 'https://openalex.org/I40434647']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5087533174', 'display_name': 'Christian Laforest', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I1294671590', 'display_name': 'Centre National de la Recherche Scientifique', 'ror': 'https://ror.org/02feahw73', 'country_code': 'FR', 'type': 'government', 'lineage': ['https://openalex.org/I1294671590']}, {'id': 'https://openalex.org/I4210099416', 'display_name': "Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes", 'ror': 'https://ror.org/00t3fpp34', 'country_code': 'FR', 'type': 'facility', 'lineage': ['https://openalex.org/I1294671590', 'https://openalex.org/I198244214', 'https://openalex.org/I203339264', 'https://openalex.org/I3019848993', 'https://openalex.org/I4210099416', 'https://openalex.org/I4210123221', 'https://openalex.org/I4210159245', 'https://openalex.org/I4387154249']}, {'id': 'https://openalex.org/I169645620', 'display_name': 'Institut Pascal', 'ror': 'https://ror.org/03vgfxd91', 'country_code': 'FR', 'type': 'facility', 'lineage': ['https://openalex.org/I1294671590', 'https://openalex.org/I169645620', 'https://openalex.org/I198244214', 'https://openalex.org/I4210095849']}], 'countries': ['FR'], 'is_corresponding': False, 'raw_author_name': 'Christian Laforest', 'raw_affiliation_strings': ['LIMOS, CNRS UMR 6158, Université Blaise Pascal, Campus des Cézeaux, 24 avenue des Landais, 63173, Aubière Cedex, France'], 'affiliations': [{'raw_affiliation_string': 'LIMOS, CNRS UMR 6158, Université Blaise Pascal, Campus des Cézeaux, 24 avenue des Landais, 63173, Aubière Cedex, France', 'institution_ids': ['https://openalex.org/I1294671590', 'https://openalex.org/I4210099416', 'https://openalex.org/I169645620']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5055330596', 'display_name': 'Raksmey Phan', 'orcid': 'https://orcid.org/0000-0001-5586-586X'}, 'institutions': [{'id': 'https://openalex.org/I4210099416', 'display_name': "Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes", 'ror': 'https://ror.org/00t3fpp34', 'country_code': 'FR', 'type': 'facility', 'lineage': ['https://openalex.org/I1294671590', 'https://openalex.org/I198244214', 'https://openalex.org/I203339264', 'https://openalex.org/I3019848993', 'https://openalex.org/I4210099416', 'https://openalex.org/I4210123221', 'https://openalex.org/I4210159245', 'https://openalex.org/I4387154249']}, {'id': 'https://openalex.org/I169645620', 'display_name': 'Institut Pascal', 'ror': 'https://ror.org/03vgfxd91', 'country_code': 'FR', 'type': 'facility', 'lineage': ['https://openalex.org/I1294671590', 'https://openalex.org/I169645620', 'https://openalex.org/I198244214', 'https://openalex.org/I4210095849']}, {'id': 'https://openalex.org/I1294671590', 'display_name': 'Centre National de la Recherche Scientifique', 'ror': 'https://ror.org/02feahw73', 'country_code': 'FR', 'type': 'government', 'lineage': ['https://openalex.org/I1294671590']}], 'countries': ['FR'], 'is_corresponding': False, 'raw_author_name': 'Raksmey Phan', 'raw_affiliation_strings': ['LIMOS, CNRS UMR 6158, Université Blaise Pascal, Campus des Cézeaux, 24 avenue des Landais, 63173, Aubière Cedex, France'], 'affiliations': [{'raw_affiliation_string': 'LIMOS, CNRS UMR 6158, Université Blaise Pascal, Campus des Cézeaux, 24 avenue des Landais, 63173, Aubière Cedex, France', 'institution_ids': ['https://openalex.org/I4210099416', 'https://openalex.org/I169645620', 'https://openalex.org/I1294671590']}]}], 'countries_distinct_count': 1, 'institutions_distinct_count': 4, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': {'value': 5000, 'currency': 'EUR', 'value_usd': 5392, 'provenance': 'doaj'}, 'apc_paid': None, 'fwci': 1.856, 'has_fulltext': False, 'cited_by_count': 6, 'citation_normalized_percentile': {'value': 0.824022, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 82, 'max': 83}, 'biblio': {'volume': None, 'issue': None, 'first_page': '438', 'last_page': '442'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10720', 'display_name': 'Combinatorial Optimization and Complexity Theory', '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': 'Combinatorial Optimization and Complexity Theory', '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': 'Graph Theory and Algorithms', 'score': 0.9997, '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/T10996', 'display_name': 'Mesh Generation Algorithms', 'score': 0.998, 'subfield': {'id': 'https://openalex.org/subfields/1704', 'display_name': 'Computer Graphics and Computer-Aided Design'}, '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/vertex-cover', 'display_name': 'Vertex cover', 'score': 0.8941132}, {'id': 'https://openalex.org/keywords/constant', 'display_name': 'Constant (computer programming)', 'score': 0.67115825}, {'id': 'https://openalex.org/keywords/approximation-algorithms', 'display_name': 'Approximation Algorithms', 'score': 0.576245}, {'id': 'https://openalex.org/keywords/constraint-satisfaction-problems', 'display_name': 'Constraint Satisfaction Problems', 'score': 0.538937}, {'id': 'https://openalex.org/keywords/edge-cover', 'display_name': 'Edge cover', 'score': 0.45521894}], 'concepts': [{'id': 'https://openalex.org/C40687702', 'wikidata': 'https://www.wikidata.org/wiki/Q11515519', 'display_name': 'Vertex cover', 'level': 3, 'score': 0.8941132}, {'id': 'https://openalex.org/C148764684', 'wikidata': 'https://www.wikidata.org/wiki/Q621751', 'display_name': 'Approximation algorithm', 'level': 2, 'score': 0.7210664}, {'id': 'https://openalex.org/C2777027219', 'wikidata': 'https://www.wikidata.org/wiki/Q1284190', 'display_name': 'Constant (computer programming)', 'level': 2, 'score': 0.67115825}, {'id': 'https://openalex.org/C80899671', 'wikidata': 'https://www.wikidata.org/wiki/Q1304193', 'display_name': 'Vertex (graph theory)', 'level': 3, 'score': 0.65035295}, {'id': 'https://openalex.org/C2780990831', 'wikidata': 'https://www.wikidata.org/wiki/Q319141', 'display_name': 'Conjecture', 'level': 2, 'score': 0.5991936}, {'id': 'https://openalex.org/C2780428219', 'wikidata': 'https://www.wikidata.org/wiki/Q16952335', 'display_name': 'Cover (algebra)', 'level': 2, 'score': 0.59117085}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.49822402}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.49508634}, {'id': 'https://openalex.org/C17762858', 'wikidata': 'https://www.wikidata.org/wiki/Q594001', 'display_name': 'Edge cover', 'level': 3, 'score': 0.45521894}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.4022323}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.35985482}, {'id': 'https://openalex.org/C132525143', 'wikidata': 'https://www.wikidata.org/wiki/Q141488', 'display_name': 'Graph', 'level': 2, 'score': 0.16184235}, {'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/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': 3, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1007/978-3-642-45278-9_39', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S106296714', 'display_name': 'Lecture notes in computer science', 'issn_l': '0302-9743', 'issn': ['0302-9743', '1611-3349'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319900', 'host_organization_name': 'Springer Science+Business Media', 'host_organization_lineage': ['https://openalex.org/P4310319965', 'https://openalex.org/P4310319900'], 'host_organization_lineage_names': ['Springer Nature', 'Springer Science+Business Media'], 'type': 'book series'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://hal.archives-ouvertes.fr/hal-01215211', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://hal.science/hal-01215211', 'pdf_url': None, 'source': None, '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': 16, 'referenced_works': ['https://openalex.org/W1572977974', 'https://openalex.org/W1573904809', 'https://openalex.org/W159504299', 'https://openalex.org/W1814966089', 'https://openalex.org/W1980447623', 'https://openalex.org/W1991790827', 'https://openalex.org/W2030970869', 'https://openalex.org/W2053913299', 'https://openalex.org/W2065161629', 'https://openalex.org/W2087226760', 'https://openalex.org/W2088806939', 'https://openalex.org/W2137118456', 'https://openalex.org/W2143838916', 'https://openalex.org/W2611804663', 'https://openalex.org/W2801463174', 'https://openalex.org/W4241764762'], 'related_works': ['https://openalex.org/W4285240128', 'https://openalex.org/W2551034790', 'https://openalex.org/W2538178083', 'https://openalex.org/W2125212169', 'https://openalex.org/W2056597184', 'https://openalex.org/W2029933769', 'https://openalex.org/W1968988491', 'https://openalex.org/W1712180277', 'https://openalex.org/W1548167816', 'https://openalex.org/W1502438505'], 'abstract_inverted_index': {'The': [0], 'vertex': [1], 'cover': [2], 'is': [3, 21], 'a': [4, 30, 41], 'classical': [5], 'NP-complete': [6], 'problem': [7], 'that': [8, 19, 57], 'has': [9, 60], 'received': [10], 'great': [11], 'attention': [12], 'these': [13], 'last': [14], 'decades.': [15], 'A': [16], 'conjecture': [17], 'states': [18], 'there': [20], 'no': [22], 'c-approximation': [23], 'polynomial': [24], 'algorithm': [25, 43, 59], 'for': [26], 'it': [27], 'with': [28, 44], 'c': [29], 'constant': [31], 'strictly': [32, 47], 'less': [33, 48], 'than': [34, 49], '2.': [35], 'In': [36], 'this': [37], 'paper': [38], 'we': [39, 55], 'propose': [40], 'new': [42], 'approximation': [45], 'ratio': [46], '2': [50], '(but': [51], 'non': [52], 'constant).': [53], 'Moreover': [54], 'show': [56], 'our': [58], 'the': [61], 'potential': [62], 'to': [63], 'return': [64], 'any': [65], 'optimal': [66], 'solution.': [67]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W159504299', 'counts_by_year': [{'year': 2022, 'cited_by_count': 1}, {'year': 2016, 'cited_by_count': 1}, {'year': 2015, 'cited_by_count': 1}, {'year': 2014, 'cited_by_count': 2}, {'year': 2013, 'cited_by_count': 1}], 'updated_date': '2024-08-17T16:11:00.042878', 'created_date': '2016-06-24'}