Publication Information

{'id': 'https://openalex.org/W2619836383', 'doi': None, 'title': 'Tropical aspects of linear programming', 'display_name': 'Tropical aspects of linear programming', 'publication_year': 2014, 'publication_date': '2014-12-02', 'ids': {'openalex': 'https://openalex.org/W2619836383', 'mag': '2619836383'}, 'language': 'en', 'primary_location': {'is_oa': True, 'landing_page_url': 'https://hal-polytechnique.archives-ouvertes.fr/tel-01198482', 'pdf_url': 'https://polytechnique.hal.science/tel-01198482/document', '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': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'type': 'preprint', 'type_crossref': 'dissertation', 'indexed_in': [], 'open_access': {'is_oa': True, 'oa_status': 'green', 'oa_url': 'https://polytechnique.hal.science/tel-01198482/document', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5091386742', 'display_name': 'Pascal Benchimol', 'orcid': None}, 'institutions': [], 'countries': [], 'is_corresponding': True, 'raw_author_name': 'Benchimol, Pascal', 'raw_affiliation_strings': [], 'affiliations': []}], 'institution_assertions': [], 'countries_distinct_count': 0, 'institutions_distinct_count': 0, 'corresponding_author_ids': ['https://openalex.org/A5091386742'], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': None, 'has_fulltext': False, 'cited_by_count': 5, 'citation_normalized_percentile': {'value': 0.844391, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 81, 'max': 82}, 'biblio': {'volume': None, 'issue': None, 'first_page': None, 'last_page': None}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T11435', 'display_name': 'Polynomial and algebraic computation', 'score': 0.9959, '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/T11435', 'display_name': 'Polynomial and algebraic computation', 'score': 0.9959, '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/polyhedron', 'display_name': 'Polyhedron', 'score': 0.5703446}, {'id': 'https://openalex.org/keywords/revised-simplex-method', 'display_name': 'Revised simplex method', 'score': 0.5241894}, {'id': 'https://openalex.org/keywords/simplex', 'display_name': 'Simplex', 'score': 0.5190935}, {'id': 'https://openalex.org/keywords/interior-point-method', 'display_name': 'Interior point method', 'score': 0.4319679}], 'concepts': [{'id': 'https://openalex.org/C41045048', 'wikidata': 'https://www.wikidata.org/wiki/Q202843', 'display_name': 'Linear programming', 'level': 2, 'score': 0.79461336}, {'id': 'https://openalex.org/C144521790', 'wikidata': 'https://www.wikidata.org/wiki/Q134164', 'display_name': 'Simplex algorithm', 'level': 3, 'score': 0.72570086}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.6545944}, {'id': 'https://openalex.org/C2780990831', 'wikidata': 'https://www.wikidata.org/wiki/Q319141', 'display_name': 'Conjecture', 'level': 2, 'score': 0.61031127}, {'id': 'https://openalex.org/C54829058', 'wikidata': 'https://www.wikidata.org/wiki/Q172937', 'display_name': 'Polyhedron', 'level': 2, 'score': 0.5703446}, {'id': 'https://openalex.org/C205658194', 'wikidata': 'https://www.wikidata.org/wiki/Q4168281', 'display_name': 'Linear-fractional programming', 'level': 3, 'score': 0.5666174}, {'id': 'https://openalex.org/C90119067', 'wikidata': 'https://www.wikidata.org/wiki/Q43260', 'display_name': 'Polynomial', 'level': 2, 'score': 0.5253871}, {'id': 'https://openalex.org/C191157680', 'wikidata': 'https://www.wikidata.org/wiki/Q17085895', 'display_name': 'Revised simplex method', 'level': 4, 'score': 0.5241894}, {'id': 'https://openalex.org/C62438384', 'wikidata': 'https://www.wikidata.org/wiki/Q331350', 'display_name': 'Simplex', 'level': 2, 'score': 0.5190935}, {'id': 'https://openalex.org/C155253501', 'wikidata': 'https://www.wikidata.org/wiki/Q461992', 'display_name': 'Interior point method', 'level': 2, 'score': 0.4319679}, {'id': 'https://openalex.org/C33676613', 'wikidata': 'https://www.wikidata.org/wiki/Q13415176', 'display_name': 'Dimension (graph theory)', 'level': 2, 'score': 0.4316076}, {'id': 'https://openalex.org/C2777735758', 'wikidata': 'https://www.wikidata.org/wiki/Q817765', 'display_name': 'Path (computing)', 'level': 2, 'score': 0.43031055}, {'id': 'https://openalex.org/C84135550', 'wikidata': 'https://www.wikidata.org/wiki/Q3154022', 'display_name': 'Linear inequality', 'level': 3, 'score': 0.4279091}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.38441306}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.37341112}, {'id': 'https://openalex.org/C126255220', 'wikidata': 'https://www.wikidata.org/wiki/Q141495', 'display_name': 'Mathematical optimization', 'level': 1, 'score': 0.33512688}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.20936504}, {'id': 'https://openalex.org/C134306372', 'wikidata': 'https://www.wikidata.org/wiki/Q7754', 'display_name': 'Mathematical analysis', 'level': 1, 'score': 0.14291948}, {'id': 'https://openalex.org/C45555294', 'wikidata': 'https://www.wikidata.org/wiki/Q28113351', 'display_name': 'Inequality', 'level': 2, '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': True, 'landing_page_url': 'https://hal-polytechnique.archives-ouvertes.fr/tel-01198482', 'pdf_url': 'https://polytechnique.hal.science/tel-01198482/document', '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': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': None, 'pdf_url': 'https://hal-polytechnique.archives-ouvertes.fr/tel-01198482/document', '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': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'https://hal-polytechnique.archives-ouvertes.fr/tel-01198482', 'pdf_url': 'https://polytechnique.hal.science/tel-01198482/document', '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': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 0, 'referenced_works': [], 'related_works': ['https://openalex.org/W3125179639', 'https://openalex.org/W2964424355', 'https://openalex.org/W2730708452', 'https://openalex.org/W25030584', 'https://openalex.org/W2337360258', 'https://openalex.org/W2133667137', 'https://openalex.org/W2079260672', 'https://openalex.org/W2041443873', 'https://openalex.org/W1709621369', 'https://openalex.org/W1600675813'], 'abstract_inverted_index': {'In': [0, 177, 350], 'this': [1, 139, 179, 535], 'thesis,': [2], 'we': [3, 93, 141, 356, 378, 435, 538], 'present': [4, 539], 'new': [5, 325, 359], 'results': [6, 381], 'on': [7, 14, 27, 153, 277, 292, 332, 371, 449, 498, 516, 534], 'the': [8, 15, 28, 34, 37, 45, 62, 88, 98, 118, 124, 130, 135, 150, 155, 171, 175, 182, 192, 207, 211, 237, 257, 260, 272, 278, 286, 293, 298, 309, 333, 336, 391, 400, 424, 427, 438, 452, 455, 466, 482, 485, 490, 494, 499, 521, 543, 575, 583], 'complexity': [9, 380, 572], 'of': [10, 19, 36, 87, 97, 132, 134, 145, 165, 174, 210, 224, 256, 259, 281, 297, 308, 335, 374, 393, 426, 430, 454, 465, 468, 473, 481, 484, 502, 505, 523, 526, 542, 554, 585], 'classical': [11, 51, 77, 146, 202, 273, 383, 401, 491, 527, 576], 'linear': [12, 21, 52, 55, 78, 108, 147, 203, 225, 283, 314, 345, 386, 414], 'programming': [13, 22, 315, 415], 'one': [16], 'hand,': [17], 'and': [18, 23, 72, 218, 301, 316, 416, 433, 471, 530], 'tropical': [20, 58, 287, 310, 313, 344, 368, 385, 413, 463, 495, 510, 544, 556], 'mean': [24, 317, 419, 443], 'payoff': [25, 318, 420, 444], 'games': [26, 445, 456], 'other': [29], 'hand.\r\nOur': [30], 'contributions': [31], 'lie': [32, 291], 'in': [33, 170, 191, 247, 446, 489, 562, 568, 592], 'study': [35], 'interplay': [38], 'between': [39, 520], 'these': [40, 329], 'two': [41], 'problems': [42, 330], 'provided': [43, 122], 'by': [44, 123, 215, 220, 559], 'dequantization': [46], 'process.': [47], 'This': [48, 476, 512], 'process': [49], 'tranforms': [50], 'programs': [53, 56, 148, 226, 346], 'into': [54], 'over': [57, 110, 149], 'semirings,': [59], 'such': [60], 'as': [61, 70, 74], '$\\R': [64], '\\cup\\{': [65], '-\\infty\\}$': [66], 'endowed': [67], 'with': [68, 158, 227, 305], '$\\max$': [69], 'addition': [71], '$+$': [73], 'muliplication.': [75], '\r\n\r\nConcerning': [76], 'programming,': [79], 'our': [81, 320], 'first': [82, 439], 'contribution': [83, 196], 'is': [84, 168, 189, 245, 323, 365, 514], 'a': [85, 106, 143, 163, 186, 222, 241, 267, 282, 306, 324, 358, 394, 409, 458, 474, 478, 509, 517, 555, 571], 'tropicalization': [86, 258, 296, 334, 483], 'simplex': [89, 99, 156, 311, 337, 402, 486], 'method.': [90, 338, 487], 'More': [91], 'precisely,': [92], 'describe': [94], 'an': [95, 111, 503, 524, 552], 'implementation': [96, 115], 'method': [100], 'that,': [101], 'under': [102], 'genericity': [103, 348], 'conditions,': [104], 'solves': [105, 442], 'program': [109], 'ordered': [112, 376], 'field.': [113], 'Our': [114, 362], 'uses': [116], 'only': [117], 'restricted': [119], 'information': [121], 'valuation': [125], 'map,': [126], 'which': [127, 154, 167, 188, 244], 'corresponds': [128], 'to': [129, 327, 343, 352, 366, 384, 508, 574], '``orders': [131], "magnitude''": [133], 'input.': [136], 'Using': [138], 'approach,': [140], 'exhibit': [142], 'class': [144], 'real': [151], 'numbers': [152], 'method,': [157, 403], 'any': [159], 'pivoting': [160, 396, 545, 550, 577], 'rule,': [161], 'performs': [162], 'number': [164], 'iterations': [166], 'polynomial': [169, 190, 410, 447], 'input': [172, 193], 'size': [173], 'problem.': [176], 'particular,': [178], 'implies': [180], 'that': [181, 390, 441, 549, 582], 'corresponding': [183], 'polyhedra': [184], 'have': [185], 'diameter': [187], 'size.\r\nOur': [194], 'second': [195], 'concerns': [197], 'interior': [198], 'point': [199, 252], 'methods': [200], 'for': [201, 399, 412, 418], 'programming.': [204, 387], 'We': [205, 250, 388, 547, 579], 'disprove': [206], 'continuous': [208], 'analog': [209], 'Hirsch': [212], 'conjecture': [213], 'proposed': [214], 'Deza,': [216], 'Terlaky': [217], 'Zinchenko,': [219], 'constructing': [221], 'family': [223], '$3r': [228], '+': [229, 234], '4$': [230], 'inequalities': [231, 561], 'in\r\ndimension': [232], '$2r': [233], '2$': [235], 'where': [236], 'central': [238, 261, 274, 288], 'path': [239, 275, 289, 307], 'has': [240, 266], 'total': [242], 'curvature': [243], 'exponential': [246], '$r$.': [248], 'also': [251, 436, 580], 'out': [253], 'suprising': [254], 'features': [255], 'path.': [262], 'For': [263], 'example': [264], 'it': [265], 'purely': [268], 'geometric': [269, 479, 518, 536], 'description,': [270], 'while': [271], 'depends': [276], 'algebraic': [279], 'representation': [280], 'program.': [284], 'Moreover,': [285], 'may': [290, 302], 'boundary': [294], 'of\r\nthe': [295], 'feasible': [299], 'set,': [300], 'even': [303], 'coincide': [304], 'method.\r\n\r\n\r\nConcerning': [312], 'games,': [319], 'main': [321], 'result': [322], 'procedure': [326], 'solve': [328, 353], 'based': [331, 370, 515], 'The': [339], 'latter': [340], 'readily': [341], 'applies': [342], 'satisfying': [347, 404], 'conditions.': [349], 'order': [351], 'arbitrary': [354], 'problems,': [355], 'devise': [357], 'perturbation': [360], 'scheme.': [361], 'key': [363], 'tool': [364], 'use': [367], 'semirings': [369], 'additive': [372], 'groups': [373], 'vectors': [375], 'lexicographically.\r\n\r\nThen,': [377], 'transfer': [379], 'from': [382], 'show': [389, 548, 581], 'existence': [392], 'polynomial-time': [395], 'rule': [397, 429], 'additional': [405], 'assumptions,': [406], 'would': [407], 'provide': [408], 'algorithm': [411, 440, 496], 'thus': [417], 'games.': [421], 'By': [422], 'transferring': [423], 'analysis': [425], 'shadow-vertex': [428], 'Adler,': [431], 'Karp': [432], 'Shamir,': [434], 'obtain': [437], 'time': [448, 569, 593], 'average,': [450], 'assuming': [451], 'distribution': [453], 'satisfies': [457], 'symmetry': [459], 'property.': [460], '\r\n\r\nWe': [461], 'establish': [462], 'counterparts': [464], 'notions': [467], 'basic': [469], 'points': [470], 'edges': [472], 'polyhedron.': [475, 511], 'yields': [477], 'interpretation': [480, 513], 'As': [488], 'case,': [492], 'pivots': [497], 'graph': [501], 'arrangement': [504, 525], 'hyperplanes': [506, 529], 'associated': [507], 'connection': [519], 'cells': [522], 'their': [531], 'tropicalization.\r\n\r\nBuilding': [532], 'up': [533], 'interpretation,': [537], 'algorithmic': [540], 'refinements': [541], 'operation.': [546, 578], 'along': [551], 'edge': [553], 'polyhedron': [557], 'defined': [558], '$m$': [560], 'dimension': [563], '$n$': [564], 'can': [565, 588], 'be': [566, 589], 'done': [567, 590], '$O(n(m+n))$,': [570], 'similar': [573], 'computation': [584], 'reduced': [586], 'costs': [587], 'tropically': [591], '$O(n(m+n))$.': [594]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2619836383', 'counts_by_year': [{'year': 2020, 'cited_by_count': 2}, {'year': 2019, 'cited_by_count': 1}, {'year': 2016, 'cited_by_count': 2}], 'updated_date': '2024-12-10T15:31:57.287054', 'created_date': '2017-06-05'}