{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T13:21:32Z","timestamp":1709817692146},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2011,4]]},"abstract":" We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. This problem is closely related to the job scheduling on parallel machines, called the machine covering problem, where its goal is to assign jobs to parallel machines such that each machine is covered as much as possible. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 \u2013 \u03b5 for any constant \u03b5 > 0 in polynomial time unless P = NP , even if all edge weights belong to {1, 2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time [Formula: see text]-approximation algorithm for MAXMINO where wmax<\/jats:sub> and wmin<\/jats:sub> denote the maximum and minimum weights among all the input edges. Furthermore, we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than wmin<\/jats:sub> is at most logarithmic in the number of vertices. Finally, we show that MAXMINO is solvable in polynomial time if the input is a cactus graph. <\/jats:p>","DOI":"10.1142\/s0129054111008246","type":"journal-article","created":{"date-parts":[[2011,4,18]],"date-time":"2011-04-18T06:11:52Z","timestamp":1303107112000},"page":"583-601","source":"Crossref","is-referenced-by-count":8,"title":["GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE"],"prefix":"10.1142","volume":"22","author":[{"given":"YUICHI","family":"ASAHIRO","sequence":"first","affiliation":[{"name":"Department of Information Science, Kyushu Sangyo University, Higashi-ku, Fukuoka 813-8503, Japan"}]},{"given":"JESPER","family":"JANSSON","sequence":"additional","affiliation":[{"name":"Ochanomizu University, Bunkyo-ku, Tokyo 112-8610, Japan"}]},{"given":"EIJI","family":"MIYANO","sequence":"additional","affiliation":[{"name":"Department of Systems Design and Informatics, Kyushu Institute of Technology, Iizuka, Fukuoka 820-8502, Japan"}]},{"given":"HIROTAKA","family":"ONO","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kyushu University, Nishi-ku, Fukuoka 819-0395, Japan"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107004644"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/1120680.1120683"},{"key":"rf7","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"1990"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.74"},{"key":"rf11","volume-title":"Computers and Intractability \u2013 A Guide to the Theory of NP-Completeness","author":"Garey M.","year":"1979"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(78)90562-4"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"rf15","volume-title":"Handbook of Graph Theory","author":"Gross J. L.","year":"2004"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1137\/0211023"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.07.007"},{"key":"rf22","first-page":"161","volume":"63","author":"Wimer T. V.","journal-title":"Congressue Numerantium"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(96)00055-7"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054111008246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:23:15Z","timestamp":1565176995000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054111008246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4]]},"references-count":13,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2011,4]]}},"alternative-id":["10.1142\/S0129054111008246"],"URL":"https:\/\/doi.org\/10.1142\/s0129054111008246","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4]]}}}