Publications related to A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings

Learning to Remove Cuts in Integer Linear Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional opti ...

2024

Decision Procedures for Power Structures

Rodrigo Raya

We study the decision problem for the existential fragment of the theory of power structures. We prove complexity results that parallel the decidability results of Feferman-Vaught for the theories of product structures thereby showing that the construction ...

EPFL2023

Removing Algorithmic Discrimination (With Minimal Individual Error)

Rachid Guerraoui, El Mahdi El Mhamdi, Alexandre David Olivier Maurer, Le Nguyen Hoang

We address for the first time the problem of correcting group discriminations within a score function, while minimizing the individual error. Each group is described by a probability density function on the set of profiles. We first solve the problem analy ...

2022

Removing algorithmic discrimination (with minimal individual error)

Rachid Guerraoui, El Mahdi El Mhamdi, Alexandre David Olivier Maurer, Le Nguyen Hoang

We address for the first time the problem of correcting group discriminations within a score function, while minimizing the individual error. Each group is described by a probability density function on the set of profiles. We first solve the problem analy ...

ELSEVIER2022

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Friedrich Eisenbrand, Moritz Andreas Venzin, Jana Tabea Cslovjecsek

We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021

Realizability of planar point embeddings from angle measurements

Majed El Helou, Adam James Scholefield, Frederike Dümbgen

Localization of a set of nodes is an important and a thoroughly researched problem in robotics and sensor networks. This paper is concerned with the theory of localization from inner-angle measurements. We focus on the challenging case where no anchor loca ...

2020

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2020

Complexity of linear relaxations in integer programming

Matthias Schymura

For a set X of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with X is called the relaxation complexity rc(X). This parameter was introduced by Kaibel & Weltge (2015) and captures the ...

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

Axiomatic scale theory

Martin Alois Rohrmeier, Daniel Harasim

Scales are a fundamental concept of musical practice around the world. They commonly exhibit symmetry properties that are formally studied using cyclic groups in the field of mathematical scale theory. This paper proposes an axiomatic framework for mathema ...

TAYLOR & FRANCIS LTD2020

A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings

Graph Chatbot

Chat with Graph Search

Learning to Remove Cuts in Integer Linear Programming

Decision Procedures for Power Structures

Removing Algorithmic Discrimination (With Minimal Individual Error)

Removing algorithmic discrimination (with minimal individual error)

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Realizability of planar point embeddings from angle measurements

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Complexity of linear relaxations in integer programming

New Results in Integer and Lattice Programming

Axiomatic scale theory

Removing algorithmic discrimination (with minimal individual error)

Removing Algorithmic Discrimination (With Minimal Individual Error)

Learning to Remove Cuts in Integer Linear Programming

New Results in Integer and Lattice Programming

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Complexity of linear relaxations in integer programming

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Realizability of planar point embeddings from angle measurements

Axiomatic scale theory

Decision Procedures for Power Structures