12 research outputs found
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing
No full textBoob et al. [Boob et al., 2020] described an iterative peeling algorithm called Greedy++ for the Densest Subgraph Problem (DSG) and conjectured that it converges to an optimum solution. Chekuri, Qaunrud and Torres [Chandra Chekuri et al., 2022] extended the algorithm to supermodular density problems (of which DSG is a special case) and proved that the resulting algorithm Super-Greedy++ (and hence also Greedy++) converges. In this paper we revisit the convergence proof and provide a different perspective. This is done via a connection to Fujishige’s quadratic program for finding a lexicographically optimal base in a (contra) polymatroid [Satoru Fujishige, 1980], and a noisy version of the Frank-Wolfe method from convex optimization [Frank and Wolfe, 1956; Jaggi, 2013]. This yields a simpler convergence proof, and also shows a stronger property that Super-Greedy++ converges to the optimal dense decomposition vector, answering a question raised in Harb et al. [Harb et al., 2022]. A second contribution of the paper is to understand Thorup’s work on ideal tree packing and greedy tree packing [Thorup, 2007; Thorup, 2008] via the Frank-Wolfe algorithm applied to find a lexicographically optimum base in the graphic matroid. This yields a simpler and transparent proof. The two results appear disparate but are unified via Fujishige’s result and convex optimization
Shortest Path Separators in Unit Disk Graphs
No full textWe introduce a new balanced separator theorem for unit-disk graphs involving two shortest paths combined with the 1-hop neighbours of those paths and two other vertices. This answers an open problem of Yan, Xiang and Dragan [CGTA '12] and improves their result that requires removing the 3-hop neighbourhood of two shortest paths. Our proof uses very different ideas, including Delaunay triangulations and a generalization of the celebrated balanced separator theorem of Lipton and Tarjan [J. Appl. Math. '79] to systems of non-intersecting paths
Oracle-Augmented Prophet Inequalities
No full textIn the classical prophet inequality setting, a gambler is given a sequence of n random variables X₁, … , X_n, taken from known distributions, observes their values in adversarial order and selects one of them, immediately after it is being observed, aiming to select a value that is as high as possible. The classical prophet inequality shows a strategy that guarantees a value at least half of the value of an omniscience prophet that always picks the maximum, and this ratio is optimal.
Here, we generalize the prophet inequality, allowing the gambler some additional information about the future that is otherwise privy only to the prophet. Specifically, at any point in the process, the gambler is allowed to query an oracle . The oracle responds with a single bit answer: YES if the current realization is greater than the remaining realizations, and NO otherwise. We show that the oracle model with m oracle calls is equivalent to the Top-1-of-(m+1) model when the objective is maximizing the probability of selecting the maximum. This equivalence fails to hold when the objective is maximizing the competitive ratio, but we still show that any algorithm for the oracle model implies an equivalent competitive ratio for the Top-1-of-(m+1) model.
We resolve the oracle model for any m, giving tight lower and upper bound on the best possible competitive ratio compared to an almighty adversary. As a consequence, we provide new results as well as improvements on known results for the Top-1-of-m model
New Prophet Inequalities via Poissonization and Sharding
No full textThis work introduces \emph{sharding} and \emph{Poissonization} as a unified
framework for analyzing prophet inequalities. Sharding involves splitting a
random variable into several independent random variables, shards, that
collectively mimic the original variable's behavior. We combine this with
Poissonization, where these shards are modeled using a Poisson distribution.
Despite the simplicity of our framework, we improve the competitive ratio
analysis of a dozen well studied prophet inequalities in the literature, some
of which have been studied for decades. This includes the
\textsc{Top--of-} prophet inequality, prophet secretary inequality, and
semi-online prophet inequality, among others. This approach not only refines
the constants but also offers a more intuitive and streamlined analysis for
many prophet inequalities in the literature. Furthermore, it simplifies proofs
of several known results and may be of independent interest for other variants
of the prophet inequality, such as order-selection.Comment: 51 pages. Major rewrite, several new results/figure
A Polynomial Time Algorithm for Constructing Optimal Binary AIFV-2 Codes
No full textHuffman Codes are optimal Instantaneous Fixed-to-Variable (FV) codes in which every source symbol can only be encoded by one codeword. Relaxing these constraints permits constructing better FV codes. More specifically, recent work has shown that AIFV-m codes can beat Huffman coding. AIFV-m codes construct an m-tuple of different coding trees between which the code alternates and are only almost instantaneous (AI). This means that decoding a word might require a delay of a finite number of bits. Current algorithms for constructing optimal AIFV-m codes are iterative processes that construct progressively 'better sets' of code trees. The processes have been proven to finitely converge to the optimal code but with no known bounds on the convergence rate. This paper derives a geometric interpretation of the space of binary AIFV-2 codes, permitting the development of the first polynomially time-bounded procedure for constructing optimal AIFV codes. This binary-search like procedure will run in O(n3+) time, where n is the number of symbols in the source alphabet and b is the maximum number of bits used to encode any one input probability.</p
Polynomial Time Algorithms for Constructing Optimal AIFV Codes
No full textHuffman Codes are 'optimal' Fixed-to-Variable (FV) codes if every source symbol can only be encoded by one codeword. Relaxing this constraint permits constructing better FV codes. More specifically, recent work has shown that AIFV codes can beat Huffman coding. AIFV codes construct a set of different coding trees between which the code alternates and are only 'almost instantaneous' (AI). This means that decoding a word might require a delay of a finite number of bits. Current algorithms for constructing optimal AIFV codes are iterative processes that construct progressively 'better sets' of code trees. The processes have been proven to finitely converge to the optimal code but with no known bounds on the convergence time. This paper derives a geometric interpretation of the space of AIFV codes. This permits the development of new polynomially time-bounded iterative procedures for constructing optimal AIFV codes. For the simplest case we show that a binary search procedure can replace the current iterative process. For the more complicated cases we describe how to frame the problem as a linear programming problem with an exponential number of constraints but a polynomial time separability oracle. This permits using the Grotschel, Lovasz and Schrijver ellipsoid method to solve the problem in a polynomial number of steps.</p
Speeding up the AIFV-2 dynamic programs by two orders of magnitude using Range Minimum Queries
No full textAIFV-2 codes are a new method for constructing lossless codes for memoryless sources that provide better worst-case redundancy than Huffman codes. They do this by using two code trees instead of one and also allowing some bounded delay in the decoding process. Known algorithms for constructing AIFV-codes are iterative; at each step they replace the current code tree pair with a “better” one. The current state of the art for performing this replacement is a pair of Dynamic Programming (DP) algorithms that use O(n5) time to fill in two tables, each of size O(n3) (where n is the number of different characters in the source). This paper describes how to reduce the time for filling in the DP tables by two orders of magnitude, down to O(n3). It does this by introducing a grouping technique that permits separating the Θ(n3)-space tables into Θ(n) groups, each of size O(n2), and then using Two-Dimensional Range-Minimum Queries (RMQs) to fill in that group's table entries in O(n2) time.</p
KFC: A scalable approximation algorithm for k-center fair clustering
No full textIn this paper, we study the problem of fair clustering on the k-center objective. In fair clustering, the input is N points, each belonging to at least one of l protected groups, e.g. male, female, Asian, Hispanic. The objective is to cluster the N points into k clusters to minimize a classical clustering objective function. However, there is an additional constraint that each cluster needs to be fair, under some notion of fairness. This ensures that no group is either “over-represented” or “under-represented” in any cluster. Our work builds on the work of Chierichetti et al. (NIPS 2017), Bera et al. (NeurIPS 2019), Ahmadian et al. (KDD 2019), and Bercea et al. (APPROX 2019). We obtain a randomized 3-approximation algorithm for the k-center objective function, beating the previous state of the art (4-approximation). We test our algorithm on real datasets, and show that our algorithm is effective in finding good clusters without over-representation or under-representation, surpassing the current state of the art in runtime speed, clustering cost, while achieving similar fairness violations.</p
Revisiting Random Points: Combinatorial Complexity and Algorithms
No full textConsider a set of points picked uniformly and independently from
for a constant dimension -- such a point set is extremely well
behaved in many aspects. For example, for a fixed , we prove a new
concentration result on the number of pairs of points of at a distance at
most -- we show that this number lies in an interval that contains only
numbers.
We also present simple linear time algorithms to construct the Delaunay
triangulation, Euclidean MST, and the convex hull of the points of . The MST
algorithm is an interesting divide-and-conquer algorithm which might be of
independent interest. We also provide a new proof that the expected complexity
of the Delaunay triangulation of is linear -- the new proof is simpler and
more direct, and might be of independent interest. Finally, we present a simple
time algorithm for the distance selection problem for
