Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
→Abstract
Line 14:
Line 14:
Profound insights, obtained over the last decade, have elevated equilibrium computation to a +full-fledged area within the theory of algorithms and computational complexity. It has its own +character which is quite distinct from the computability of optimization problems. +Using the powerful notions of complementarity and complementary pivot algorithms, traditional +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.
== Abstract ==
== Abstract ==
−We are generally interested in the following not-well defined problem: What
−is a conceptually simple algorithm and what is the power and limitations
−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?
−Joint work with Norman Huang
−