Miley Cyrus Big Boobs 2010

Hirsch's Conjecture refuted by a

When we take the linear programming course, teach us that the problem is represented by d variables and n constraints seeing

This geometric point of view we have to, for example, two variables (d = 2), a area that is bounded by straight lines that give the sides of a polygon, then we as the axes variables will be two and constraints (eg n = 5) will lead to each side of the polygon, which finally gives us the area where the feasible solutions.

The best we have on one side, which maximize or minimize a function of two variables (the objective function).

If we see three variables we imagine the space within which begin to act planes that cut through one side, and finally we leave an irregular polyhedron (but convex) with vertices, faces or facets and edges.

When operating the simplex method, it moves from one vertex to another through the edges, from one corner to another corner to find a solution that always improves previous and to reach the optimal solution.
recently by the news that publish newspapers, I learned something I had said Warren Hirsch, connected to the above problem, in which he states that the diameter (combinatorial) graph of a polyhedron of dimension "d" and defined by "n" inequalities can never be greater than "nd".

But to understand it referred is necessary to review some graph theory:

• Distance between two vertices: is the number of arcs that connect in the shortest route possible.
• Eccentricity of a vertex: is the longest distance between that vertex and another
• The diameter of a graph: is the maximum eccentricity of any vertex of the graph, ie the longest distance of any pair of vertices. To calculate the distance to be calculated for each pair of vertices and take the value of the calculated value.

Returning to the above would have to if I have two variables (dimension d = 2) and five constraints (inequalities n = 5), the longest distance between any pair of vertices never to exceed 3 (see the initial image to view if true, we see that in any case, we need more than 3 arc to connect two vertices). But it was still

just a guess. Recently the mathematical

Francisco Santos has found a case in which the rule is not met before, built a polytope dimension 43 (variables) with 86 facets (restrictions) spindle-shaped in which the diameter was greater to 43, which honestly is not very encouraging because instead of shortening the number of steps to reach the optimum would indicate that possibly in some cases we need to nd more steps (or edges) to connect the most remote corners.

That usually happens when we start with the worst solution (farthest from the optimum) and seek to reach the optimum in the fewest of steps or iterations as in the simplex.

For more information:

Cantabrian A teacher solves a problem word ...
El Diario Montanes - 26/05/2010
"is part of the Simplex Method, an algorithm that all companies in the world currently used for road design, production planning, ...
A English resolves the conjecture of Hirsch, laid over ... La Vanguardia
Resolved Hirsch's conjecture, a mathematical problem 50 years ABC.es Professor
solves one of the major mathematical puzzles Terra Peru
elmundo.es
the 42 articles »