Publications related to Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids

Streaming and Matching Problems with Submodular Functions

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input consists of a set of jobs, characterized by their processing times, release time ...

ASSOC COMPUTING MACHINERY2021

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

Symbolic Algorithms for Token Swapping

Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...

2020

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

ASSOC COMPUTING MACHINERY2020

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

Entropic Matroids and Their Representation

Emmanuel Abbé

This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have support of cardinality p. We draw ...

2019

An Improved Analysis of Local Search for Max-Sum Diversification

Friedrich Eisenbrand, Rico Zenklusen, Alfonso Bolívar Cevallos Manzano

We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so th ...

INFORMS2019

On 2-Level Polytopes Arising In Combinatorial Settings

Yuri Faenza, Manuel Francesco Aprile, Alfonso Bolívar Cevallos Manzano

2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some 2-level polytopes arisi ...

SIAM PUBLICATIONS2018

Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids

Graph Chatbot

Chat with Graph Search

Streaming and Matching Problems with Submodular Functions

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

New Results in Integer and Lattice Programming

Symbolic Algorithms for Token Swapping

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

New Graph Algorithms via Polyhedral Techniques

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Entropic Matroids and Their Representation

An Improved Analysis of Local Search for Max-Sum Diversification

On 2-Level Polytopes Arising In Combinatorial Settings

Streaming and Matching Problems with Submodular Functions

New Results in Integer and Lattice Programming

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

New Graph Algorithms via Polyhedral Techniques

An Improved Analysis of Local Search for Max-Sum Diversification

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Entropic Matroids and Their Representation

On 2-Level Polytopes Arising In Combinatorial Settings

Symbolic Algorithms for Token Swapping