As in the title, the problem is as follows:

Given a set ({$h_1, h_2...h_n$},{$p_1, p_2...p_n$},{$c_1, c_2...c_n$}, {$B$})

where: $ n ≤ 30000 $, $1≤c_k≤10000$, $0≤h_k≤1$, $0≤p_k≤1$, $1≤B≤100000$. \begin{array}{ll} \text{maximize} & (h_1i_1+h_2i_2...h_ni_n)*(p_1i_1+p_2i_2...p_ni_n)\\ \text{subject to}& c_1i_1+c_2i_2...c_ni_n \le B \\ \end{array}

I saw it in an ICPC practice set, and I been trying to figure what algorithm/method I need to solve it. It seems to be related to linear programming or convex optimization. I want learn more about the subject, so what I'm looking for the most the most its if someone can identify what type of problem this is and point me to some tutorial or lecture.

Note that input is very large. So the algorithm has to be $O(n)$ or $O(nlog(n))$ and that $i_k$ is a real number and $B, c_k$ are integers.

  • $\begingroup$ did you appreciate my answer? $\endgroup$ – LinAlg Dec 27 '18 at 23:46
  • $\begingroup$ @LinAlg appreciate your effort on the answer, thank you. But honestly I can hardly understand the document, the math is too advanced (I'm computer science). I'll take a look at it again once I finish my math minor in 1-2 years, otherwise I'll ask one of my professor once the semester starts, or maybe you know some other resource. $\endgroup$ – Yumario Dec 29 '18 at 3:24
  • $\begingroup$ @LinAlg Note that this was not an easy problem problem it was problem 'J' 'Mobilization' here and only two teams manage to solve it. $\endgroup$ – Yumario Dec 29 '18 at 3:37
  • $\begingroup$ I have updated my answer to conform it to your background. $\endgroup$ – LinAlg Dec 29 '18 at 13:44

The problem can be summarized as $\max\{ x^TQx : a^Tx \leq b\}$, where $Q$ is not necessarily negative semidefinite. An optimization problem with a quadratic objective and just one linear constraint is easy, since it satisfies strong duality. That can be proven via the S-lemma.

For more information, see these lecture notes or Appendix B.1 of the (free) book Convex Optimization by Boyd and Vandenberghe.

upd As a computer scientist you may be interested in multi-objective swarm optimization (or variants thereof). Your objectives are maximizing $h_1i_1+h_2i_2...h_ni_n$ and $p_1i_1+p_2i_2...p_ni_n$. Among the Pareto optimal solutions, you multiply both quantities and select the solution with the highest outcome.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.