just for clarification: the value of matchings already depends on all edges, namely their sum; that is the reason why greedy algorithms may fail to yield the optimal solution. Therefore it would be important to learn more about your cost function or, what the actual problem is.

To me the problem looks like a special case of the quadratic assignment problem; not clear whether it simpler or harder the problem of the question

even if your answer is not what I asked for it is still valuable information related to the topic

very nice; thank you for putting so much effort in answering my question

@fedja let the arguments be regularly spaced in the interval $[-\pi,\pi]$, the y-values in $[-1,1]$

@fedja just take $\lbrace -1,0,1\rbrace$ for the exponential's coefficients and $\lbrace 0,\pi,2\pi\sqrt{2}\rbrace$ for the sine's coeffients; that should suffice for demonstrational purposes

The number of points that are subject to the approximation are about 100 to 500 and the number functions is about 5, which should suffice because the series looks like a fairly smooth function with added high frequency noise of small amplitude and then subjected to truncation to integer values.

@fedja I have added a more detailed descriptionof my specific problem; I hope it helps

yes, indeed now it is clear to me; thanks for clarifying.

I don't quite understand the argument; a circle with radius $\sqrt{2}$ is an ellipse that when centered at $(1,1)$ has distance $0$ to $(0,0)$, or do you by "touching" mean the existence of a common tangent in a common point? Could you please formulate the least squares approximation problem and also the Chebyshev approximation problem for your example and explain why the optimal solution to the latter problem can't be approximated arbitrarily well by solutions to the weighted versions of the least squares problem?

@fedja as my specific problem in the purest sense is "only" to determine a finite set of parameters for which the evaluation of the approximating functions yield minimal maximal error for their evaluation at a discrete set of arguments, I only demand continuity at these arguments. Of course "secondary" concerns like overall continuity and smoothness constraints play an important role. Please feel free to make assumptions about the function space as appropriate for a theoretical discussion of the proposed idea.