3 citations · 6 across the 10 of their papers we have counts for
13 papers
Improved Integrality Gap for Multicommodity Flow on Trees
Elfarouk Harb
We improve the best known lower bound on the integrality gap for weighted unit-demand multicommodity flow on trees from to , improving on the long-standing bound of Chek…
How to Catch Grid Points
Sariel Har-Peled, Elfarouk Harb, Qizheng He
Given a positive integer , we study the problem of finding a convex polygon of minimum perimeter that encloses exactly points of . We show that an optimal poly…
Dense Subgraph Clustering and a New Cluster Ensemble Method
The-Anh Vu-Le, João Alfredo Cardoso Lamy, Tomás Alessi +5
We propose DSC-Flow-Iter, a new community detection algorithm that is based on iterative extraction of dense subgraphs. Although DSC-Flow-Iter leaves many nodes unclustered, it is…
Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
Elfarouk Harb, Yousef Yassin, Chandra Chekuri
We study the problem of minimizing or maximizing the average value of a submodular or supermodular set function over non-empty subsets $ S \s…
ReFill: Reinforcement Learning for Fill-In Minimization
Elfarouk Harb, Ho Shan Lam
Efficiently solving sparse linear systems , where is a large, sparse, symmetric positive semi-definite matrix, is a core challenge in scientific computing, machine learni…
Shortest Path Separators in Unit Disk Graphs
Elfarouk Harb, Zhengcheng Huang, Da Wei Zheng
We 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 answe…
Oracle-Augmented Prophet Inequalities
Sariel Har-Peled, Elfarouk Harb, Vasilis Livanos
In the classical prophet inequality settings, a gambler is given a sequence of random variables , taken from known distributions, observes their values in this…
New Prophet Inequalities via Poissonization and Sharding
Elfarouk Harb
This work introduces \emph{sharding} and \emph{Poissonization} as a unified framework for analyzing prophet inequalities. Sharding involves splitting a random variable into several…
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing
Elfarouk Harb, Kent Quanrud, Chandra Chekuri
Boob et al. [1] described an iterative peeling algorithm called Greedy++ for the Densest Subgraph Problem (DSG) and conjectured that it converges to an optimum solution. Chekuri, Q…
Revisiting Random Points: Combinatorial Complexity and Algorithms
Sariel Har-Peled, Elfarouk Harb
Consider 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 e…
KFC: A Scalable Approximation Algorithm for -center Fair Clustering
Elfarouk Harb, Ho Shan Lam
In this paper, we study the problem of fair clustering on the center objective. In fair clustering, the input is points, each belonging to at least one of protected gro…
Speeding up the AIFV- dynamic programs by two orders of magnitude using Range Minimum Queries
Mordecai Golin, Elfarouk Harb
AIFV- 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…
Polynomial Time Algorithms for Constructing Optimal Binary AIFV- Codes
Mordecai Golin, Elfarouk Harb
Huffman 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 constructi…