{"entities":{"Q2336632":{"pageid":2347375,"ns":120,"title":"Item:Q2336632","lastrevid":57314490,"modified":"2026-03-30T09:36:55Z","type":"item","id":"Q2336632","labels":{"en":{"language":"en","value":"Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7131782"}},"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":"Q2336632$71509D19-44F7-47DD-BC7F-598CC2516D5F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b6714fafc615a273af2b9008e5ad82a53d5091c2","datavalue":{"value":{"text":"Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2336632$58DD730C-6D3A-41FD-A0D4-94871ABC8257","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6248ed0ca5681c273444a408114d0d0bb229c69b","datavalue":{"value":"1442.90082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336632$CD373874-B425-4E2E-800E-C533F0D17995","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"27aa8e07af07bc2c17147cdfc0d07dd9b02bec27","datavalue":{"value":"10.1155/2014/679702","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336632$F3678A77-75EF-4A42-89D2-C1655861C419","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$FF6BD4D1-7968-4F74-AD57-F06D9A97D49A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"bb299feb2b87699ac8beef494c52fd2765eaf609","datavalue":{"value":{"entity-type":"item","numeric-id":118601,"id":"Q118601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$571FEA87-1996-4707-921B-37DFF75C8434","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"10393ba55f1a886ba53e75eccd4b56403eff1eb9","datavalue":{"value":{"time":"+2019-11-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2336632$D3E9CDE2-1F95-4753-9143-7BD1EAD8B17A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ea02a7905bd8cede345c8d1026aa4b193c802960","datavalue":{"value":"Summary: This paper addresses a new performance measure for scheduling problems, entitled ``biased tardiness penalty''. We study the approximability of minimum biased tardiness on a single machine, provided that all the due dates are equal. Two heuristic algorithms are developed for this problem, and it is shown that one of them has a worst-case ratio bound of 2. Then, we propose a dynamic programming algorithm and use it to design an FPTAS. The FPTAS is generated by cleaning up some states in the dynamic programming algorithm, and it requires \\(O(n^3 / \\varepsilon)\\) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2336632$0D9CBBA3-C77C-474C-ABB7-003143079208","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336632$291CD7D2-4A94-4605-ADBA-65BFAB5844F5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1feea2fe62cd19d6ccb48931a69517f3d56ef5c4","datavalue":{"value":"7131782","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336632$5F9039EF-CB0F-4D42-8FCF-C29E8F241599","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"80564858302429ae49c62e4ba0278f91823c185d","datavalue":{"value":"Q59054017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336632$6115DA85-AABB-49AC-A632-B8EC8D1ECD70","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":"Q2336632$C6E47A97-1768-486C-8906-1FF9566AED95","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cbd25f1e274471f5546a6927489340a676e64455","datavalue":{"value":"https://doi.org/10.1155/2014/679702","type":"string"},"datatype":"url"},"type":"statement","id":"Q2336632$649E79E7-CF78-4DCE-9581-C66239221583","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7c397ab044ffc51854418412f88943b180a7011e","datavalue":{"value":"W1975123132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336632$50BE2660-B291-486C-9D4B-CFD51BADD1F1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"90324e6e93bcf2fdec5e5778fdf491c93fa57a58","datavalue":{"value":{"entity-type":"item","numeric-id":4124332,"id":"Q4124332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$CA9FE43C-1614-4639-B0B6-DD9C3BB46431","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4ae368f5009736f85a97fcebaf4630774830353","datavalue":{"value":{"entity-type":"item","numeric-id":4124328,"id":"Q4124328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$8571E4D1-BE9F-4B36-86CE-2381C34FE02C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1a09830a1d6a5dd43289e798100889350216445","datavalue":{"value":{"entity-type":"item","numeric-id":2368997,"id":"Q2368997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$887DD2CA-0DE9-43E3-8B49-BB43AD586740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f77b75439ccd17584810072b951a45e72240dc6","datavalue":{"value":{"entity-type":"item","numeric-id":1772846,"id":"Q1772846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$7A649709-0A44-4D5C-8DB4-B44A827EF48A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b102e902ac92d44baf01d3855a9f6002e1512056","datavalue":{"value":{"entity-type":"item","numeric-id":5323068,"id":"Q5323068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$FB07A00E-93BC-4AE9-9C2D-A820DDC8722D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44c4d8aa79e4bb7bacb61f3abd1a6642d3e82b20","datavalue":{"value":{"entity-type":"item","numeric-id":4034337,"id":"Q4034337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$4CEBE7CF-D90D-4709-B105-72DED7447CA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565dd9f994f9ad40804f24534c6e2ebb318c8a1d","datavalue":{"value":{"entity-type":"item","numeric-id":5576138,"id":"Q5576138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$F9F1B81D-B825-4C7E-80EC-74FCDD0A0494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c777262c143ede91b8a569edecdb9a4c5721273","datavalue":{"value":{"entity-type":"item","numeric-id":861263,"id":"Q861263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$9D076DDC-B763-4D2A-8161-298983E0A4B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8550f777bbb0372f08c5179ea5a282bcdd96211b","datavalue":{"value":{"entity-type":"item","numeric-id":708332,"id":"Q708332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$1FB86C63-0BDB-4BB6-BAC0-A586FC57F83F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b153e6a92a65a41501aa0a1819873f5d9ce7b9d9","datavalue":{"value":{"entity-type":"item","numeric-id":3200872,"id":"Q3200872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$FF2668A8-5E28-4FD7-92F6-C90BE3A697EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a243c05cb7445ab5c0df82ffa9b8f4375460f853","datavalue":{"value":{"entity-type":"item","numeric-id":1839195,"id":"Q1839195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$59881C96-8CFC-4D8A-A4C1-4F5B43E52121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932359ee69525a93ed0526ba572384360cc69bea","datavalue":{"value":{"entity-type":"item","numeric-id":958114,"id":"Q958114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$37E548F1-B327-4878-953B-97646BC013E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"609f21fd8e322ee758aa74606240f0dfff932325","datavalue":{"value":{"entity-type":"item","numeric-id":1904613,"id":"Q1904613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$177A3019-26EC-4B4F-A47A-3D1A221BCE11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e85787f169176bffdb7f9ac127b363632cedafce","datavalue":{"value":{"entity-type":"item","numeric-id":5920391,"id":"Q5920391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$DAD2BC8A-354B-4431-AA40-E36C2D0FE99E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a82d1ce580c2b0418b7e5e59ba7eb57e9aecaa7","datavalue":{"value":{"entity-type":"item","numeric-id":1850992,"id":"Q1850992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$68A823A1-4756-425A-8DCD-41CC0E1EBC6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b916828114586c907ab9703174b17d58bf1c2d1","datavalue":{"value":{"entity-type":"item","numeric-id":4114965,"id":"Q4114965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$4DE8040E-308A-40B6-95FD-F2B426FE7B53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d14e38710bb7c7255e16b5029eb9bff7affd17fc","datavalue":{"value":{"entity-type":"item","numeric-id":2434268,"id":"Q2434268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$EBC0AD9E-EB8B-4691-98D1-311196E70207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e2a529b19eb431e5627134dad07655f5261df16","datavalue":{"value":{"entity-type":"item","numeric-id":1038382,"id":"Q1038382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$848936BA-296E-45EF-B2B6-BAFBFA58A9A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df73a6dd4dbd3c6650898af08b743df7eaf8f3e7","datavalue":{"value":{"entity-type":"item","numeric-id":2268520,"id":"Q2268520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$082A228F-77C4-49AD-A2A4-BF8714D72F99","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"e6a05ec2efd6d9653d835c3f2b8201d16c8dcfed","datavalue":{"value":"journals/jam/MoslehiK14","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2336632$8AF94437-EBB7-443B-BB79-51687A49305B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89f4978118837a1774ad75d907d99993d0b93550","datavalue":{"value":{"entity-type":"item","numeric-id":2368997,"id":"Q2368997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48d0b0fd451773e78bb1364e84c9f6fd7bf8a2a6","datavalue":{"value":{"amount":"+0.8166557550430298","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":"Q2336632$92E361D2-9B14-4040-9955-186AE51A3397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a844b83d8139cd1895aee78956ed3696ac36724e","datavalue":{"value":{"entity-type":"item","numeric-id":861263,"id":"Q861263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82bc06a90ccfe802c384968fa5aec33ec322971f","datavalue":{"value":{"amount":"+0.8133841156959534","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":"Q2336632$720BCC58-DDA8-451A-BBCA-8165C1183076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78abe2e9bf7e86e62cbe0ddd2804270bb6bb1ac2","datavalue":{"value":{"entity-type":"item","numeric-id":5309698,"id":"Q5309698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe0a7ece6e79df1a2377b8ac5b18af0bbb3ecdda","datavalue":{"value":{"amount":"+0.8097094297409058","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":"Q2336632$38CEEF64-478A-4815-8C26-A45E421E594A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34f22e0efbeaf719eb57d3212e6dd68ade822ee5","datavalue":{"value":{"entity-type":"item","numeric-id":2628167,"id":"Q2628167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7026353fd11edba5c3d34c135bcd80cad3881d48","datavalue":{"value":{"amount":"+0.803379237651825","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":"Q2336632$D7A084DD-9389-4E34-8EC1-DFC7B80B33B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aba82cb34b73fcc53a97c479b02ce5aee46faad7","datavalue":{"value":{"entity-type":"item","numeric-id":5323068,"id":"Q5323068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90a283ef2f49904385c2926d6404584f6a639675","datavalue":{"value":{"amount":"+0.7996714115142822","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":"Q2336632$E5A24B94-A5A2-4867-97D1-C71C6790B677","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"daf5f856a5d861312ad309ab567540337a5f61d6","datavalue":{"value":{"entity-type":"item","numeric-id":57050,"id":"Q57050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2336632$67CEFA5E-1CE0-4976-AA66-DB8FFBA85534","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2336632","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2336632"}}}}}