Publications related to Set cover problem

Convergence of a stabilized discontinuous Galerkin method for incompressible nonlinear elasticity

Alfio Quarteroni, Ricardo Esteban Ruiz Baier, Davide Baroli

In this paper we present a discontinuous Galerkin method applied to incompressible nonlinear elastostatics in a total Lagrangian deformation-pressure formulation, for which a suitable interior penalty stabilization is applied. We prove that the proposed di ...

Springer Verlag2013

Completeness and Ambiguity of Schema Cover

Karl Aberer, Quoc Viet Hung Nguyen, Zoltán Miklós

Given a schema and a set of concepts, representative of entities in the domain of discourse, schema cover deﬁnes correspondences between concepts and parts of the schema. Schema cover aims at interpreting the schema in terms of concepts and thus, vastly si ...

2013

Steiner Tree Approximation via Iterative Randomized Rounding

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem w ...

Assoc Computing Machinery2013

A local search heuristic for a mixed integer nonlinear integrated airline schedule planning problem

Michel Bierlaire, Matteo Salani, Bilge Atasoy

In this paper we present a local search heuristic method for an integrated airline scheduling, fleeting and pricing model. The integrated model simultaneously optimizes the decisions of schedule design, fleet assignment, seat allocation, pricing and consid ...

2013

New Results in the Theory of Linear and Integer Programming

Nicolai Hähnle

The polynomial Hirsch conjecture states that the vertex-edge diameter of a d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. For the special case where the polyhedron is defined as the set of points satisfying a system Ax ≤ b of ...

EPFL2012

On stable self-similar blow up for equivariant wave maps: The linearized problem

Roland Donninger

We consider co-rotational wave maps from (3+1) Minkowski space into the three-sphere. This is an energy supercritical model which is known to exhibit finite time blow up via self-similar solutions. The ground state self-similar solution

f_0

is known in c ...

2012

Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability

Ola Nils Anders Svensson, Klaus Jansen

We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objecti ...

Assoc Computing Machinery2012

Optimizing Mixing in Pervasive Networks: A Graph-Theoretic Perspective

Jean-Pierre Hubaux, Murtuza Jadliwala, Igor Bilogrevic

One major concern in pervasive wireless applications is location privacy, where malicious eavesdroppers, based on static device identifiers, can continuously track users. As a commonly adopted countermeasure to prevent such identifier-based tracking, devic ...

Springer2011

Covering Cubes and the Closest Vector Problem

Friedrich Eisenbrand, Martin Niemeier, Nicolai Hähnle

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest vector problem in the infinity-norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2^(O(n))(log(1/epsilon ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut

Ola Nils Anders Svensson

We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approxima ...

Society for Industrial and Applied Mathematics2011

Set cover problem

Graph Chatbot

Chat with Graph Search

Convergence of a stabilized discontinuous Galerkin method for incompressible nonlinear elasticity

Completeness and Ambiguity of Schema Cover

Steiner Tree Approximation via Iterative Randomized Rounding

A local search heuristic for a mixed integer nonlinear integrated airline schedule planning problem

New Results in the Theory of Linear and Integer Programming

On stable self-similar blow up for equivariant wave maps: The linearized problem

Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability

Optimizing Mixing in Pervasive Networks: A Graph-Theoretic Perspective

Covering Cubes and the Closest Vector Problem

Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut

Steiner Tree Approximation via Iterative Randomized Rounding

New Results in the Theory of Linear and Integer Programming

Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut

On stable self-similar blow up for equivariant wave maps: The linearized problem

Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability

A local search heuristic for a mixed integer nonlinear integrated airline schedule planning problem

Completeness and Ambiguity of Schema Cover

Optimizing Mixing in Pervasive Networks: A Graph-Theoretic Perspective

Convergence of a stabilized discontinuous Galerkin method for incompressible nonlinear elasticity

Covering Cubes and the Closest Vector Problem