1
$\begingroup$

Are there any examples where you take a problem for the unweighted case and reduce it to the weighted case? (Not the other way around).

My objective is to do something similar to the following: If the unweighted case cannot be approximated better than say $O(n^3)$ where $n$ is the number of nodes in the graph; I want a reduction that says you if you can do the weighted variant with $O(n^k))$, then you can do the unweighted one with $O(n^{k-c})$ and thus you can't do the weighted one with a ratio better than $O(n^{3+c})$.

PS: Sorry for being vague here. I haven't asked too many questions in StackExchange. So, I am not sure how exactly it works.

I searched around for this; everything I can find is a reduction from the weighted case to the unweighted case.

I also do not want weights to be assigned as 1 for the reduction as I want c to be some useful number.

Improve this question
$\endgroup$
2
  • $\begingroup$ Well, there are problems whose unweighted versions can be approximated (in poly time) with much better approximation ratios than the weighted versions. But I don't know of any such results that are shown via the kind of reduction you ask for. $\endgroup$
    – Neal Young
    Oct 20, 2022 at 0:52
  • $\begingroup$ Typically, for most problems in discrete optimization, the approximation for weighted is similar to that of unweighted even though it is sometimes more difficulty to handle the weighted case. There are only a few "natural" examples that I am aware of where the weighted case is provably harder than the unweighted --- there must be something specific about the problem structure that allows this. Given this, the type of reduction you are looking for is perhaps not so easy to find. $\endgroup$
    – Chandra Chekuri
    Oct 20, 2022 at 17:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.