Publication

Approximations in Distributed Optimization

Boi Faltings
2005
Reports

Abstract

We present in this paper an approximative method for distributed combinatorial optimization problems based on dynamic programming. The algorithm is a utility propagation method and requires a linear number of messages. The largest message is in the worst case exponential in the width of the constraint graph, in case of exact computation. However, it can be tuned with 2 parameters that allow the user to specify the desired tradeoff between solution quality and computational complexity. The second part of this paper presents an anytime version of the first algorithm, which provides increasingly accurate solutions while the propagation is still in progress, thus being suitable for very large distributed problems. Although the algorithms presented here are distributed, their reduction to the centralized case is rather straightforward.

Official source

https://infoscience.epfl.ch/entities/publication/d1218055-a4fe-4ef7-a744-3886131bc263

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Boi Faltings
2005
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/d1218055-a4fe-4ef7-a744-3886131bc263

About this result

Related concepts (32)

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.

Distributed computing

A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another. Distributed computing is a field of computer science that studies distributed systems. The components of a distributed system interact with one another in order to achieve a common goal. Three significant challenges of distributed systems are: maintaining concurrency of components, overcoming the lack of a global clock, and managing the independent failure of components.

Related publications (32)

Approximations in Distributed Optimization

Chat with Graph Search

Sponsored Fair Exchange (Extended Abstract)

Accelerated Solvers for Neutral Particle Dynamics in Plasma Simulation

Controller Design for Structured State-space Models via Contraction Theory