Publications related to New Graph Algorithms via Polyhedral Techniques

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

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Nisheeth Vishnoi, Javad Ebrahimi Boroojeni, Damian Mateusz Straszak

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v(1), ..., v(m) is an element of R-d and a constraint family B subset of 2([m]), find a set S. B that maximizes the squared volume of the sim ...

Ieee2017

An integer programming approach to scheduling the transshipment of products at cross-docks in less-than-truckload industries

Mohammad Yousef Maknoon

This paper introduces an exact method to schedule the internal transshipment process at cross-docks in less-than-truckload industries. An integer programming formulation is presented to minimize the cost of double handling by synchronizing two types of dec ...

Pergamon-Elsevier Science Ltd2017

Maximizing Symmetric Submodular Functions

Moran Feldman

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases, including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little attention by c ...

Association for Computing Machinery2017

Efficient Linear Programming for Dense CRFs

Mathieu Salzmann

The fully connected conditional random field (CRF) with Gaussian pairwise potentials has proven popular and effective for multi-class semantic segmentation. While the energy of a dense CRF can be minimized accurately using a linear programming (LP) relaxat ...

2017

A Distributed Algorithm for Partitioned Robust Submodular Maximization

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

Abstract—In this paper, we consider the problem of maximizing a monotone submodular function subject to a cardinality constraint, with two added twists: The computation is distributed across a number of machines, and we require the solution to be robust ag ...

2017

Recompression Of Hadamard Products Of Tensors In Tucker Format

Daniel Kressner, Lana Perisa

The Hadamard product features prominently in tensor-based algorithms in scientific computing and data analysis. Due to its tendency to significantly increase ranks, the Hadamard product can represent a major computational obstacle in algorithms based on lo ...

Siam Publications2017

Many disjoint edges in topological graphs

Andres Jacinto Ruiz Vargas

A monotone cylindrical graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called simple if any pair of its edges have at most one ...

Elsevier Science Bv2017

GDSP: A graphical perspective on the distributed storage systems

Michael Christoph Gastpar, Saeid Sahraei

The classical distributed storage problem can be modeled by a k-uniform complete hyper-graph where vertices represent servers and hyper-edges represent users. Hence each hyper-edge should be able to recover the full file using only the memories of the vert ...

2017

Independence number of generalized Petersen graphs

Javad Ebrahimi Boroojeni

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed towa ...

Charles Babbage Res Ctr2016

New Graph Algorithms via Polyhedral Techniques

Graph Chatbot

Chat with Graph Search

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

An integer programming approach to scheduling the transshipment of products at cross-docks in less-than-truckload industries

Maximizing Symmetric Submodular Functions

Efficient Linear Programming for Dense CRFs

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Recompression Of Hadamard Products Of Tensors In Tucker Format

Many disjoint edges in topological graphs

GDSP: A graphical perspective on the distributed storage systems

Independence number of generalized Petersen graphs

Independence number of generalized Petersen graphs

Maximizing Symmetric Submodular Functions

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Recompression Of Hadamard Products Of Tensors In Tucker Format

An integer programming approach to scheduling the transshipment of products at cross-docks in less-than-truckload industries

Efficient Linear Programming for Dense CRFs

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Many disjoint edges in topological graphs

GDSP: A graphical perspective on the distributed storage systems