Changes

CATS-Apr-11-2014 (view source)

27 bytes removed , 14:14, 3 April 2014

Line 14: Line 14:

== Abstract ==

−

~~Profound insights, obtained over~~ the ~~last decade~~, ~~have elevated equilibrium computation~~ to a

+

We are generally interested in the following not-well defined problem: What

−

~~full~~-~~fledged area within~~ the ~~theory~~ of algorithms and ~~computational complexity. It has its own~~

+

is a conceptually simple algorithm and what is the power and limitations

−

~~character which is quite distinct from~~ the ~~computability of optimization problems.~~

+

of such algorithms? In particular, what is a greedy algorithm

+

or more generally a myopic algorithm for a combinatorial optimization

+

problem? And to be even more specific,

+

motivated by the Buchbinder et al ``online greedy algorithm'' for the

+

unconstrained non-monotone

+

submodular maximization problem, what are (if any) the limitations of

+

algorithms "of this genre" for the general unconstrained problem and for

+

specific instances of the problem, such as Max-Di-Cut?

−

~~Using the powerful notions of complementarity and complementary pivot algorithms, traditional~~

+

Joint work with Norman Huang

−

~~complexity classes NP, co-NP, ETR (Existential Theory of Reals) and UTR (Universal Theory of Reals),~~

−

~~and new classes PPAD and FIXP, we will provide a broad overview of this theory as it stands today.~~

−

~~The picture is intensely beautiful! The area still has low-hanging fruit -- we will indicate where.~~

373

edits