Rundung, um die Summe der Fehler in paarweisen Abständen zu minimieren

Was ist über die Komplexität des folgenden Problems bekannt:

Gegeben: rationale Zahlen . $x_1 < x_2 < \dotso < x_n$
Ausgabe: Ganzzahlen . $y_1 \le y_2 \le \dotso \le y_n$
Ziel: minimiere wobei $\sum_{1 \leq i < j \leq n} e (i, j),$ $\sum_{1 \le i < j \le n} e(i,j),$ $e (i, j) = | (y_{j} - y_{i}) - (x_{j} - x_{i}) | .$ $e(i,j) = | (y_j-y_i) - (x_j-x_i)|.$

Das heißt, wir möchten die rationalen Zahlen auf ganze Zahlen runden, um die Summe der Fehler in paarweisen Abständen zu minimieren. Für jedes Paar möchten wir den gerundeten Abstand so nahe wie möglich am wahren Abstand . $i, j$ $y_j-y_i$ $x_j-x_i$

Motivation: Eine langweilige U-Bahn-Fahrt und ein Plakat, auf dem die "Standorte" der Bahnhöfe in einer Minute Fahrzeit dargestellt sind. Hier minimieren wir den Fehler, den Menschen machen, wenn sie das Poster verwenden, um die Reisezeit zwischen den Stationen und , wobei der Durchschnitt über alle Paare . $i$ $j$ $i<j$

Straßenkarte

(Quelle)

Zum Beispiel können wir hier die folgenden Näherungen der paarweisen Abstände zwischen den vier Stationen lesen (wobei der Kürze halber A, B, C, D verwendet wird):

A – B ≤ 1 Minute, B – C ≤ 2 Minuten, C – D ≤ 2 Minuten
A – C ≈ 3 Minuten, B – D ≈ 4 Minuten
A – D ≈ 5 Minuten

Ist das die bestmögliche Annäherung? Wenn Sie die tatsächlichen Reisezeiten kennen, könnten Sie eine bessere Lösung finden?

Anfangs klang dies wie eine einfache Übung in dynamischer Programmierung, aber jetzt scheint es, dass ein gewisses Maß an tatsächlichem Denken erforderlich ist.

Kennt jemand dieses Problem? Oder sehen Sie einen cleveren Algorithmus, um das Problem zu lösen?

Bearbeiten: Es gibt einige natürliche Varianten der Frage, die in den Kommentaren erwähnt wurden; Geben wir ihnen einige Namen:

Boden- / Deckenversion : Es ist erforderlich, dass für alle . $y_i \in \{ \lfloor x_i \rfloor, \lceil x_i \rceil \}$ $i$
Ganzzahlige Version: Es ist ausreichend, dass für alle . $y_i \in \mathbb{Z}$ $i$
monotone Version: es ist erforderlich, dass . $y_1 \le y_2 \le \dotso \le y_n$
nicht monotone Version: wir können für . $y_i > y_j$ $i < j$

Die ursprüngliche Frage berücksichtigt die monotone Integer-Version. Antworten zu diesen Versionen sind jedoch willkommen.

ds.algorithms reference-request optimization Jukka Suomela
quelle

Funktioniert der DP für den Fall, dass Sie sich nur um benachbarte Messungen kümmern?

Suresh Venkat

@SureshVenkat: Tatsächlich wird das Problem in diesem Fall sehr einfach: Sie wählen einfach den besten Integralabstand für jedes . Das heißt, Sie können jedes unabhängig voneinander minimieren .

y_{i} - y_{i - 1}

$y_i - y_{i-1}$

i

$i$

e (i - 1, i)

$e(i-1,i)$

Jukka Suomela

Dieser Bericht von Estie Arkin scheint verwandt zu sein: ams.sunysb.edu/~estie/papers/beautification.pdf Es ist bewiesen, dass die Minimierung der Anzahl unterschiedlicher Zwischenpunktabstände in der Ausgabe NP-schwer ist. Dies ist nicht die Gesamtsumme der Verschiebungen, wie in diesen Fragen dargestellt, aber die Härte-Gadgets im Bericht könnten möglicherweise einen Härtegewinn für dieses Problem anzeigen.

val

Ich habe das Gefühl, dass dieses Problem mit bekannten Techniken sicher lösbar sein sollte. Mal sehen, ob das Kopfgeld ausreicht, um die Leute zur Lösung dieses Problems zu motivieren. :)

Jukka Suomela

@vzn: Ich interessiere mich für die rechnerische Komplexität dieses Problems. Wenn Sie nachweisen können, dass es einen lokalen Suchansatz für Polynome gibt, mit dem Sie garantiert das globale Optimum finden, liegt die Prämie bei Ihnen.

Jukka Suomela

Antworten:

OKAY. Der DP-Algorithmus scheint unnötig kompliziert zu sein. Nach dem Lesen von Kommentaren denke ich, dass dies die monotone Version des Problems lösen könnte (aber ich habe nicht jedes Detail überprüft).

, dass jedes , wobei der integrale Teil ist, der gebrochene Teil ist. Angenommen, ist auf gerundet , wobei eine nichtnegative ganze Zahl ist (natürlich kann im Allgemeinen negativ sein, aber wir können immer so verschieben, dass das kleinste 0 ist). $x_i = \lfloor x_i\rfloor +\{x_i\}$ $\lfloor x_i\rfloor$ $\{x_i\}$ $x_i$ $\lfloor x_i \rfloor + v_i$ $v_i$ $v_i$ $v_i$

Betrachten Sie nun die Kosten für ein Paar , wenn Sie diese Rundung durchführen. Die Kosten sollten sein $x_i$ $x_j$

| | v_{i} - v_{j} + ⌊ x_{i} ⌋ - ⌊ x_{j} ⌋ | - | {x_{i}} - {x_{j}} + ⌊ x_{i} ⌋ - ⌊ x_{j} ⌋ | |

$||v_i-v_j+ \lfloor x_i\rfloor - \lfloor x_j\rfloor| - |\{x_i\}-\{x_j\} + \lfloor x_i\rfloor - \lfloor x_j\rfloor||$

Der Ausdruck ist wegen der absoluten Werte kompliziert. Beachten Sie jedoch, dass wir Monotonie haben, sodass die Dinge in den beiden inneren absoluten Werten das gleiche Zeichen haben sollten. Da wir einen äußeren absoluten Wert haben, ist es wirklich egal, was dieses Zeichen ist, der Ausdruck vereinfacht sich nur

| v_{i} - v_{j} - ({x_{i}} - {x_{j}}) |

$|v_i-v_j - (\{x_i\} - \{x_j\})|$

Von nun an gehen wir nicht mehr davon aus, dass die Lösung monoton ist, sondern ändern stattdessen das Ziel, die Summe des obigen Terms für alle Paare zu minimieren. Wenn die Lösung für dieses Problem monoton ist, ist es natürlich auch die optimale Lösung für die monotone Version. (Stellen Sie sich das vor: Das ursprüngliche Problem hat eine unendliche Strafe, wenn die Lösung nicht monoton ist. Das neue Problem hat eine geringere Strafe. Wenn eine monotone Lösung auch in der neuen Version gewinnt, muss es die Lösung der monotonen Version sein.)

Nun möchten wir beweisen, dass wir in der optimalen Lösung haben müssen , wenn . $\{x_i\} > \{x_j\}$ $v_i \ge v_j$

Angenommen, dies ist nicht wahr, wir haben ein Paar aber . Wir werden zeigen, dass die Lösung strikt besser wird, wenn wir tauschen . $\{x_i\} > \{x_j\}$ $v_i < v_j$ $v_i$ $v_j$

Zuerst vergleichen wir den Ausdruck zwischen und , hier ist es wirklich klar, dass das Tauschen strikt besser ist, da in der Nicht-Tausch-Version und das gleiche Vorzeichen haben, das Absolute value ist die Summe der beiden absoluten Werte. $i$ $j$ $v_i-v_j$ $\{x_j\}-\{x_i\}$

Nun vergleichen wir für jedes die Summe der Paare und $k$ $(i,k)$ . Das heißt, wir müssen vergleichen $(j,k)$

und $|v_i-v_k-(\{x_i\}-\{x_k\})|+|v_j-v_k-(\{x_j\}-\{x_k\})|$ . $|v_j-v_k-(\{x_i\}-\{x_k\})|+|v_i-v_k-(\{x_j\}-\{x_k\})|$

Verwenden Sie , , , , um die vier Terme innerhalb des Absolutwerts zu bezeichnen. Es ist klar, dass . Auch ist klar, dass . Durch die Konvexität des Absolutwertes wissen wir $A$ $B$ $C$ $D$ $A+B = C+D$ $|A-B| \ge |C-D|$ $|A|+|B| \ge |C|+|D|$ . Nimm die Summe über alle $x_k$ wir wissen tauschen kann nur besser sein.

Beachten Sie, dass wir jetzt bereits eine Lösung für die monotone Boden- / Deckenversion haben: Es muss eine Schwelle geben, wenn größer ist, immer auf- und abrunden , wenn es kleiner ist, immer auf- und abrunden nach unten, während die Lösungsqualität nur von der Anzahl abhängt. Wir führen alle diese Lösungen auf und wählen die mit der kleinsten Zielfunktion aus. (Alle diese Lösungen sind notwendigerweise monoton). $\{x_i\}$

Zum Schluss möchten wir noch auf die monotone Integer-Version des Problems eingehen. Wir können tatsächlich nachweisen, dass die optimale Lösung mit der monotonen Boden- / Deckenversion identisch ist.

$v_i$ $x_i$ $v_i$ $0,1,2,...,\max\{v_i\}$ $k$ $v_i > k$ $v_i = v_i-1$ . Es ist leicht zu erkennen, dass sich die Zielfunktion immer verbessert (im Grunde genommen, weil ). $|\{x_i\}-\{x_j\}| < 1$

Nun wollen wir beweisen, dass der Durchschnitt von in Gruppe mindestens der Durchschnitt von in Gruppe plus . Wenn dies nicht zutrifft, sei einfach $\{x_i\}$ $k+1$ $\{x_i\}$ $k$ $1/2$ $v_i = v_i-1$ für alle , die Berechnung zeigt erneut, dass sich die Zielfunktion verbessert. $v_i > k$

Da der Durchschnitt von im Bereich , gibt es tatsächlich höchstens zwei Gruppen, was der Boden- / Deckenversion entspricht. $\{x_i\}$ $[0,1)$

Rong Ge
quelle

Nur ein ausführlicher Kommentar ... (vielleicht trivial und / oder falsch :)

Wenn und das am wenigsten verbreitete Vielfache von , können wir die loswerden: . $x_i = a_i / b_i$ $M$ $b_i$ $x'_i = M*x_i$

Wenn (Boden, Ceil-Beschränkung), können wir die binären Variablen , um Verwendung seines Abstands von ( oder $y_i \in \{ \lceil x_i \rceil, \lfloor x_i \rfloor \}$ $v_i$ $y'_i$ $x'_i$ $L_i = x'_i - M*\lfloor x_i \rfloor$ $R_i = x'_i - M*\lceil x_i \rceil$ ):

$y'_i = x'_i + L_i * v_i + R_i * (1 - v_i) = x'_i + (L_i - R_i)*v_i + R_i = x'_i + D_i *v_i + R_i$

Und das ursprüngliche Problem sollte (?!?) Gleichbedeutend sein mit dem Finden des : $v_i$

$\sum_{1 \le i < j \leq n} | D_i * v_i - D_j * v_j |$

mit $v_i \in \{0,1\}, D_i \in \mathbb{Z}$

Marzio De Biasi
quelle

Erweitern Sie Ihre letzte Summe mit der obigen Idee error fn. Könnte gezeigt werden, dass das Optimum tatsächlich nur die Wahl ist, bei der jede binäre Variable floor / ceil näher an ? Damit bleibt nur der Fall, wie für in der Form gerundet wird, wobei eine ganze Zahl ist.

e^{'} (i, j)

$e'(i,j)$

x_{n}

$x_n$

x_{n}

$x_n$

m_{n} + \frac{1}{2}

$m_n + {1 \over 2}$

m

$m$

VZN

@vzn: Ich denke das ist ein Gegenbeispiel. Wenn wir mit den Rundungskriterien runden , erhalten wir mit einem Fehler von , aber mit einem Fehler von (das Ergebnis ist dasselbe, wenn Wir eliminieren die mit dem LCM multiplizierten Rationen.

(0, 1.4, 8.7)

$(0, 1.4, 8.7)$

x_{i}

$x_i$

(0, 1, 9)

$(0, 1, 9)$

1.4

$1.4$

(0, 2, 9)

$(0,2,9)$

1.2

$1.2$

Marzio De Biasi

ok doch neue idee. Betrachte noch einmal . Erweitern Sie die Summe. es wird sich auf viele Terme mit und auch reduzieren . aber letztere ist gleich ! daher reduziert es sich auf ein Problem in Form der Minimierung von wobei ein 0/1- Zeilenvektor und ein konstanter Spaltenvektor ist . wahr? dann ist das trivial, und wählen Sie einfach das so, dass es 1 ist, wenn das entsprechende Element in negativ ist, und 0, wenn es positiv ist .... QED?

e^{'} (i, j)

$e'(i,j)$

v_{i}

$v_i$

v_{i}^{2}

$v_i^2$

v_{i}

$v_i$

X * D

$X*D$

X

$X$

D

$D$

X

$X$

D

$D$

VZN

@vzn: Wenn Sie den , um die Absolutwertfunktion zu eliminieren, erhalten Sie Terme wie ; Wie gehst du mit ihnen bei der Minimierung um?

((y_{i}^{'} - y_{j}^{'}) - (x_{i}^{'} - x_{j}^{'}))^{2}

$((y'_i - y'_j) - (x'_i - x'_j))^2$

- 2 * D_{i} * D_{j} * v_{i} * v_{j}

$- 2*D_i * D_j * v_i * v_j$

Marzio De Biasi

Hoppla! Sie haben geantwortet, bevor ich die Gelegenheit hatte, diesen Kommentar zu löschen, nachdem mir klar wurde, dass es sich trotzdem um ein fast lineares Matrixoptimierungsproblem handelt. auch mit einem Term wobei ein Spaltenvektor ist ...?

V * V^{T}

$V * V^T$

V

$V$

VZN

Noch ein erweiterter Kommentar ... Könnte falsch sein.

Ich denke auch über den Fall mit Boden- / Deckenbeschränkungen nach und versuche, ihn mit dynamischer Programmierung zu lösen (ich kann nicht, aber vielleicht funktioniert es, wenn der gemeinsame Teiler klein ist).

Sei der Bruchteil von , betrachten wir die Dinge vom kleinsten bis zum größten. Angenommen, die größte ist , und weil wir dynamische Programmierung betreiben, wissen wir bereits "etwas" (ich werde erklären, was dies ist) über die optimale Lösung für alles andere außer . $\{x_i\}$ $x_i$ $\{x_i\}$ $\{x_k\}$ $x_k$

Betrachten Sie nun den Unterschied in der Zielfunktion, wenn wir auf- oder abrunden. Wenn ursprünglich etwas aufgerundet ist, dann ist die Differenz einfach 1 (nicht wirklich sorgfältig geprüft, aber es scheint so, als ob dies der Fall ist, ist es wirklich wichtig, dass unabhängig davon, ob links oder rechts von , die Differenz ist immer gleich); Wenn ursprünglich etwas abgerundet ist, beträgt die Differenz . Also: Wir wissen, welche Entscheidung wir treffen sollen, wenn die folgenden drei Größen bekannt sind: $x_k$ $x_i$ $x_i$ $x_k$ $x_i$ $2\{x_k\}-2\{x_i\}-1$

Wie viele Dinge sind aufgerundet
Wie viele Dinge sind abgerundet
Was ist die Summe von unter den , die abgerundet sind? $\{x_i\}$ $x_i$

OK, 1 und 2 sind im Wesentlichen gleich, wir können f [N, Ndown, Sdown] die optimale Lösung für die ersten N Punkte sein lassen (wenn die Punkte in aufsteigender Reihenfolge von sortiert sind ), die Anzahl von ‚s abgerundet ist Ndown, und die Summe von für diejenigen , die abgerundet sind , ist Sdown. Dann ist es nicht schwer zu schreiben, wie man von f [N-1] nach f [N] geht. $\{x_i\}$ $x_i$ $\{x_i\}$

Das Problem ist natürlich, dass Sdown exponentiell viele Werte haben kann. Aber es funktioniert, wenn entweder der gemeinsame Divisor klein ist, oder wir können alles zuerst auf einen Gitterpunkt runden und ein FPTAS erhalten (wenn das obige dynamische Programm korrekt ist ...)

Rong Ge
quelle

Ich habe gerade den Kommentar von @Marzio De Biasi bemerkt. Mit dieser Zielfunktion ist es viel einfacher, über diese dynamische Programmierung nachzudenken. Da wir im Wesentlichen nach sortieren , verschwindet der gesamte absolute Wert, wenn wir versuchen, den letzten zu betrachten. Die zusätzlichen Kosten entweder oder .

D_{i}

$D_i$

\sum D_{i} v_{i}

$\sum D_iv_i$

(N - 1) D_{k} - \sum D_{i} v_{i}

$(N-1) D_k - \sum D_iv_i$

Rong Ge

OK muss nicht positiv sein. Das geht aber auch. Wir müssen nur den Unterschied zwischen feststellen und . Ndown ist die Anzahl der vorherigen 's, die gleich 0 sind, Nup ist die Anzahl der vorherigen ' s, die gleich 1 sind.

D_{i}

$D_i$

\sum | D_{i} v_{i} |

$\sum |D_i v_i|$

N d o w n | D_{k} | + N u p D_{k} - \sum D_{i} v_{i}

$Ndown|D_k| + Nup D_k - \sum D_iv_i$

v_{j}

$v_j$

v_{j}

$v_j$

Rong Ge

Das sieht vielversprechend aus, aber ich denke, es gibt einige weitere Schwierigkeiten, wenn die Eingabewerte zu nahe beieinander liegen. Betrachten Sie zB und . Wenn wir nun auf- und könnten, hätten wir nicht mehr die nette Eigenschaft, dass sich der Fehler um genau 1 ändert, je nachdem, ob auf- oder abgerundet ist. Wenn wir dagegen eine Rundung verbieten, die die Reihenfolge der Punkte ändert (wie ich es in der ursprünglichen Frage getan habe), müssen wir anscheinend mögliche Rundungen im Auge behalten, die im dynamischen Programm noch verfügbar sind. Können wir das tun?

x_{i} = 1.1

$x_i = 1.1$

x_{k} = 1.9

$x_k = 1.9$

x_{i}

$x_i$

x_{k}

$x_k$

x_{k}

$x_k$

Jukka Suomela

@Jukka Suomela, Nachdem ich Ihren Kommentar gesehen hatte, wurde mir klar, dass wir niemals zulassen sollten, dass etwas mit größerem abgerundet wird, während etwas mit kleinerem aufgerundet wird. Dies kann bewiesen werden, wenn Sie alle Fälle untersuchen. Dann ist die Antwort auf das Problem (mit Rundenbeschränkungen) klar: Es muss einen Schwellenwert geben, der über dem Schwellenwert liegt, den Sie aufrunden sollten, unter dem Sie abrunden sollten, an dem Schwellenwert sollten möglicherweise einige auf- und einige abrunden, aber nur die Qualität abhängig von der Anzahl. Diese Lösungen können leicht aufgezählt werden.

{x_{i}}

$\{x_i\}$

{x_{i}}

$\{x_i\}$

Rong Ge

{x_{i}} < {x_{j}}

$\{x_i\} < \{x_j\}$

{x_{k}}

$\{x_k\}$

{x_{i}}

$\{x_i\}$

{x_{j}}

$\{x_j\}$

{x_{k}}

$\{x_k\}$

x_{i}

$x_i$

x_{j}

$x_j$

x_{j}

$x_j$

x_{i}

$x_i$

Rong Ge