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.



Unidentified Combinatorial Problem
This problem is equivalent to the *graph orientation problem* also known as the *graph balancing problem*. One is given an undirected graph and has to give an orientation of the edges which minimizes the maximum out-degree. If this value is $k$, then the graph is called $k$-orientable. Here are some articles on the topic ["Graph Orientation Algorithms to Minimize the Maximum Outdegree"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.3168), and ["A note on graph balancing problems with restrictions"](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V0F-4XC57MY-1&_user=10&_coverDate=12%2F01%2F2009&_rdoc=1&_fmt=high&_orig=gateway&_origin=gateway&_sort=d&_docanchor=&view=c&_searchStrId=1658729844&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=b4bf2d7406f62116349beae9938fe3b2&searchtype=a).


