Publications related to Greedy algorithm

Freight railway network design problem

Michel Bierlaire, Virginie Janine Camille Lurkin, Nikola Obrenovic

In freight railway networks, commodities are usually transported via hubs, which are called marshaling or shunting yards, depending on their capacity. Consequently, the number and locations of these yards effect the transport costs to a great extent. The ...

2018

Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints

Boi Faltings, Andreas Krause, Goran Radanovic

We study a problem of optimal information gathering from multiple data providers that need to be incentivized to provide accurate information. This problem arises in many real world applications that rely on crowdsourced data sets, but where the process of ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2018

Approximating Steiner trees and forests with minimum number of Steiner points

Nachshon Cohen

Let R be a finite set of terminals in a convex metric space (M, d). We give approximation algorithms for problems of finding a minimum size set S subset of M of additional points such that the unit-disc graph G[R boolean OR S] of R boolean OR S satisfies s ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2018

Constant factor approximation for ATSP with two edge weights

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was give ...

SPRINGER HEIDELBERG2018

Using Structural Properties for Integer Programs

Kim-Manuel Klein

Integer programs (IPs) are one of the fundamental tools used to solve combinatorial problems in theory and practice. Understanding the structure of solutions of IPs is thus helpful to argue about the existence of solutions with a certain simple structure, ...

SPRINGER INTERNATIONAL PUBLISHING AG2018

A reconfiguration strategy for modular robots using origami folding

Jamie Paik, Christoph Heinrich Belke, Meibao Yao

Reconfigurability in versatile systems of modular robots is achieved by changing the morphology of the overall structure as well as by connecting and disconnecting modules. Recurrent connectivity changes can cause misalignment that leads to mechanical fail ...

2018

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of th ...

ASSOC COMPUTING MACHINERY2018

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Justin Dean Ward

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or ...

INFORMS2017

Information Structure Design in Team Decision Problems

Maryam Kamgarpour, Tyler Summers

We consider a problem of information structure design in team decision problems and team games. We propose simple, scalable greedy algorithms for adding a set of extra information links to optimize team performance and resilience to non-cooperative and adv ...

2017

Greedy algorithm

Graph Chatbot

Chat with Graph Search

Freight railway network design problem

Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints

Approximating Steiner trees and forests with minimum number of Steiner points

Constant factor approximation for ATSP with two edge weights

Using Structural Properties for Integer Programs

A reconfiguration strategy for modular robots using origami folding

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Information Structure Design in Team Decision Problems

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Approximating Steiner trees and forests with minimum number of Steiner points

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Information Structure Design in Team Decision Problems

Freight railway network design problem

Constant factor approximation for ATSP with two edge weights

Using Structural Properties for Integer Programs

A reconfiguration strategy for modular robots using origami folding