{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T07:40:11Z","timestamp":1751614811017,"version":"3.41.0"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T00:00:00Z","timestamp":1525651200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T00:00:00Z","timestamp":1525651200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1305054"],"award-info":[{"award-number":["1305054"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s10878-018-0292-8","type":"journal-article","created":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T02:45:42Z","timestamp":1525661142000},"page":"329-345","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On approximating optimal weight \u201cno\u201d-certificates in weighted difference constraint systems"],"prefix":"10.1007","volume":"36","author":[{"given":"Bugra","family":"Caskurlu","sequence":"first","affiliation":[]},{"given":"Matthew","family":"Williamson","sequence":"additional","affiliation":[]},{"given":"K.","family":"Subramani","sequence":"additional","affiliation":[]},{"given":"Vahan","family":"Mkrtchyan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,5,7]]},"reference":[{"key":"292_CR1","doi-asserted-by":"crossref","unstructured":"Anderson M, Williamson M, Subramani K (2018) Empirical analysis of algorithms for the shortest negative cost cycle problem. Discrete Appl Math. Accepted, In Press","DOI":"10.1016\/j.dam.2018.03.055"},{"key":"292_CR2","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. The MIT Press, Cambridge","edition":"3"},{"issue":"6","key":"292_CR3","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C Demtrescu","year":"2004","unstructured":"Demtrescu C, Italiano GF (2004) A new approach to dynamic all pairs shortest paths. J ACM 51(6):968\u2013992","journal-title":"J ACM"},{"key":"292_CR4","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman Company, San Francisco"},{"key":"292_CR5","doi-asserted-by":"crossref","unstructured":"Goel A, Ramakrishnan KG, Kataria D, Logothetis D (2001) Efficient computation of delay-sensitive routes from one source to all destinations. In Proceedings IEEE INFOCOM 2001. Conference on computer communications. Twentieth annual joint conference of the IEEE Computer and Communications Society (Cat. No. 01CH37213), vol\u00a02. pp 854\u2013858 vol 2","DOI":"10.1109\/INFCOM.2001.916276"},{"key":"292_CR6","unstructured":"Han CC, Lin KJ (1989) Job scheduling with temporal distance constraints. Technical report UIUCDCS-R-89-1560, University of Illinois at Urbana-Champaign, Department of Computer Science"},{"issue":"3","key":"292_CR7","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1145\/71021.71026","volume":"23","author":"ST Levi","year":"1989","unstructured":"Levi ST, Tripathi SK, Carson SD, Agrawala AK (1989) The Maruti hard real-time operating system. ACM Spec Interest Group Oper Syst 23(3):90\u2013106","journal-title":"ACM Spec Interest Group Oper Syst"},{"key":"292_CR8","volume-title":"Integer and combinatorial optimization","author":"GL Nemhauser","year":"1999","unstructured":"Nemhauser GL, Wolsey LA (1999) Integer and combinatorial optimization. Wiley, New York"},{"issue":"1","key":"292_CR9","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/j.dam.2017.10.011","volume":"236","author":"JB Orlin","year":"2018","unstructured":"Orlin JB, Subramani K, Wojciechowski P (2018) Randomized algorithms for finding the shortest negative cost cycle in networks. Discrete Appl Math 236(1):387\u2013394","journal-title":"Discrete Appl Math"},{"key":"292_CR10","doi-asserted-by":"crossref","unstructured":"Seshia SA, Lahiri SK, Bryant RE (2003) A hybrid sat-based decision procedure for separation logic with uninterpreted functions. In: DAC, pp 425\u2013430","DOI":"10.1145\/775832.775945"},{"issue":"2","key":"292_CR11","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s10817-009-9139-4","volume":"43","author":"K Subramani","year":"2009","unstructured":"Subramani K (2009) Optimal length resolution refutations of difference constraint systems. J Autom Reason (JAR) 43(2):121\u2013137","journal-title":"J Autom Reason (JAR)"},{"issue":"2","key":"292_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s00165-011-0186-3","volume":"25","author":"K Subramani","year":"2013","unstructured":"Subramani K, Williamson M, Gu X (2013) Improved algorithms for optimal length resolution refutation in difference constraint systems. Form Asp Comput 25(2):319\u2013341","journal-title":"Form Asp Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0292-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0292-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0292-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T07:23:20Z","timestamp":1751613800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0292-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,7]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["292"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0292-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,5,7]]},"assertion":[{"value":"7 May 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}