Consider a graph $G(V,E)$. Let degree of each vertex be denoted to $\beta(v) < d$. Maximize the following, where $\beta(v)$ is the only variable for all vertex $v\in V$. $$ \max \sum_{(u,v)\in E} \big((d - \beta(u))*(d-\beta(v)\big)\\ s.t\\ \qquad\\ \sum_{v\in V}\beta(v) = (|V|-W)d\\ \sum_{v\in V}(d-\beta(v))*\beta(v) = |V|W $$ Feel free to post answers with certain assumptions and any help would be truly appreciated.

Thanks in advance!

  • $\begingroup$ I am mainly looking for an answer upto a constant. By which I mean that numerical constants can be ignored $\endgroup$ – Vivek Bagaria Dec 2 '13 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.