User aaron mavrinac - MathOverflow

Unidentified Combinatorial Problem

2011-02-28T12:28:51Z

Given a (finite, simple, undirected) graph $\mathcal{G} = (V, E)$, an edge binning 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.

Is this (or its dual) a well-known problem, or reducible to a well-known problem?

Edit:

The proper formal problem statement follows (derived from Asahiro 2009), with $d^+(u)$ denoting the outdegree of vertex $u$.

Minimum Maximum Outdegree: 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)]$.

This can equivalently be stated in terms of indegree.

Note that Asahiro et al. primarily study the problem involving a weighted graph and weighted outdegree, which is generally NP-hard.

Distance metric on the unit sphere in R^3?

2010-06-23T20:45:13Z

Suppose the unit sphere in ℝ³ has coordinates (ρ, η) with ρ as the "co-latitude" angle (measured from positive z-axis) and η as the "longitude" angle measured from positive x-axis in the xy plane. I am given to understand that the metric tensor is

$g = \left[\matrix{1 & 0 \\ 0 & \sin^2\rho}\right]$

and I am further told that this induces a distance metric on the unit sphere.

How can I obtain a distance metric d(x, y) from this? I have seen several definitions similar to this one (see the note), but I am unsure how to actually reduce this to a usable form.

Disclaimer: Posted by an engineer in over his head.

Comment by Aaron Mavrinac

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).

Comment by Aaron Mavrinac

2011-03-02T16:26:06Z

K. Lee, J. Leung, and M. L. Pinedo, "A Note on Graph Balancing Problems with Restrictions," Info. Proc. Lett., vol. 110, no. 1, 2009, pp. 24-29.

Comment by Aaron Mavrinac

2011-03-02T16:25:53Z

Y. Asahiro, J. Jansson, E. Miyano, H. Ono, and K. Zenmyo, "Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree," J. Comb. Optim., Nov. 2009, pp. 1-19.

Comment by Aaron Mavrinac

2011-03-02T16:25:38Z

Y. Asahiro, E. Miyano, H. Ono, and K. Zenmyo, "Graph Orientation Algorithms To Minimize the Maximum Outdegree," Int. J. Found. Comput. Sci., vol. 18, 2007, pp. 197-215.

Comment by Aaron Mavrinac

2011-03-02T16:25:17Z

V. Venkateswaran, "Minimizing Maximum Indegree," Disc. Appl. Math., vol. 143, 2004, pp. 374-378.

Comment by Aaron Mavrinac

2011-02-28T13:18:58Z

Oops, that's 2006.

Comment by Aaron Mavrinac

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 "orientations" terminology, which was the key. A quick search turns up a 2008 article by Asahiro et al. entitled "Graph Orientation Algorithms to Minimize the Maximum Outdegree" which will likely help.