fixed_n_comp_ratio.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "34f3f02a-26f7-4391-b728-93cc2c6e853a",
   "metadata": {},
   "source": [
    "## imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "id": "cc9d1795-a5fe-4001-a020-a763bc9e1dc2",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "from tqdm import tqdm, trange"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d6377b5-55d0-4f54-b7b7-7e773b09b259",
   "metadata": {},
   "source": [
    "## functions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c031d346-d041-4f67-b6da-224fa6a08e03",
   "metadata": {},
   "source": [
    "convert an integer $x$ to a zero-padded binary string with $d$ digits:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "id": "d331b078-01b5-487e-9ac7-4fcabe9960dd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_bin(x, d):\n",
    "    assert d >= 0\n",
    "    \n",
    "    if d == 0:\n",
    "        return \"\"\n",
    "    else:\n",
    "        return f'{x:0{d}b}'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dec56638-a2fe-47e1-8cce-52a0fceb294c",
   "metadata": {},
   "source": [
    "get the $n$th triangular number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "id": "8a4fd9ba-4106-4a85-8bb2-f3d5eac6120f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def T(n):\n",
    "    return int((n+1) * n / 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee61e344-edc4-43d3-a106-8e4c66fe3472",
   "metadata": {},
   "source": [
    "check if next node in graph represented by `G_str` can be added to independent set represented by `selected_str`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "id": "ba985095-fbc2-40d7-ae2f-b82de545a0e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def conflicts(G_str, selected_str):\n",
    "    d = len(selected_str)\n",
    "    \n",
    "    if d == 0:\n",
    "        return False\n",
    "\n",
    "    to_check = G_str[T(d-1):T(d-1)+d]\n",
    "    for x, y in zip(selected_str, to_check):\n",
    "        if x == \"1\" and y == \"1\":\n",
    "            return True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aceac7ab-8423-4f04-b1fc-cb41bb70bcf3",
   "metadata": {},
   "source": [
    "get the edge corresponding to the $j$th character in a `G_str`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "id": "3cd55816-2f03-4b97-aafe-c7e2323dec00",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_edge(j):\n",
    "    assert j >= 0\n",
    "    \n",
    "    temp = 0\n",
    "    i = 1\n",
    "    while temp + i < j + 1:\n",
    "        temp += i\n",
    "        i += 1\n",
    "    return j - temp, i"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f95ff9f-3b60-4234-88c6-c5ff229511d4",
   "metadata": {},
   "source": [
    "print the edges of the graph represented by the string `G_str`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "id": "0134656c-a44c-4f83-86f0-9ce589d027a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_graph(G_str):\n",
    "    for j, e in enumerate(G_str):\n",
    "        if e == \"1\":\n",
    "            x, y = find_edge(j)\n",
    "            print((x+1, y+1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab19e1af-d32e-425e-a0d2-db4c17280cd5",
   "metadata": {},
   "source": [
    "compute competitive ratio for $n$ nodes and probability $p$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "id": "bc10c333-504d-4f66-9c8a-b1e8947e9a43",
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_comp_ratio(n, p):\n",
    "    num_pairs = T(n-1)\n",
    "    \n",
    "    first_iter = True\n",
    "    for G_int in range(2**num_pairs):\n",
    "        G_str = to_bin(G_int, num_pairs)\n",
    "\n",
    "        # optimal offline algorithm\n",
    "        # note: this could be marginally sped up by going in decreasing order of selected set size and breaking once a valid selection is found\n",
    "        opt_val = 0\n",
    "        for i in range(2**n):\n",
    "            selected_str = to_bin(i, n)\n",
    "            valid_sel = True\n",
    "            for j, e in enumerate(G_str):\n",
    "                if e == \"1\":\n",
    "                    x, y = find_edge(j)\n",
    "                    if selected_str[x] == \"1\" and selected_str[y] == \"1\":\n",
    "                        valid_sel = False\n",
    "                        break\n",
    "            if valid_sel:\n",
    "                val = 0\n",
    "                for node in selected_str:\n",
    "                    if node == \"1\":\n",
    "                        val += 1\n",
    "                opt_val = max(opt_val, val)\n",
    "\n",
    "\n",
    "        # probabilistic greedy algorithm\n",
    "        F = {}\n",
    "\n",
    "        for i in range(2**n):\n",
    "            F[to_bin(i, n)] = 0\n",
    "\n",
    "        for d in range(n-1,-1,-1):\n",
    "            for i in range(2**d):\n",
    "                selected_str = to_bin(i, d)\n",
    "\n",
    "                if not conflicts(G_str, selected_str):  # all selected nodes are not joined to current node\n",
    "                    res = p * (1 + F[selected_str + \"1\"]) + (1-p) * F[selected_str + \"0\"]\n",
    "                else:\n",
    "                    res = F[selected_str + \"0\"]\n",
    "\n",
    "                F[selected_str] = res\n",
    "\n",
    "        greedy_val = F[\"\"]\n",
    "        \n",
    "        \n",
    "        ratio = opt_val / greedy_val if greedy_val > 0 else math.inf\n",
    "        \n",
    "        if first_iter:\n",
    "            best_G = G_str\n",
    "            comp_ratio = ratio\n",
    "            first_iter = False\n",
    "        elif ratio > comp_ratio:\n",
    "            best_G = G_str\n",
    "            comp_ratio = ratio\n",
    "    \n",
    "    return best_G, comp_ratio"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8359936-a250-4be0-b329-d9d826de6c38",
   "metadata": {},
   "source": [
    "## results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "id": "c9194da9-902a-4399-a8ab-826b2e050ecf",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "id": "694d079f-4081-4f6f-a642-03c8ab4dfd0f",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|█████████████████████████████████████████████████████████████| 101/101 [00:01<00:00, 95.14it/s]\n"
     ]
    }
   ],
   "source": [
    "comp_ratios = {}\n",
    "\n",
    "for p in tqdm(np.linspace(0, 1, num=101)):\n",
    "    comp_ratios[p] = compute_comp_ratio(n, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "id": "5019db6e-ae79-4ce3-a059-b9ec9fac1382",
   "metadata": {},
   "outputs": [],
   "source": [
    "p = min(comp_ratios, key=lambda string: comp_ratios.get(string)[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "id": "9abad44f-5475-412f-82fa-b298f015a7be",
   "metadata": {},
   "outputs": [],
   "source": [
    "G_str, comp_ratio = comp_ratios[p]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "id": "b50ea76e-266d-4ba7-9e5c-098e5687d834",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "with p=0.67, graph 110100 gives competitive ratio 2.250056\n"
     ]
    }
   ],
   "source": [
    "print(f\"with {p=:.2f}, graph {G_str} gives competitive ratio {comp_ratio:.6f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "id": "072252c5-c031-4381-9c78-07c82f34a391",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2)\n",
      "(1, 3)\n",
      "(1, 4)\n"
     ]
    }
   ],
   "source": [
    "print_graph(G_str)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7e69320-602f-4c86-95f1-26dc44fa0163",
   "metadata": {},
   "source": [
    "### ad hoc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "id": "6954de64-83a5-49ad-9d25-8ba0788e08e0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('111110110011000110000', 3.6363636363636362)"
      ]
     },
     "execution_count": 182,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_comp_ratio(7, 0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "id": "5c7360c4-ae93-4f8b-ba95-bd1ff8fb6f49",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2)\n",
      "(1, 3)\n",
      "(2, 3)\n",
      "(1, 4)\n",
      "(2, 4)\n",
      "(1, 5)\n",
      "(2, 5)\n",
      "(1, 6)\n",
      "(2, 6)\n",
      "(1, 7)\n",
      "(2, 7)\n"
     ]
    }
   ],
   "source": [
    "print_graph('111110110011000110000')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:omisr]",
   "language": "python",
   "name": "conda-env-omisr-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}