Concept

Oriented matroid

Related publications (23)

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

Quadratic serendipity element shape functions on general planar polygons

Xiaodong Wei, Juan Cao

This paper proposes a method for the construction of quadratic serendipity element (QSE) shape functions on planar convex and concave polygons. Existing approaches for constructing QSE shape functions are linear combinations of the pair-wise products of ge ...

ELSEVIER SCIENCE SA2022

Modeling and mitigating supply chain disruptions as a bilevel network flow problem

Anna Timonina-Farkas, René Yves Glogg

Years of globalization, outsourcing and cost cutting have increased supply chain vulnerability calling for more effective risk mitigation strategies. In our research, we analyze supply chain disruptions in a production setting. Using a bilevel optimization ...

SPRINGER HEIDELBERG2022

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

Maryam Kamgarpour, Orcun Karaca

This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and ...

2021

Actuator Placement under Structural Controllability using Forward and Reverse Greedy Algorithms

Maryam Kamgarpour, Tyler Summers, Baiwei Guo, Orcun Karaca

Actuator placement is an active field of research which has received significant attention for its applications in complex dynamical networks. In this paper, we study the problem of finding a set of actuator placements minimizing the metric that measures t ...

2020

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

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 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

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

Graph Chatbot

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.