{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q2336632","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q2336632","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q2336632","kernelVersion":"v1","immutable":true,"modified":"2026-03-30T09:36:55Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q2336632","name":"Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty","headline":"Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty","description":"scientific article; zbMATH DE number 7131782","url":"https://portal.mardi4nfdi.de/entity/Q2336632","datePublished":"2019-11-19","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q1787138"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q118601"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1155/2014/679702","url":"https://doi.org/10.1155/2014/679702"},"sameAs":["https://doi.org/10.1155/2014/679702"],"comment":"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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q4124332"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4124328"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2368997"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1772846"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5323068"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4034337"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5576138"},{"@id":"https://portal.mardi4nfdi.de/entity/Q861263"},{"@id":"https://portal.mardi4nfdi.de/entity/Q708332"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3200872"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1839195"},{"@id":"https://portal.mardi4nfdi.de/entity/Q958114"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1904613"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5920391"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1850992"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4114965"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2434268"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1038382"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2268520"}]},"provenance":{"prov:generatedAtTime":"2026-03-30T09:36:55Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}