Search

We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal-dual paradigm in the enhanced setting of KKT conditions and convex programs. We pinpoint the added difficulty raised by this setting and the manner in which our algorithm circumvents it. [ABSTRACT FROM AUTHOR]

We develop polynomial-time algorithms for finding correlated equilibria—a well-studied notion of rationality that generalizes the Nash equilibrium—in a broad class of succinctly representable multiplayer games, encompassing graphical games, anonymous games, polymatrix games, congestion games, scheduling games, local effect games, as well as several generalizations. Our algorithm is based on a variant of the existence proof due to Hart and Schmeidler, and employs linear programming duality, the ellipsoid algorithm, Markov chain steady state computations, as well as applicationspecific methods for computing multivariate expectations over product distributions. For anonymous games and graphical games of bounded tree-width, we provide a different polynomial-time algorithm for optimizing an arbitrary linear function over the set of correlated equilibria of the game. In contrast to our sweeping positive results for computing an arbitrary correlated equilibrium, we prove that optimizing over correlated equilibria is NP-hard in all of the other classes of games that we consider. [ABSTRACT FROM AUTHOR]

We study a novel genre of optimization problems, which we call segmentation problems, motivated in part by certain aspects of clustering and data mining. For any classical optimization problem, the corresponding segmentation problem seeks to partition a set of cost vectors into several segments, so that the overall cost is optimized. We focus on two natural and interesting (but MAXSNP-complete) problems in this class, the HYPERCUBE SEGMENTATION PROBLEM and the CATALOG SEGMENTATION PROBLEM, and present approximation algorithms for them. We also present a general greedy scheme, which can be specialized to approximate any segmentation problem. [ABSTRACT FROM AUTHOR]

Considers a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries. Definition of the string graph problem; Characterization of map graphs in terms of planar bipartite graphs; Ways in which the cliques in map graphs are realized.

Presents a study that developed a theoretical framework to characterize the hardness of indexing data sets on block-access memory devices like computer hard disks. Lower-bound theorem that is applicable to arbitrary workloads; Trade-offs for a two-dimensional workload; Information on the Fibonacci workload.

Presents information on the off-line version of the geometric Gallery Tour (GT) problem. Notations and preliminaries of the study; Solutions and extensions of the problem; How to design an on-line algorithm for finding an optimal route.