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

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

Abstract

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 generalizes to problems in scheduling, network design and capacited location, its dynamic programming approaches do not. One often relies on strong polyhedral relaxations for corresponding integer programs instead. Among other results, we construct such a relaxation for the time-invariant incremental knapsack problem (IIK), and study classes of valid inequalities for MinKnap.

IIK is covered in the first part of this thesis. It is a generalization of the max-knapsack problem to a discrete multi-period setting. At each time, capacity increases and items can be added, but not removed from the knapsack. The goal is to maximize the sum of profits over all times. IIK models scenarios in specific financial markets and governmental decision processes. It is known to be strongly NP-hard and there has been work on approximation algorithms for special cases. We settle the complexity of IIK by designing a PTAS, and provide several extensions of the technique.

The second part is on MinKnap and divided into two chapters. One is motivated by a recent work on disjunctive relaxations for MinKnap with fixed objective function, where we reduce the size of the construction. The other focuses on a class of bounded pitch inequalities, that generalize the unweighted cover inequalities for MinKnap. While separating over pitch-1 inequalities is NP-hard, we show that approximate separation over the set of pitch-1 and pitch-2 inequalities can be done in polynomial time. We also investigate integrality gaps of linear relaxations for MinKnap when these inequalities are added. Consequently we show that, for any fixed t, the t-th CG closure of the natural relaxation has unbounded gap.

The last chapter deals with questions in clustered planarity testing. The Hanani-Tutte theorem is a classical result that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. We conclude by a short proof, using matroid intersection, for a result by Di Battista and Frati on embedded clustered graphs.

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 concepts (7)

Time

Time is the continued sequence of existence and events that occurs in an apparently irreversible succession from the past, through the present, into the future. It is a component quantity of various measurements used to sequence events, to compare the duration of events or the intervals between them, and to quantify rates of change of quantities in material reality or in the conscious experience. Time is often referred to as a fourth dimension, along with three spatial dimensions.

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.