DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.17

On the Convergence Time of a Natural Dynamics for Linear Programming

Authors: Vincenzo Bonifaci

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

We consider a system of nonlinear ordinary differential equations for the solution of linear programming (LP) problems that was first proposed in the mathematical biology literature as a model for the foraging behavior of acellular slime mold Physarum polycephalum, and more recently considered as a method to solve LP instances. We study the convergence time of the continuous Physarum dynamics in the context of the linear programming problem, and derive a new time bound to approximate optimality that depends on the relative entropy between projected versions of the optimal point and of the initial point. The bound scales logarithmically with the LP cost coefficients and linearly with the inverse of the relative accuracy, establishing the efficiency of the dynamics for arbitrary LP instances with positive costs.

Cite as

Vincenzo Bonifaci. On the Convergence Time of a Natural Dynamics for Linear Programming. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bonifaci:LIPIcs.ISAAC.2017.17,
  author =	{Bonifaci, Vincenzo},
  title =	{{On the Convergence Time of a Natural Dynamics for Linear Programming}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.17},
  URN =		{urn:nbn:de:0030-drops-82274},
  doi =		{10.4230/LIPIcs.ISAAC.2017.17},
  annote =	{Keywords: linear programming, natural algorithm, Physarum polycephalum, relative entropy, Mirror Descent}
}

Document

DOI: 10.4230/LIPIcs.STACS.2008.1338

Minimizing Flow Time in the Wireless Gathering Problem

Authors: Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, and Leen Stougie

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract

We address the problem of efficient data gathering in a wireless network through multi-hop communication. We focus on the objective of minimizing the maximum flow time of a data packet. We prove that no polynomial time algorithm for this problem can have approximation ratio less than $Omega(m^{1/3)$ when $m$ packets have to be transmitted, unless $P = NP$. We then use resource augmentation to assess the performance of a FIFO-like strategy. We prove that this strategy is 5-speed optimal, i.e., its cost remains within the optimal cost if we allow the algorithm to transmit data at a speed 5 times higher than that of the optimal solution we compare to.

Cite as

Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, and Leen Stougie. Minimizing Flow Time in the Wireless Gathering Problem. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 109-120, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bonifaci_et_al:LIPIcs.STACS.2008.1338,
  author =	{Bonifaci, Vincenzo and Korteweg, Peter and Marchetti-Spaccamela, Alberto and Stougie, Leen},
  title =	{{Minimizing Flow Time in the Wireless Gathering Problem}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{109--120},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1338},
  URN =		{urn:nbn:de:0030-drops-13381},
  doi =		{10.4230/LIPIcs.STACS.2008.1338},
  annote =	{Keywords: Wireless networks, data gathering, approximation algorithms, distributed algorithms}
}

Search Results

Documents authored by Bonifaci, Vincenzo

On the Convergence Time of a Natural Dynamics for Linear Programming

Abstract

Cite as

Minimizing Flow Time in the Wireless Gathering Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message