{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:27:00Z","timestamp":1761596820472},"reference-count":41,"publisher":"Elsevier BV","issue":"2-3","license":[{"start":{"date-parts":[[2004,2,1]],"date-time":"2004-02-01T00:00:00Z","timestamp":1075593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3490,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2004,2]]},"DOI":"10.1016\/s0166-218x(03)00444-x","type":"journal-article","created":{"date-parts":[[2003,9,16]],"date-time":"2003-09-16T22:32:50Z","timestamp":1063751570000},"page":"249-269","source":"Crossref","is-referenced-by-count":7,"title":["On approximability of linear ordering and related NP-optimization problems on graphs"],"prefix":"10.1016","volume":"136","author":[{"given":"Sounaka","family":"Mishra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kripasindhu","family":"Sikdar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(03)00444-X_BIB1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0895480192240226","article-title":"Performance guarantees for the approximation algorithms depending on parametrized triangle inequality","volume":"8","author":"Andreae","year":"1995","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB2","unstructured":"S. Arora, C. Lund, Hardness of approximation, Approximation Algorithms for NP-hard problems, PWS publishing company, 1997 (Chapter 10)."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB3","series-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"Ausiello","year":"1999"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB4","doi-asserted-by":"crossref","unstructured":"A. Backer, D. Geiger, Approximation algorithm for the loop cutset problem, in: Proceedings of the 10th Conference on Uncertainty in artificial Intelligence, Morgan Kaufman, Los Altos, CA, 1994, pp. 167\u2013188.","DOI":"10.1016\/B978-1-55860-332-5.50013-4"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB5","series-title":"ISAAC95, Algorithms and Computation","first-page":"142","article-title":"Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs","volume":"Vol. 1004","author":"Bafna","year":"1995"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB6","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(94)90199-6","article-title":"Approximation algorithms for multidimensional assignment problems with decomposable costs","volume":"49","author":"Bandelt","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB7","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","article-title":"Approximating maximum independent set by excluding subgraphs","volume":"32","author":"Boppana","year":"1992","journal-title":"BIT"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB8","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0024-3795(93)00312-N","article-title":"(0,12,1) matrices which are extreme points of the generalized transitive tournament polytope","volume":"220","author":"Borobia","year":"1995","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB9","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0024-3795(92)90024-5","article-title":"Generalized transitive tournaments and double stochastic matrices","volume":"172","author":"Bruladi","year":"1992","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB10","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF00249646","article-title":"A new heuristic algorithm solving the linear ordering problem","volume":"6","author":"Chanas","year":"1996","journal-title":"Comput. Optim. Appl."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB11","unstructured":"N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem, Technical Report, Graduate School of Industrial Administration, Carnegie\u2013Mellon University, Pittsburg, 1976."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB12","doi-asserted-by":"crossref","unstructured":"P. Crescenzi, V. Kann, R. Silvestri, L. Trevisan, Structures in approximation classes, in: 1st Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science, Vol. 959, Springer, Berlin, 1995, pp. 539\u2013548.","DOI":"10.1007\/BFb0030875"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB13","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","article-title":"Completeness in approximation classes","volume":"93","author":"Crescenzi","year":"1991","journal-title":"Inform. and Comput."},{"issue":"1","key":"10.1016\/S0166-218X(03)00444-X_BIB14","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1006\/inco.2000.3011","article-title":"On weighted vs unweighted versions of combinatorial optimization problems","volume":"167","author":"Crescenzi","year":"2001","journal-title":"Information and Computation"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB15","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0024-3795(79)90171-X","article-title":"On removing a vertex from the assignment polytope","volume":"26","author":"Cruse","year":"1979","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB16","first-page":"15","article-title":"Sur les distributions binaries associees a des distributions ordinales","volume":"69","author":"Dridi","year":"1980","journal-title":"Math. Sci. Humaines"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB17","doi-asserted-by":"crossref","unstructured":"G. Even, J. Noar, B. Schieber, M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs, in: Proceedings of the Fourth MPS Conference on Integer Programming and Combinatorial Optimization (IPCO), University of Copenhagen, Copenhagen, 1995, pp. 14\u201324.","DOI":"10.1007\/3-540-59408-6_38"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB18","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A threshold of logn for approximating set cover","volume":"45","author":"Feige","year":"1998","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB19","doi-asserted-by":"crossref","unstructured":"P. Festa, P.M. Pardalos, M.G.C. Resende, Feedback set problems, AT & T Labs Research Technical Report: 99.2.2, 1999.","DOI":"10.1007\/978-1-4757-3023-4_4"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB20","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322077.322090","article-title":"Strong NP-completeness results","volume":"25","author":"Garey","year":"1978","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB21","series-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB22","doi-asserted-by":"crossref","first-page":"1195","DOI":"10.1287\/opre.32.6.1195","article-title":"A cutting plane algorithm for linear ordering problem","volume":"32","author":"Gr\u00f6tschel","year":"1984","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB23","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/BF01582009","article-title":"On the acyclic subgraph polytope","volume":"33","author":"Gr\u00f6tschel","year":"1985","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB24","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, M. Junger, G. Reinelt, Acyclic subdigraphs and linear orderings: polytopes, facets, and a cutting plane algorithm, in: Graphs and Orders \u2014 the role of graphs in the theory of ordered sets and its applications, Proceedings NATO advanced study institute, Banff, 1984, I. Rival (Ed.), Reidel, Dordrecht, (1985) 217\u2013264.","DOI":"10.1007\/978-94-009-5315-4_7"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB25","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1287\/moor.17.3.727","article-title":"A new lower bound via projection for the quadratic assignment problem","volume":"17","author":"Hadley","year":"1992","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB26","unstructured":"M. M. Halld\u00f3rrson, Approximations via partitioning, Technical Report IS-RR-95-0003F, JAIST, March 1995."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB27","series-title":"Graph Theory","author":"Harary","year":"1969"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB28","doi-asserted-by":"crossref","unstructured":"D.S. Hochbaum, Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, MA, 1997.","DOI":"10.1145\/261342.571216"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB29","unstructured":"V. Kann, On the approximability of NP-complete optimization problems, Ph.D. Thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB30","first-page":"317","article-title":"Polynomially bounded minimization problems that are hard to approximate","volume":"1","author":"Kann","year":"1995","journal-title":"Nordic J. Comput."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB31","doi-asserted-by":"crossref","unstructured":"T. Leighton, S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, in: Proceedings of the 29th Annual Symposium on FOCS, White Plains, New York, 1988, pp. 422\u2013431.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB32","unstructured":"S. Mishra, K. Sikdar, M. Satpathy, On optimizing register spills for eager functional languages, International Conference on Computational Science, ICCS-2001, part- II, Lecture Notes in Computer Science, Vol. 2074, Springer, Berlin, 2001, pp. 128\u2013137."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB33","series-title":"Topics on Tournaments","author":"Moon","year":"1968"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB34","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","article-title":"Vertex packing","volume":"8","author":"Nemhauser","year":"1975","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB35","unstructured":"A. Newman, Approximating the maximum acyclic subgraph, MS Thesis, M.I.T., June 2000."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB36","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0024-3795(94)00063-8","article-title":"On non-{0, 12, 1} extreme points of the transitive tournament polytope","volume":"233","author":"Nutov","year":"1996","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB37","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation, and complexity classes","volume":"43","author":"Papadimitrou","year":"1991","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB38","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","article-title":"Nondeterministic polynomial optimization problems and their applications","volume":"15","author":"Paz","year":"1981","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB39","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF01200760","article-title":"Packing directed circuits fractionally","volume":"15","author":"Seymour","year":"1995","journal-title":"Combinatorica"},{"key":"10.1016\/S0166-218X(03)00444-X_BIB40","unstructured":"L. Trevisan, Reductions and (non)-approximability, Ph.D. Thesis, Computer Science Department, University of Rome, La Sapienza, 1997."},{"key":"10.1016\/S0166-218X(03)00444-X_BIB41","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/BFb0121198","article-title":"On permutations and permutation polytopes","volume":"8","author":"Younger","year":"1978","journal-title":"Math. Programming Stud."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X0300444X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X0300444X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T15:59:49Z","timestamp":1585151989000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X0300444X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,2]]},"references-count":41,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2004,2]]}},"alternative-id":["S0166218X0300444X"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(03)00444-x","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2004,2]]}}}