Ellipsoid Method for Integer Programming - Edubirdie

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

Related Documents

Ellipsoid Method for Integer Programming

Ellipsoid Method for Integer Programming - Page 1

of 1

Recommended Documents

The Balance Sheet and the Recording of Transactions

The Balance Sheet and the Recording of Transactions

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

The Accounting Process

The Accounting Process

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Intro to Financial & Managerial Accounting Set 2

Intro to Financial & Managerial Accounting Set 2

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Financial Statements - the Annual Report

Financial Statements - the Annual Report

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

The Classified Balance Sheet

The Classified Balance Sheet

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Tabular analysis of the effects of various

Tabular analysis of the effects of various

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Mapping the Telecom Value Chain - A Roadmap for Communications Networks

Mapping the Telecom Value Chain - A Roadmap for Communications Networks

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Constructive Conflict, Uncertainty and Real Options

Constructive Conflict, Uncertainty and Real Options

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Strategic Management and Consulting Proseminar Strategic Questions Lufthansa

Strategic Management and Consulting Proseminar Strategic Questions Lufthansa

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Advanced Corporate Risk Management: MW Petroleum (B)

Advanced Corporate Risk Management: MW Petroleum (B)

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Communication for Managers Active Listening Exercise

Communication for Managers Active Listening Exercise

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Communication for Managers: Craigstone Worksheet

Communication for Managers: Craigstone Worksheet

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

New Documents from this Course

Introduction to Financial and Managerial Accountin Problem Set 1

Introduction to Financial and Managerial Accountin Problem Set 1

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Midterm 2 Review Notes

Midterm 2 Review Notes

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Marketable Securities (Deferred Taxes)

Marketable Securities (Deferred Taxes)

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Long-term Assets, Depreciation (Deferred Taxes)

Long-term Assets, Depreciation (Deferred Taxes)

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note