**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# Results on Sparse Integer Programming and Geometric Independent Sets

Abstract

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed parameter tractable.One example are block-structured integer programs, which exhibits a (recursive) block structure: The problem decomposes into independent and efficiently solvable sub-problems, if a small number of rows or columns are deleted from the constraint matrix. Prominent examples are 2-stage stochastic integer programs, n-fold integer programs and their generalizations.Previously known algorithms for these problems were based on the augmentation framework, a variant of local search tailored to integer programming. We propose a different approach. We provide new proximity bounds, independent of the number of sub-problems, for both n-fold and 2-stage stochastic integer programming. Further, we show that the relaxation can be solved efficiently via an adaptation of a parametric search framework.We apply our techniques to n-fold and 2-stage integer programming, and integer programming with bounded primal or dual treedepth. For these cases, we obtain strongly polynomial algorithms, which are near-linear in the dimension of the problem. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable.For the second part of this thesis, the focus is shifted to a different NP-hard problem, the maximum (weight) independent set problem. We consider intersection graphs of axis-parallel rectangles or segments, both in the weighted and unweighted case. Given a set of weighted axis-parallel rectangles or segments, the task is to find a subset of pairwise non-intersecting objects with the maximum possible total weight. For weighted rectangles, the best-known polynomial-time approximation algorithm achieves an approximation factor of O(log log (n)). In the unweighted setting, constant factor approximation algorithms are known. It remains open if there are also constant factor approximation algorithms for the weighted setting.We give a parameterized approximation algorithm for finding a maximum weight independent set of axis-parallel rectangles. Given a parameter k, and e>0, the algorithm finds a set of non-overlapping rectangles with weight at least (1-e) opt(k) in 2^O(k log(k/e)) n^O(1/e) time, where opt(k) is the maximum weight of a solution of cardinality at most k. Note that, our algorithm may return a solution consisting of more than k rectangles. To complement this, we also propose a parameterized approximation algorithm for the case of axis-parallel segments. Here the algorithm finds a solution with cardinality at most k and total weight at least (1-e)opt(k) in time 2^O(k^2 log(k/e)) n^O(1).Lastly, we provide a nearly tight bound on the independence number of axis-parallel segments. More precisely, we prove that for any triangle-free intersection graph of n axis-parallel segments in the plane, the independence number of this graph is at least n/4 + c sqrt(n), for an absolute constant c. We complement this with a construction of a graph in this class, with an independence number at most n/4 + d sqrt(n) for an absolute constant d.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related MOOCs (33)

Related concepts (55)

Related publications (266)

Analyse I

Le contenu de ce cours correspond à celui du cours d'Analyse I, comme il est enseigné pour les étudiantes et les étudiants de l'EPFL pendant leur premier semestre. Chaque chapitre du cours correspond

Analyse I (partie 1) : Prélude, notions de base, les nombres réels

Concepts de base de l'analyse réelle et introduction aux nombres réels.

Analyse I (partie 2) : Introduction aux nombres complexes

Introduction aux nombres complexes

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time.

Independent set (graph theory)

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

2023Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

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