User aaron mavrinac - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T11:08:04Z http://mathoverflow.net/feeds/user/5029 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem Unidentified Combinatorial Problem Aaron Mavrinac 2011-02-28T12:28:51Z 2011-03-02T16:37:36Z <p>Given a (finite, simple, undirected) graph $\mathcal{G} = (V, E)$, an <em>edge binning</em> associates each $e_{ij} \in E$ with one or the other of its vertices $v_i, v_j \in V$. Let $c_i$ be the number of edges associated with vertex $v_i$ in a given edge binning. Find an edge binning such that $\max_{v_i \in V}(c_i)$ is minimized.</p> <p>Is this (or its dual) a well-known problem, or reducible to a well-known problem?</p> <p><strong>Edit:</strong></p> <p>The proper formal problem statement follows (derived from Asahiro 2009), with $d^+(u)$ denoting the outdegree of vertex $u$.</p> <p><em>Minimum Maximum Outdegree</em>: Given a finite, simple, undirected graph $\mathcal{G}= (V, E)$, find an orientation $\Lambda$ of $\mathcal{G}$ that minimizes $\max_{u \in V}[d^+_\Lambda(u)]$.</p> <p>This can equivalently be stated in terms of indegree.</p> <p>Note that Asahiro et al. primarily study the problem involving a weighted graph and weighted outdegree, which is generally NP-hard.</p> http://mathoverflow.net/questions/29279/distance-metric-on-the-unit-sphere-in-r3 Distance metric on the unit sphere in R^3? Aaron Mavrinac 2010-06-23T20:45:13Z 2010-06-24T00:08:07Z <p>Suppose the unit sphere in &#8477;<sup>3</sup> has coordinates (<i>&rho;</i>, <i>&eta;</i>) with <i>&rho;</i> as the "co-latitude" angle (measured from positive <i>z</i>-axis) and <i>&eta;</i> as the "longitude" angle measured from positive <i>x</i>-axis in the <i>xy</i> plane. I am given to understand that the metric tensor is</p> <p><code>$g = \left[\matrix{1 &amp; 0 \\ 0 &amp; \sin^2\rho}\right]$</code></p> <p>and I am further told that this induces a distance metric on the unit sphere.</p> <p>How can I obtain a distance metric <i>d</i>(<i>x</i>, <i>y</i>) from this? I have seen several definitions similar to <a href="http://planetmath.org/encyclopedia/MetricTensor.html" rel="nofollow">this one</a> (see the note), but I am unsure how to actually reduce this to a usable form.</p> <p><b>Disclaimer:</b> Posted by an engineer in over his head.</p> http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem Comment by Aaron Mavrinac Aaron Mavrinac 2011-03-02T16:29:44Z 2011-03-02T16:29:44Z This is also a variation of unrelated parallel machine scheduling, specifically the $P|M_j, |M_j| \leq 2|C_{\max}$ problem (see M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Second Edition, Prentice-Hall, 2002). http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem Comment by Aaron Mavrinac Aaron Mavrinac 2011-03-02T16:26:06Z 2011-03-02T16:26:06Z K. Lee, J. Leung, and M. L. Pinedo, &quot;A Note on Graph Balancing Problems with Restrictions,&quot; Info. Proc. Lett., vol. 110, no. 1, 2009, pp. 24-29. http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem Comment by Aaron Mavrinac Aaron Mavrinac 2011-03-02T16:25:53Z 2011-03-02T16:25:53Z Y. Asahiro, J. Jansson, E. Miyano, H. Ono, and K. Zenmyo, &quot;Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree,&quot; J. Comb. Optim., Nov. 2009, pp. 1-19. http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem Comment by Aaron Mavrinac Aaron Mavrinac 2011-03-02T16:25:38Z 2011-03-02T16:25:38Z Y. Asahiro, E. Miyano, H. Ono, and K. Zenmyo, &quot;Graph Orientation Algorithms To Minimize the Maximum Outdegree,&quot; Int. J. Found. Comput. Sci., vol. 18, 2007, pp. 197-215. http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem Comment by Aaron Mavrinac Aaron Mavrinac 2011-03-02T16:25:17Z 2011-03-02T16:25:17Z V. Venkateswaran, &quot;Minimizing Maximum Indegree,&quot; Disc. Appl. Math., vol. 143, 2004, pp. 374-378. http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem/56893#56893 Comment by Aaron Mavrinac Aaron Mavrinac 2011-02-28T13:18:58Z 2011-02-28T13:18:58Z Oops, that's 2006. http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem/56893#56893 Comment by Aaron Mavrinac Aaron Mavrinac 2011-02-28T13:16:04Z 2011-02-28T13:16:04Z Yes, this is exactly what I mean. I had been looking at digraphs and indigree/outdegree but never stumbled across the &quot;orientations&quot; terminology, which was the key. A quick search turns up a 2008 article by Asahiro et al. entitled &quot;Graph Orientation Algorithms to Minimize the Maximum Outdegree&quot; which will likely help.