Constraint violation and efficiency in search

It seems that (in a broad sense) two approaches can be utilized to produce an algorithm for solving various optimization problems:

• Start with a feasible solution and expand search until constraints are tight and solution is maximal (or minimal).

• Begin with violated constraints and search for maximal (or minimal) feasible approach.

For the Max-Flow problem Ford-Fulkerson satisfies condition (1), while Push-Relabel satisfies condition (2). An interesting point is that Push-Relabel is a more efficient algorithm than Ford-Fulkerson. My question is this:


What other examples are there where (2)-based approaches outperform their (1)-based counterparts?

A follow up is:


Do there exist meta-theorems regarding approaches based on condition (2)?

Another example is interior-point algorithms for convex optimizations, which (if I remember correctly) start at an arbitrary point and try to simultaneously get into the feasible region and optimize the objective function. They are provable and (to some extent) practically faster than the simplex algorithm (and related algorithms like the criss-cross algorithm), which does a local search inside the feasible polytope.

StackExchange Computer Science Q#10528, answer score: 4