{
    "info": {
        "author": "Hermish Mehta",
        "author_email": "hermishdm@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "License :: OSI Approved :: MIT License",
            "Operating System :: OS Independent",
            "Programming Language :: Python :: 3"
        ],
        "description": "# CVX Graph Algorithms\n\n## Introduction\n\n> Modern convex optimization-based graph algorithms.\n\nConvex optimization presents an exciting new direction in designing exact and\napproximate graph algorithms. However, these algorithms are often overlooked in\npractice due to limitations in solving large convex programs quickly.\nConvex optimization-based graph algorithms nonetheless achieve impressive \ntheoretical performance, and often provide a beautiful geometric interpretation.\nThis package implements some of these algorithms and provides corresponding \ngraph generators to test performance---hopefully highlighting how simple, \nelegant and effective these can be for many real-world problems.\n\n## Details\n\nIn this package, we provide implementations of the following algorithms. Note\nfeatured convex optimization-based algorithms are in bold and references are\nprovided when available.\n\nThis package also provides functions to generate graphs drawn from the planted\nindependent set distribution and stochastic block model.\n\n1. Maximum Cut Problem\n    1. **Goemans-Williamson MAX-CUT Algorithm** [1]\n    2. Random MAX-CUT Algorithm\n    3. Greedy MAX-CUT Algorithm\n2. Independent Set Algorithm\n    1. **Crude SDP-based Independent Set** [2]\n    2. Greedy Independent Set Algorithm\n    3. Spectral Algorithm for Independent Set\n\n## Install and Usage\n\nYou can install this directly from the Python Package Index (PyPI).\n\n```\npip install cvxgraphalgs\n```\n\nBelow, we show how to run the Goemans-Williamson MAX-CUT Algorithm on a graph\ndrawn from the stochastic block model distribution. For more examples, explore \nthe jupyter notebooks available with the package documentation available\n[here](https://github.com/hermish/cvx-graph-algorithms/).\n\n```\n>>> import cvxgraphalgs as cvxgr\n>>> graph, _ = cvxgr.generators.bernoulli_planted_independent(\n...     size=50, independent_size=15, probability=0.5\n... )\n>>> recovered = cvxgr.algorithms.crude_sdp_independent_set(graph)\n>>> len(recovered)\n15\n```\n\n## References\n[1]: Goemans, Michel X., and David P. Williamson. \"Improved approximation \nalgorithms for maximum cut and satisfiability problems using semidefinite \nprogramming.\" *Journal of the ACM (JACM)* 42, no. 6 (1995): 1115-1145.\n\n[2]: McKenzie, Theo, Hermish Mehta, and Luca Trevisan. \"A New Algorithm for the\nRobust Semi-random Independent Set Problem.\" *arXiv:1808.03633* (2018).\n\n\n",
        "description_content_type": "text/markdown",
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/hermish/cvx-graph-algorithms",
        "keywords": "graph algorithms theory convex optimization",
        "license": "",
        "maintainer": "",
        "maintainer_email": "",
        "name": "cvxgraphalgs",
        "package_url": "https://pypi.org/project/cvxgraphalgs/",
        "platform": "",
        "project_url": "https://pypi.org/project/cvxgraphalgs/",
        "project_urls": {
            "Homepage": "https://github.com/hermish/cvx-graph-algorithms"
        },
        "release_url": "https://pypi.org/project/cvxgraphalgs/0.1.2/",
        "requires_dist": [
            "numpy",
            "scipy",
            "cvxpy",
            "networkx"
        ],
        "requires_python": "",
        "summary": "Modern convex optimization-based graph algorithms.",
        "version": "0.1.2"
    },
    "last_serial": 5538783,
    "releases": {
        "0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "9f7afeee6ab12deb95af83ed0e24f31c",
                    "sha256": "361bb9a99913989b1543faca94dbe12c538480d4cf1db18c6662d6f916f154b1"
                },
                "downloads": -1,
                "filename": "cvxgraphalgs-0.1-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "9f7afeee6ab12deb95af83ed0e24f31c",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 10028,
                "upload_time": "2019-07-16T06:23:59",
                "url": "https://files.pythonhosted.org/packages/fb/c1/be7f5ff80c9f4510bcf3c5093564193032bdf278d2737ec15d6557d1bd9a/cvxgraphalgs-0.1-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "5bd4c868fc7640154a675a28d62ff2cc",
                    "sha256": "7f0bb1d1c09b97dcf70b844bea10d804155036a39ff479144a934c2558693365"
                },
                "downloads": -1,
                "filename": "cvxgraphalgs-0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "5bd4c868fc7640154a675a28d62ff2cc",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6765,
                "upload_time": "2019-07-16T06:24:01",
                "url": "https://files.pythonhosted.org/packages/c4/46/b02b6cf4fb9d11fcd10abd8011a7141e61e9662354108f3a9f5d8ba35d9d/cvxgraphalgs-0.1.tar.gz"
            }
        ],
        "0.1.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "9e97dbf2bdf83e1c9654a5a22fb3f3af",
                    "sha256": "c72ea0a0614cd501baf05ae8664cc9529f7455c76b9fb170fec7bbac13e5c0e0"
                },
                "downloads": -1,
                "filename": "cvxgraphalgs-0.1.1-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "9e97dbf2bdf83e1c9654a5a22fb3f3af",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 10041,
                "upload_time": "2019-07-16T06:29:39",
                "url": "https://files.pythonhosted.org/packages/c7/3d/068845b87e94d0c8e39534dc55fc83842e14a5fdb7481c1c80a68cf44c48/cvxgraphalgs-0.1.1-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "0e694401338706eb970b75da49636608",
                    "sha256": "d2a78e4f96991a3fc6d2de03a99e8e1d3a5190afe18899068003ad34aa3d01f0"
                },
                "downloads": -1,
                "filename": "cvxgraphalgs-0.1.1.tar.gz",
                "has_sig": false,
                "md5_digest": "0e694401338706eb970b75da49636608",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6751,
                "upload_time": "2019-07-16T06:29:40",
                "url": "https://files.pythonhosted.org/packages/8f/4d/db24c00a7d7a58b9ba3708d445211676e788d0c3d7dbce6d2bea7d093747/cvxgraphalgs-0.1.1.tar.gz"
            }
        ],
        "0.1.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "726833d42f30ad8e6d4ac24eeb4ba460",
                    "sha256": "62e3e67663380776a80c5cb46bf46f2b955cece4e0f775cf64833225ff22ffe5"
                },
                "downloads": -1,
                "filename": "cvxgraphalgs-0.1.2-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "726833d42f30ad8e6d4ac24eeb4ba460",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 10045,
                "upload_time": "2019-07-16T06:34:24",
                "url": "https://files.pythonhosted.org/packages/f7/1a/1c3447a31c2e7d4aea1d0250e0c69e00fb2ff541b765eb834c6ecf681490/cvxgraphalgs-0.1.2-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "ca7743bb7bbfe1bb5e5ad092ab4c038e",
                    "sha256": "0dd81cae1d4b814b51fceae2df1532e9239ab04152768cc917a886ea17720445"
                },
                "downloads": -1,
                "filename": "cvxgraphalgs-0.1.2.tar.gz",
                "has_sig": false,
                "md5_digest": "ca7743bb7bbfe1bb5e5ad092ab4c038e",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6757,
                "upload_time": "2019-07-16T06:34:26",
                "url": "https://files.pythonhosted.org/packages/8b/b3/1bcef1166cfd42b2fc89b759c78d8ea97f53bc808cb7625d3306e3c20765/cvxgraphalgs-0.1.2.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "726833d42f30ad8e6d4ac24eeb4ba460",
                "sha256": "62e3e67663380776a80c5cb46bf46f2b955cece4e0f775cf64833225ff22ffe5"
            },
            "downloads": -1,
            "filename": "cvxgraphalgs-0.1.2-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "726833d42f30ad8e6d4ac24eeb4ba460",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": null,
            "size": 10045,
            "upload_time": "2019-07-16T06:34:24",
            "url": "https://files.pythonhosted.org/packages/f7/1a/1c3447a31c2e7d4aea1d0250e0c69e00fb2ff541b765eb834c6ecf681490/cvxgraphalgs-0.1.2-py3-none-any.whl"
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "ca7743bb7bbfe1bb5e5ad092ab4c038e",
                "sha256": "0dd81cae1d4b814b51fceae2df1532e9239ab04152768cc917a886ea17720445"
            },
            "downloads": -1,
            "filename": "cvxgraphalgs-0.1.2.tar.gz",
            "has_sig": false,
            "md5_digest": "ca7743bb7bbfe1bb5e5ad092ab4c038e",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 6757,
            "upload_time": "2019-07-16T06:34:26",
            "url": "https://files.pythonhosted.org/packages/8b/b3/1bcef1166cfd42b2fc89b759c78d8ea97f53bc808cb7625d3306e3c20765/cvxgraphalgs-0.1.2.tar.gz"
        }
    ]
}