{"entities":{"Q1758879":{"pageid":1769621,"ns":120,"title":"Item:Q1758879","lastrevid":51598919,"modified":"2026-01-19T00:23:25Z","type":"item","id":"Q1758879","labels":{"en":{"language":"en","value":"Approximating the asymmetric profitable tour"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6108305"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758879$DB39A806-9480-4AF1-807C-47A484FFA542","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5325efe26359ab66548233ababa3eb91d912ed9f","datavalue":{"value":{"text":"Approximating the asymmetric profitable tour","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1758879$E3144B04-A2AD-4996-9176-BE8BB55C7928","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"783c7e9a02d84837348f62fef3689796185414ea","datavalue":{"value":"1269.90094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758879$6783B782-73ED-4DD6-B81B-6B6293E56FB0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7283d424485d2cc41e42e883d01539eccb5b704e","datavalue":{"value":"10.1504/IJMOR.2012.046689","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758879$92772DA6-F26B-4822-826D-3C65B97EEDBB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3136553beb0b82a888f7886c593b713b30b6e508","datavalue":{"value":{"entity-type":"item","numeric-id":325410,"id":"Q325410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758879$CC0D77C8-6CD9-41EA-87C4-8AD3E92F0B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab8f2306ae4617391fc5a72ecaa3a1dcca4e90b7","datavalue":{"value":{"entity-type":"item","numeric-id":1758878,"id":"Q1758878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758879$358D059C-22E1-431B-BF73-5CC4EF79973A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"08904a7410b5f731fa63153720439160d216b374","datavalue":{"value":{"entity-type":"item","numeric-id":548461,"id":"Q548461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758879$D7FF7768-957F-4558-9F07-32650B306FB2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"16d9ed1da0749c54273c05a4ba5499c71e474aeb","datavalue":{"value":{"time":"+2012-11-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1758879$BAC8F7C9-7D95-45CE-90A7-C50574003B92","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4a0f62e1e18d08d4bb7d94626ae673ae43305070","datavalue":{"value":"Summary: We study the version of the asymmetric prize collecting travelling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. In [\\textit{M. Dell'Amico} et al., Int. Trans. Oper. Res. 2, No. 3, 297--308 (1995; Zbl 0860.90121)], the authors defined it as the profitable tour problem (PTP). We present an \\((1 + \\lceil \\log(n)\\rceil )\\)-approximation algorithm for the asymmetric PTP, where \\(n\\) denotes the number of vertices. The algorithm is based on a heuristic for the asymmetric travelling salesman problem by \\textit{A. M. Frieze} et al. [Networks 12, 23--39 (1982; Zbl 0478.90070)], as well as a method to round fractional solutions of a linear programming relaxation to integers (feasible solution for the original problem), represents a directed version of the algorithm for the symmetric PTP by \\textit{D. Bienstock} et al. [Math. Program. 59, No. 3 (A), 413--420 (1993; Zbl 0793.90089)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758879$52E54D43-CC80-43C4-8185-E43D5FF3D473","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758879$2138C52E-D871-4806-BA69-C7EF21EB32AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758879$F1493DA3-217A-45FE-836B-20D49987C07D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f2c0ca49607eb6daaf0dccb650fd8b7dbeb79e20","datavalue":{"value":"6108305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758879$9C196D11-B5F3-4321-97ED-84B4D86330F5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"acc7d7a4bd8473b88155b68342941b3ef357dd51","datavalue":{"value":"asymmetric profitable tour","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758879$33092EA2-798A-42BF-AD0B-874E092C216F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8158c5c90afb9d0e6c5d13942b7fde7a9ef2dcf","datavalue":{"value":"asymmetric prize collecting travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758879$735C25BC-66E7-497E-AE5A-856D615B6A4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"533ed66c7e237697c722dc21b6ca1bb7999c060c","datavalue":{"value":"Held-Karp relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758879$C8602A12-833E-4FD6-BFC6-3934794F721F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32ed692e060ccf56a27267cda08fa34f517b9fca","datavalue":{"value":"discrete optimisation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758879$3D7875C3-A40F-43E7-B308-55536AEC2FBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ddc2790f83291413186a9651d6c4959058d194f","datavalue":{"value":"operations research","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758879$96830396-46BD-4DA2-B31D-B6D32E0B8F0E","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758879$DE0A8C4F-315A-4E27-9CEE-26B617C1CAB0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e743e5eeb1fbe43e4020874f8ee93a16087a995f","datavalue":{"value":"https://doi.org/10.1504/ijmor.2012.046689","type":"string"},"datatype":"url"},"type":"statement","id":"Q1758879$481A785C-3046-4E1E-A867-ED5763CF51D9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4d93f7bac4087550f636e4afa9cf7dda3149dc31","datavalue":{"value":"W1999401924","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758879$81D07D6B-AB34-4A95-AFED-9D1DF0767161","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"335e128776e78466472738fbf80dba56ad04dbc2","datavalue":{"value":{"entity-type":"item","numeric-id":2861509,"id":"Q2861509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6748a7f29de311b678d85ab166afc840331de228","datavalue":{"value":{"amount":"+0.9960877299308776","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1758879$179D9D0E-99E5-4051-AB98-5FD8DC756EBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da631d3e408c53932ba1d231a803b05fb2c76535","datavalue":{"value":{"entity-type":"item","numeric-id":5688010,"id":"Q5688010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1be2c4af2b8e67966b13a521cedc7674373455e7","datavalue":{"value":{"amount":"+0.892841637134552","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1758879$E0F2C35A-6EE4-48C4-B601-532ECC2CA65E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0822b9d004eeb1802569a7aaec226120049d68a","datavalue":{"value":{"entity-type":"item","numeric-id":3066163,"id":"Q3066163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cb3d99e752efc24161f2e68b5b570059ddca31e","datavalue":{"value":{"amount":"+0.8791951537132263","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1758879$780EF12D-AF08-4855-918C-32558E800C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46bda8924b82bc844f944fc731ee6b9f2086c154","datavalue":{"value":{"entity-type":"item","numeric-id":1944387,"id":"Q1944387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10287fadc1002e30bccdb5914dbf8a4b54bb3093","datavalue":{"value":{"amount":"+0.8770027756690979","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1758879$511A2E84-5E7B-4B80-A190-E2A3A810F25C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef6da6925c6c32f2abb143b475e51c6315cd3328","datavalue":{"value":{"entity-type":"item","numeric-id":6167003,"id":"Q6167003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52103f9ce118439302521ef68bf5bb68aea1fae4","datavalue":{"value":{"amount":"+0.8567597270011902","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1758879$BF2A6CDA-2F8F-4B52-B068-406762ABC523","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1758879","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1758879"}}}}}