Can You Solve the Following Minimization Problems?

Revision en10, by Noam527, 2024-05-03 21:59:44

I've spent some time on the following problem, which is quite generic (and is similar to many well-known problems):

You are given $$$2n$$$ pairs of integers $$$(x_i, y_i)$$$, where $$$1 \leq x_i, y_i \leq M$$$. Your goal is to choose exactly $$$n$$$ of them, such that their pointwise sum $$$(X, Y)$$$ (that is, you sum each coordinate on its own), minimizes the cost function $$$f(X, Y)$$$. What is the best time complexity you can achieve, given some properties about the function $$$f$$$?

Since the time complexity can depend on both $$$n$$$ and $$$M$$$, the order in which the best complexity is determined is:

  1. Polynomial in $$$n$$$ and in $$$\log M$$$.

  2. Polynomial in $$$n$$$ and in $$$M$$$.

  3. $$$O(\binom{2n}{n})$$$ (applicable to all of them).

Try to solve each of the following variations, with varying difficulties. This post is purposed for all levels, and I'll try to write solutions that can be understood by all levels (except maybe for the advanced problems).

I'm interested to know if you have any other variations with interesting insights that I can add to here, as I find this topic quite interesting to research.


Problem A. $$$f(X,Y) = X + Y$$$

Solution complexity
Solution
Extra notes (don't read before solution)

Problem B. $$$f$$$ can be any function

Solution complexity
Solution
Extra notes (don't read before solution)

Problem C. $$$f$$$ is monotonic: for each pair of pairs $$$(x_1,y_1), (x_2, y_2)$$$ such that $$$x_1 \leq x_2$$$ and $$$y_1 \leq y_2$$$, you have $$$f(x_1, y_1) \leq f(x_2, y_2)$$$.

Solution complexity
Solution
Extra notes (don't read before solution)

Problem D. $$$f(x,y) = \frac{x}{y}$$$

Solution complexity
Solution
Extra notes (don't read before solution)

Problem E. $$$f(x,y) = xy$$$

Solution complexity
Solution
Extra notes (don't read before solution)

Problem F. $$$f(x,y) = x^2 + y^2$$$

Solution complexity
Solution
Extra notes (don't read before solution)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en12 English Noam527 2024-05-04 19:57:57 3091 Tiny change: '$\alpha = X, \beta = Y$ but this' -> '$\alpha = Y, \beta = X$ but this' (published)
en11 English Noam527 2024-05-04 19:17:43 4558 Tiny change: '$O(n \log nM)$.\n</spo' -> '$O(n \log (nM))$.\n</spo'
en10 English Noam527 2024-05-03 21:59:44 149
en9 English Noam527 2024-05-03 19:50:37 2049 Tiny change: '1 \leq x_2, y_1 \leq y' -> '1 \leq x_2$ and $y_1 \leq y'
en8 English Noam527 2024-05-03 19:22:12 3 Tiny change: 'ze $dp[0][*][*][*] = 0$, e' -> 'ze $dp[0][\*][\*][\*] = 0$, e'
en7 English Noam527 2024-05-03 19:21:35 71
en6 English Noam527 2024-05-03 19:16:37 475 Tiny change: 'on">\n####$O(n^4' -> 'on">\n######$O(n^4'
en5 English Noam527 2024-05-03 18:59:54 119
en4 English Noam527 2024-05-03 18:49:04 438
en3 English Noam527 2024-05-03 18:45:34 1257
en2 English Noam527 2024-05-03 18:31:17 1717 Tiny change: 'n $\log M$' -> 'n $\log M$.\n\n2. Polynomial in $n$ and in $M$.'
en1 English Noam527 2024-05-03 18:16:06 450 Initial revision (saved to drafts)