Online Maximum Independent Set of Hyperrectangles

Companion repo for "Online Maximum Independent Set of Hyperrectangles" paper.

fixed_n_comp_ratio.ipynb includes code to compute upper bounds on the competitive ratio of the "greedy with probability $p$" algorithm for fixed $n$ under the oblivious adversary model. experiments.ipynb includes code to empirically evaluate the online greedy algorithm under different input distributions.

Installation

• Clone the repo
• Create a virtual environment using e.g., venv or Conda
• Install any missing packages using e.g., pip or Conda
  • only essential external packages are NumPy, SciPy, and Matplotlib

Usage

• Run desired notebook using Jupyter Notebook or JupyterLab

Authors

• Rishi Advani
• Abolfazl Asudeh

License

This project is licensed under the MIT License — see the LICENSE file for details.