{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:22:48Z","timestamp":1758266568025},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540002253"},{"type":"electronic","value":"9783540362067"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36206-1_25","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T03:23:08Z","timestamp":1187234588000},"page":"277-288","source":"Crossref","is-referenced-by-count":6,"title":["On the Hardness of Approximating Minimum Monopoly Problems"],"prefix":"10.1007","author":[{"given":"S.","family":"Mishra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaikumar","family":"Radhakrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Sivasubramanian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,12,16]]},"reference":[{"key":"25_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/3-540-62592-5_80","volume-title":"Hardness of approximating problems on cubic graphs","author":"P. Alimonti","year":"1997","unstructured":"P. Alimonti AND V. Kann, Hardness of approximating problems on cubic graphs, in Proc. 3rd Italian Conf. on Algorithms and Complexity, LNCS-1203, Springer-Verlag, 1997, 288\u2013298."},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"G Bracha, An o(log n) expected rounds randomised Byzantine generals algorithm. Journal of the ACM, 1987, 910\u2013920.","DOI":"10.1145\/31846.42229"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"U. Feige, A threshold of ln n for approximating set cover, In Proc. ACM Symp. on the Theory of Computing, 1996.","DOI":"10.1145\/237814.237977"},{"key":"25_CR4","unstructured":"P. Flocchini, F. Geurts AND N. Santoro, Dynamic majority in general graphs and chordal rings (Draft) 1997."},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1145\/234782.234783","volume":"27","author":"R. Greenlaw","year":"1995","unstructured":"R. Greenlaw AND R. Petreschi, Cubic graphs, ACM Computing Surveys, vol. 27, 1995, 471\u2013495.","journal-title":"ACM Computing Surveys"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D. S. Hochbaum","year":"1982","unstructured":"D. S. Hochbaum, Effcient bounds for the stable set, vertex cover and set packing problems, Disc. Appl. Math., vol. 6, 1982, 243\u2013254.","journal-title":"Disc. Appl. Math."},{"key":"25_CR7","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02523693","volume":"18","author":"M. Halld\u00f3rsson","year":"1997","unstructured":"M. Halld\u00f3rsson AND J. Radhakrishnan, Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs, Algorithmica, vol. 18, 1997, 145\u2013163.","journal-title":"Algorithmica"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"S. Kutten AND D. Peleg, Fault-local distributed mending. In Proc. 36th IEEE Symp. on Foundations of Computer Science 1995.","DOI":"10.1145\/224964.224967"},{"key":"25_CR9","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L. Lamport","year":"1982","unstructured":"L. Lamport, R. Shostak AND M. Pease, The Byzantine generals problem. ACM Transactions on Programming Languages and systems, vol. 4, 1982, 382\u2013401.","journal-title":"ACM Transactions on Programming Languages and systems"},{"key":"25_CR10","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund AND M. Yannakakis, On the hardness of Approximating minimisation problems. Journal of ACM, vol. 41, 1994, 960\u2013981.","journal-title":"Journal of ACM"},{"key":"25_CR11","unstructured":"D. Peleg, Local majority voting, small coalition and controlling monopolies in graphs: A review. In Proc. of 3rd Colloquium on Structural Information and Communication Complexity, 152\u2013169, 1996."},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Luca Trevisan, Non-approximability Results for Optimization Problems on Bounded Degree Instances. In Proc. of the 33rd ACM STOC, 2001.","DOI":"10.1145\/380752.380839"},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou AND M. Yannakakis, Optimization, Approximation, and Complexity Classes. J. Comput. System Sci., vol. 43, 1991, 425\u2013440.","journal-title":"J. Comput. System Sci."},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0012-365X(88)90226-9","volume":"72","author":"S. Ueno","year":"1988","unstructured":"S. Ueno, Y. Kajtani AND S. Gotoh, On the non-separating independent set problem and feedback set problem for graphs with no vertex exceeding three, Disc. Math., vol. 72, 1988, 355\u2013360.","journal-title":"Disc. Math."},{"key":"25_CR15","unstructured":"V. Vazirani, Approximation Algorithms, Springer, 2001."}],"container-title":["Lecture Notes in Computer Science","FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36206-1_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T00:07:57Z","timestamp":1556755677000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36206-1_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540002253","9783540362067"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-36206-1_25","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}