NDLI: On a Natural Dynamics for Linear Programming

Please wait, while we are loading the content...

Can Almost Everybody be Almost Happy?

Permanent v. Determinant: An Exponential Lower Bound Assuming Symmetry

Local Algorithms for Block Models with Side Information

Strategic Classification

Obfuscating Conjunctions under Entropic Ring LWE

Timeability of Extensive-Form Games

Rational Proofs with Multiple Provers

Coordination Complexity: Small Information Coordinating Large Populations

Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

How To Bootstrap Anonymous Communication

Information Complexity Density and Simulation of Protocols

Mechanisms With Costly Knowledge

On Hardness of Approximating the Parameterized Clique Problem

Distribution Design

A PAC Approach to Application-Specific Algorithm Selection

Secure Multiparty Computation with General Interaction Patterns

Auction Revenue in the General Spiteful-Utility Model

Lower Bounds: From Circuits to QBF Proof Systems

On a Natural Dynamics for Linear Programming

On Sketching Quadratic Forms

Time-Lock Puzzles from Randomized Encodings

Satisfiability on Mixed Instances

On the Computational Complexity of Optimal Simple Mechanisms

The Complexity of DNF of Parities

Sampling Correctors

An Axiomatic Approach to Community Detection

Fully Succinct Garbled RAM

How to Incentivize Data-Driven Collaboration Among Competing Parties

Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

On the Space Complexity of Linear Programming with Preprocessing

Energy-Efficient Algorithms

Is There an Oblivious RAM Lower Bound?

On the Computational Complexity of Limit Cycles in Dynamical Systems

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions

On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]

Cryptography for Parallel RAM from Indistinguishability Obfuscation

From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology

The Space "Just Above" BQP

Simultaneous Private Learning of Multiple Concepts

Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds

On a Natural Dynamics for Linear Programming

Content Provider	ACM Digital Library
Author	Vishnoi, Nisheeth K. Straszak, Damian
Abstract	In this paper we study dynamics inspired by Physarum polycephalum (a slime mold) for solving linear programs [NTY00, IJNT11, JZ12]. These dynamics are arrived at by a local and mechanistic interpretation of the inner workings of the slime mold and a global optimization perspective has been lacking even in the simplest of instances. Our first result is an interpretation of the dynamics as an optimization process. We show that Physarum dynamics can be seen as a steepest-descent type algorithm on a certain Riemannian manifold. Moreover, we prove that the trajectories of Physarum are in fact paths of optimizers to a parametrized family of convex programs, in which the objective is a linear cost function regularized by an entropy barrier. Subsequently, we rigorously establish several important properties of solution curves of Physarum. We prove global existence of such solutions and show that they have limits, being optimal solutions of the underlying LP. Finally, we show that the discretization of the Physarum dynamics is efficient for a class of linear programs, which include unimodular constraint matrices. Thus, together, our results shed some light on how nature might be solving instances of perhaps the most complex problem in P: linear programming.
Starting Page	291
Ending Page	291
Page Count	1
File Format	PDF
ISBN	9781450340571
DOI	10.1145/2840728.2840762
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-01-14
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Linear programming Physarum Dynamical systems
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Robust-to-dynamics linear programming

Convergence of the non-uniform directed Physarum model

Dynamical programming of physarum (908).

Dynamical systems that solve linear programming problems

A slime mold solver for linear programming problems.

On a Natural Dynamics for Linear Programming

Optimal motion planning for assembly skill based on mixed logical dynamical system

On a nonlinear observer with pseudo-linearized error dynamics

PhysarumSoft - a software tool for programming Physarum machines and simulating Physarum games

On a Natural Dynamics for Linear Programming

Similar Documents

Robust-to-dynamics linear programming

Convergence of the non-uniform directed Physarum model

Dynamical programming of physarum (908).

Dynamical systems that solve linear programming problems

A slime mold solver for linear programming problems.

On a Natural Dynamics for Linear Programming

Optimal motion planning for assembly skill based on mixed logical dynamical system

On a nonlinear observer with pseudo-linearized error dynamics

PhysarumSoft - a software tool for programming Physarum machines and simulating Physarum games

On a Natural Dynamics for Linear Programming