The diversity maximization problem (also known as dispersion) is a fundamental optimization problem with broad applications in data mining, machine learning, web search, and data summarization. In its classical form, the goal is to select a subset of k points from a metric space that maximizes a prescribed diversity objective over the selected set. Motivated by modern large-scale and distributed systems, the input dataset is often partitioned into multiple groups, each stored on a separate machine or data center. More recently, concerns of fairness and representation in applications such as machine learning and recommendation systems have led to the study of fair diversity maximization under group constraints. In this setting, we are given m groups of points in a metric space along with integers k1, ..., km satisfying #x03A3;iki = k, and the objective is to select exactly ki points from group i so as to maximize the diversity of the union of the selected points.

Clustering and diversification are two central problems with various applications in machine learning, data mining, and information retrieval. The k-center clustering and k-diversity maximization are two of the most well-studied and widely-used problems in this area. Both problems admit sequential algorithms with optimal approximation factors of 2 in any metric space. However, finding distributed algorithms matching the same optimal approximation ratios has been open for more than a decade, with the best current algorithms having factors at least twice the optimal. In this paper, we settle this open problem by presenting constant-round distributed algorithms for k-center clustering and k-diversity maximization in the massively parallel computation (MPC) model, achieving an approximation factor of 2 + ε in any metric space for any constant ε > 0, which is essentially the best possible considering the lower bound of 2 on the approximability of both these problems. Our algorithms are based on a novel technique for approximating vertex degrees and finding a so-called k-bounded maximal independent set in threshold graphs, using only a constant number of MPC rounds. Other applications of our general technique is also implied, including an almost optimal (3 + ε)-approximation algorithm for the k-supplier problem in any metric space in the MPC model.

Motivated by the bus escape routing problem in printed circuit boards (PCBs), we study the following optimization problem: given a set of rectangles attached to the boundary of a rectangular region, find a subset of nonoverlapping rectangles with maximum total weight. We present an efficient algorithm that solves this problem optimally in O(n4) time, where n is the number of rectangles in the input instance. This improves over the best previous O(n6)-time algorithm available for the problem. We also present two efficient approximation algorithms for the problem that find near-optimal solutions with guaranteed approximation factors. The first algorithm finds a 2-approximate solution in O(n2) time, and the second one computes a 4/3-approximation in O(n3) time. The experimental results demonstrate the efficiency of both our exact and approximation algorithms.

We consider the problem of path planning above a polyhedral terrain and present a new algorithm that for any p ges 1, computes a (c + epsi)-approximation to the Lp-shortest path above a polyhedral terrain in O(n/epsi log n log log n) time and O(n log n) space, where n is the number of vertices of the terrain, and c = 2(p-1)p/. This leads to an epsi-approximation algorithm for the problem in L1metric, and a (radic2 + epsi)-factor approximation algorithm in Euclidean space