{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:40:47Z","timestamp":1725536447049},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642036842"},{"type":"electronic","value":"9783642036859"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_8","type":"book-chapter","created":{"date-parts":[[2009,8,20]],"date-time":"2009-08-20T22:39:51Z","timestamp":1250807991000},"page":"98-110","source":"Crossref","is-referenced-by-count":6,"title":["New Hardness Results for Diophantine Approximation"],"prefix":"10.1007","author":[{"given":"Friedrich","family":"Eisenbrand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Rothvo\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"8_CR1","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.ipl.2006.09.005","volume":"101","author":"W. Chen","year":"2007","unstructured":"Chen, W., Meng, J.: An improved lower bound for approximating shortest integer relation in $l\\sb \\infty$ norm $({\\rm SIR}\\sb \\infty)$ . Information Processing Letters\u00a0101(4), 174\u2013179 (2007)","journal-title":"Information Processing Letters"},{"issue":"2","key":"8_CR2","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1137\/05064148X","volume":"21","author":"M. Conforti","year":"2007","unstructured":"Conforti, M., Di Summa, M., Wolsey, L.A.: The mixing set with flows. SIAM Journal on Discrete Mathematics\u00a021(2), 396\u2013407 (2007) (electronic)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/978-3-540-68891-4_30","volume-title":"Integer Programming and Combinatorial Optimization","author":"M. Conforti","year":"2008","unstructured":"Conforti, M., Summa, M.D., Wolsey, L.A.: The mixing set with divisible capacities. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 435\u2013449. Springer, Heidelberg (2008)"},{"key":"8_CR4","unstructured":"Conforti, M., Zambelli, G.: The mixing set with divisible capacities: a simple approach (manuscript)"},{"issue":"1","key":"8_CR5","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0304-3975(01)00290-0","volume":"285","author":"I. Dinur","year":"2000","unstructured":"Dinur, I.: Approximating ${\\rm SVP}\\sb \\infty$ to within almost-polynomial factors is NP-hard. Theoretical Computer Science\u00a0285(1), 55\u201371 (2000); Algorithms and complexity, Rome (2000)","journal-title":"Theoretical Computer Science"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., Rothvo\u00df, T.: Static-priority realtime-scheduling: Response time computation is NP-hard. In: RTSS 2008 (2008)","DOI":"10.1109\/RTSS.2008.25"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A. Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica\u00a07, 49\u201365 (1987)","journal-title":"Combinatorica"},{"key":"8_CR8","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, 2nd edn. Algorithms and Combinatorics, vol.\u00a02. Springer, Berlin (1993)","edition":"2"},{"issue":"3, Ser. A","key":"8_CR9","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/PL00011430","volume":"90","author":"O. G\u00fcnl\u00fck","year":"2001","unstructured":"G\u00fcnl\u00fck, O., Pochet, Y.: Mixing mixed-integer inequalities. Mathematical Programming. A Publication of the Mathematical Programming Society\u00a090(3, Ser. A), 429\u2013457 (2001)","journal-title":"A Publication of the Mathematical Programming Society"},{"key":"8_CR10","first-page":"22","volume":"389","author":"D.R. Heath-Brown","year":"1988","unstructured":"Heath-Brown, D.R.: The number of primes in a short interval. Journal f\u00fcr die Reine und Angewandte Mathematik\u00a0389, 22\u201363 (1988)","journal-title":"Journal f\u00fcr die Reine und Angewandte Mathematik"},{"issue":"5","key":"8_CR11","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1090\/S0273-0979-1979-14654-8","volume":"1","author":"D.R. Heath-Brown","year":"1979","unstructured":"Heath-Brown, D.R., Iwaniec, H.: On the difference between consecutive primes. American Mathematical Society. Bulletin. New Series\u00a01(5), 758\u2013760 (1979)","journal-title":"American Mathematical Society. Bulletin. New Series"},{"issue":"3","key":"8_CR12","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s004930200019","volume":"22","author":"M. Henk","year":"2002","unstructured":"Henk, M., Weismantel, R.: Diophantine approximations and integer points of cones. Combinatorica\u00a022(3), 401\u2013407 (2002)","journal-title":"Combinatorica"},{"issue":"1","key":"8_CR13","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1145\/322358.322368","volume":"30","author":"R. Kannan","year":"1983","unstructured":"Kannan, R.: Polynomial-time aggregation of integer programming problems. Journal of the Association for Computing Machinery\u00a030(1), 133\u2013145 (1983)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"1","key":"8_CR14","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0214016","volume":"14","author":"J.C. Lagarias","year":"1985","unstructured":"Lagarias, J.C.: The computational complexity of simultaneous Diophantine approximation problems. SIAM Journal on Computing\u00a014(1), 196\u2013209 (1985)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"8_CR15","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra Jr., H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen\u00a0261(4), 515\u2013534 (1982)","journal-title":"Mathematische Annalen"},{"issue":"2","key":"8_CR16","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/0022-0000(78)90044-2","volume":"16","author":"K.L. Manders","year":"1978","unstructured":"Manders, K.L., Adleman, L.: NP-complete decision problems for binary quadratics. Journal of Computer and System Sciences\u00a016(2), 168\u2013184 (1978)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1-3, Ser. B","key":"8_CR17","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s10107-003-0397-3","volume":"98","author":"A.J. Miller","year":"2003","unstructured":"Miller, A.J., Wolsey, L.A.: Tight formulations for some simple mixed integer programs and convex objective integer programs. Mathematical Programming\u00a098(1-3, Ser. B), 73\u201388 (2003); Integer programming, Pittsburgh, PA (2002)","journal-title":"Mathematical Programming"},{"key":"8_CR18","volume-title":"An introduction to the theory of numbers","author":"I. Niven","year":"1991","unstructured":"Niven, I., Zuckerman, H.S., Montgomery, H.L.: An introduction to the theory of numbers, 5th edn. John Wiley & Sons Inc., New York (1991)","edition":"5"},{"key":"8_CR19","series-title":"Springer Series in Operations Research and Financial Engineering","volume-title":"Production planning by mixed integer programming","author":"Y. Pochet","year":"2006","unstructured":"Pochet, Y., Wolsey, L.A.: Production planning by mixed integer programming. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006)"},{"key":"8_CR20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/3-540-61422-2_121","volume-title":"Algorithm Theory - SWAT \u201996","author":"R. Ravi","year":"1996","unstructured":"Ravi, R., Goemans, M.X.: The constrained minimum spanning tree problem (extended abstract). In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 66\u201375. Springer, Heidelberg (1996)"},{"key":"8_CR21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/3-540-61550-4_173","volume-title":"Mathematical Foundations of Computer Science 1996","author":"C. R\u00f6ssner","year":"1996","unstructured":"R\u00f6ssner, C., Seifert, J.P.: Approximating good simultaneous Diophantine approximations is almost NP-hard. In: Penczek, W., Sza\u0142as, A. (eds.) MFCS 1996. LNCS, vol.\u00a01113, pp. 494\u2013505. Springer, Heidelberg (1996)"},{"issue":"1, Ser. A","key":"8_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s10107-007-0140-6","volume":"115","author":"M. Zhao","year":"2008","unstructured":"Zhao, M., de Farias Jr., I.R.: The mixing-MIR set with divisible capacities. Mathematical Programming. A Publication of the Mathematical Programming Society\u00a0115(1, Ser. A), 73\u2013103 (2008)","journal-title":"A Publication of the Mathematical Programming Society"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T23:33:47Z","timestamp":1558481627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}