Integer Program Combination Optimization - Recitation Notes for Duality II and Efficient Algorithms

University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

427

Pages:

1
Author:

quietriot74uo

1 Algorithm 6.6 1.1 Step 1 & 2: Algo 6.5 Slide 1 • d: interior point in P • D −2 : symmetric, positive deﬁnite matrix, • D invertible, contains information about the major and minor axles of the el lipsoid. • In step 2 of 6.6, Dy is in the space of x, space of y is transformed and ”normal ized”. Ignoring d, – x� D −2 x describes an ellipse – (D −1 x)� I −2 (D −1 x) describes a sphere 1.2 Step 3 to 6 • Find approximate nearest nearest lattice vector to p = D −1 d: Slide 2 1 �y ∗ − p� ≤ (2n − 1) 2 min{�y − p� : y ∈ L(D −1 ), y = � p} – Nearest vector problem is NPhard. � p} min{�y − p� : y ∈ L(D −1 ), y = • bn bears information about the ﬂat axis of the ellipse. 1.3 Step 8 Slide 3 • Proof in Therorem 6.11 shows that: ˜� p ˜=k – c ˜� p̃ ∈ Z – c ˜� p ˜ ≤ �˜ c� p − �c̃�� ≤ c c� p + �c̃�� (from P ⊂ E � ) – �˜ • bn bears information about the ﬂat axis of the ellipse. 1.4 Questions • How can we be sure that we cover P and only P since we use ellipsoids? • Given Algorithm 6.6, how can we solve an optimization problem in polynomial time? • If we have an algorithm that ﬁnd nearest lattice point, how can we use it to solve this problem? • Can Algorithm 6.5 be used for the separation problem in Chapter 5? 1 Slide 4