Timeline for How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 21, 2023 at 20:19 | comment | added | Display name | I have abandoned this function and moved onto a simpler one, sorry for wasting your time. | |
| Jul 21, 2023 at 20:19 | vote | accept | Display name | ||
| Jul 14, 2023 at 1:12 | comment | added | Display name | This seems like too many constraints to find a nice constant factor approximation in polynomial time, I was hoping for a trick like we have for cut norm since the $\infty \to 1$ norm has very nice algorithms: web.math.princeton.edu/~naor/homepage%20files/cutnorm.pdf. I will see if anyone posts a better answer, and if not then I guess the only option is to use this brute force conversion, relax to linear programming, round the solution, and find an estimate on the rounding. Very routine, but I assume it's gonna produce a bad estimate (could be worse than constant factor). | |
| Jul 13, 2023 at 16:53 | history | edited | RobPratt | CC BY-SA 4.0 |
added 128 characters in body
|
| Jul 13, 2023 at 16:10 | history | answered | RobPratt | CC BY-SA 4.0 |