We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...
Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...
Adjustable robust minimization problems where the objective or constraints depend in a convex way on the adjustable variables are generally difficult to solve. In this paper, we reformulate the original adjustable robust nonlinear problem with a polyhedral ...
Future low-carbon societies will need to store vast amounts of electricity to stabilize electricity grids and to power electric vehicles. Vehicle-to-grid allows vehicle owners and grid operators to share the costs of electricity storage by making the batte ...
We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large-scale feature selection problems. Identifying the knockoff distribution requires solving a large-scale semidefinite progra ...
Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...
Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021
A clique covering of a graph G is a set of cliques of G such that any edge of G is contained in one of these cliques, and the weight of a clique covering is the sum of the sizes of the cliques in it. The sigma clique cover number scc(G) of a graph G, is de ...
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 ...
The Fourier-Galerkin method (in short FFTH) has gained popularity in numerical homogenisation because it can treat problems with a huge number of degrees of freedom. Because the method incorporates the fast Fourier transform (FFT) in the linear solver, it ...
We consider solutions to the 2d Navier-Stokes equations on T x R close to the Poiseuille flow, with small viscosity nu > 0. Our first result concerns a semigroup estimate for the linearized problem. Here we show that the x-dependent modes of linear solutio ...
We study the behavior of solutions to the incompressible 2d Euler equations near two canonical shear flows with critical points, the Kolmogorov and Poiseuille flows, with consequences for the associated Navier-Stokes problems. We exhibit a large family of ...
Stochastic optimization is a popular modeling paradigm for decision-making under uncertainty and has a wide spectrum of applications in management science, economics and engineering. However, the stochastic optimization models one faces in practice are int ...
The objective of this thesis is to develop a general methodology to incorporate a disaggregate demand representation in supply-oriented optimization problems that allows to capture the interplay between the behavior of individuals and the decisions to be o ...
A broad class of convex optimization problems can be formulated as a semidefinite program (SDP), minimization of a convex function over the positive-semidefinite cone subject to some affine constraints. The majority of classical SDP solvers are designed fo ...
In this paper, we focus on the problem of minimizing a network of state facilities that provide essential public services (schools, offices, and hospitals). The goal is to reduce the size of the network in order to minimize the costs associated with it. Ho ...
With the ever-growing data sizes along with the increasing complexity of the modern problem formulations, contemporary applications in science and engineering impose heavy computational and storage burdens on the optimization algorithms. As a result, there ...
We consider linear programming (LP) problems in infinite dimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinite-dimensional LP to tractable finite convex programs ...
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 ...
Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear ...
This paper presents a coordinated primal-dual interior point (PDIP) method for solving structured convex linear and quadratic programs (LP-QP) in a distributed man- ner. The considered class of problems represents a multi-agent setting, where the aggregate ...
