# Approximate algorithm to find the minimum score

Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle.

Query: let $v \in P$, approximate/find the minimum value that $f$ could take over all possible configurations of $v$. For e.g., if 4 variables are given $\{x_1,x_2,x_3,x_4\}$, then if we select $v$ of size 2, that means we select a set from the PowerSet of $\{x_1,x_2,x_3,x_4\}$ of size 2 it can be {x_1,x_2} or {x_2,x_3}. [ Max Value function $f$ can take is when $v = \phi$ (thus, size of v = 0 -> No variables selected)

Max Size of $\left | v \right | \leq \frac{3}{4} n$. Here, size represents the number of variables selected from the given $n$ variables.

Brute Force: Enumerate all possibles elements of $PowerSet \ P$, and compute $f(v)$. Note the minimum value of $f$.

Greedy approach: In this method, we increase the size of $v$ by 1 on each iteration.

 Greedy approach for computing minimum value of f
Input:
Given $n$ variables
Function $f$
Output:
Approximate minimum value that $f$ takes
Working:
$minVal = f(v)$ where $v = \phi$
FOR{each $i = 0 to \frac{3}{4}n$}
FOR{each $e \in {Remaining$n-i$variables}$}
$u = v + \{e\}$
$Compute$f(u)$ENDFOR Let variable$e$gives you the minimum value when added to set$
$newVal = f(v+\{e\})$
IF{newVal < minVal}
minVal = newVal
v = v + {e}
ELSE
break
ENDIF
ENDFOR


And I believe that its not differentiable (unsure as how differentiable is defined)! Its quite close to the best feature subset selection, as adding more features might improve classification. Question: 1)Is to come up with an approximate algorithm with a performance ratio value?
2) For the above given Greedy algorithm what would be worst possible performance? Or is it possible to come up with a approximate bound on it in comparison to the optimal solution?

• 1. Can you proof-read your question? Something seems to be missing in the first sentence: the first sentence trails off (and ends with  for no apparent reason). 2. What's meant by the size of $v$? $v$ is a $n$-dimensional vector, right? 3. Do you know anything about the properties of $f$? Is it continuous, differentiable, smooth, etc.? 3. How is $f$ represented? How is it provided to the algorithm? as an oracle? – D.W. Dec 22 '15 at 20:21
• @D.W.: I have updated the question.Do you mind to have a look ? – letsBeePolite Dec 22 '15 at 20:42
• Well, I find the question confusing. You use $v$ both for a $n$-dimensional vector and for a subset of the $n$ variables. Anyway, if $f$ is a function of $n$ variables, what does it mean to minimize $f$ when "selecting" only a subset of the variables? The value of $f$ presumably depends on the values of all $n$ variables, so it's not clear how you plan to evaluate $f$. Perhaps $f$is a function from subsets of $\{1,\dots,n\}$ to $\mathbb{R}$? I think you need to go back to the drawing board to figure out how to formulate your problem mathematically, because right now it makes no sense. – D.W. Dec 22 '15 at 20:47
• Anyway, the availability of algorithms is going to depend on the properties of $f$. In the general case (without using any properties of $f$), you can't do any better than brute force... but if $f$ is known to have some properties (monotone, or something like that) there are known techniques. So I recommend you look at your particular $f$ and see what properties or structure it might have, and use that to improve your question. – D.W. Dec 22 '15 at 20:53