Anonymous

Changes

From Theory

CATS-Apr-11-2014 (view source)

Revision as of 14:14, 3 April 2014

27 bytes removed ,  14:14, 3 April 2014
→‎Abstract
Line 14: Line 14:     
== Abstract ==
 
== 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.
 
Retrieved from "https://wiki.cs.umd.edu/theory/view/Special:MobileDiff/1844"