Publications related to NP-completeness

Steiner Tree Approximation via Iterative Randomized Rounding

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

Constrained Binary Identification Problem

Amin Karbasi, Morteza Zadimoghaddam

We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the “20 questions game” of information theory and is closely related to lossless so ...

2013

On Repairing Ill-Typed Expressions

Tihomir Gvero, Ivan Kuraj, Ruzica Piskac

When developing code, a programmer typically knows the approximate structure of the desired expression. However, often the first attempt at writing it down results in an ill-typed code fragment. We propose an approach that automatically repairs code expres ...

2013

An overview of the Leon verification system: verification by translation to recursive functions

Viktor Kuncak, Etienne Kneuss, Régis William Blanc, Philippe Paul Henri Suter

We present the Leon verification system for a subset of the Scala programming language. Along with several functional features of Scala, Leon supports imperative constructs such as mutations and loops, using a translation into recursive functional form. Bo ...

2013

Detection of Floods In Sar Images with Non-Linear Kernel Clustering and Topographic Prior

Jean-Philippe Thiran, Devis Tuia, Frank Grégoire Jean de Morsier, Maurice Borgeaud

After a major flood catastrophe, a precious information is the delineation of the affected areas. Remote sensing imagery, especially synthetic aperture radar, allows to obtain a global and complete view of the situation. However, the detection of the flood ...

2013

Overview of New Approaches for Approximating TSP

Ola Nils Anders Svensson

n this extended abstract, we survey some of the recent results on approximating the traveling salesman problem on graphic metrics. We start by briefly explaining the algorithm of Oveis Gharan et al. [1] that has strong similarities to Christofides’ famo ...

Springer2013

Effects of ZnO film growth route and nanostructure on electron transport and recombination in dye-sensitized solar cells

Michael Graetzel, Thomas Moehl

The photovoltaic performances of ZnO-based dye-sensitized solar cells (DSSCs) have been studied for ZnO porous films prepared by different techniques. A comparison is made between nanoparticle (NP) films prepared by a sol-gel method and two different elect ...

Royal Society of Chemistry2013

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\mathbb{F}_{2^{1971}}$ and $\mathbb{F}_{2^{3164}}$

Robert Granger, Jens Markus Zumbrägel

In this paper we propose a binary field variant of the Joux-Lercier medium-sized Function Field Sieve, which results not only in complexities as low as

L_{q^n}(1/3,(4/9)1/3)

for computing arbitrary logarithms, but also in an heuristic polynomial time alg ...

Springer Berlin Heidelberg2013

Nanoparticle actuated hollow drug delivery vehicles

Esther Amstad

The trend towards personalized medicine and the long-standing wish to reduce drug consumption and unwanted side effects have been the driving force behind research on drug delivery vehicles that control localization, timing and dose of released cargo. Cont ...

2012

Pliable Index Coding

Christina Fragouli, Siddhartha Brahma

We propose a new formulation of the index coding problem, where instead of demanding a specific message, clients are “pliable” and are happy to receive any one message they do not have. We prove that with this relaxation, although some instances of this pr ...

Ieee2012

NP-completeness

Graph Chatbot

Chat with Graph Search

Steiner Tree Approximation via Iterative Randomized Rounding

Constrained Binary Identification Problem

On Repairing Ill-Typed Expressions

An overview of the Leon verification system: verification by translation to recursive functions

Detection of Floods In Sar Images with Non-Linear Kernel Clustering and Topographic Prior

Overview of New Approaches for Approximating TSP

Effects of ZnO film growth route and nanostructure on electron transport and recombination in dye-sensitized solar cells

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\mathbb{F}_{2^{1971}}$ and $\mathbb{F}_{2^{3164}}$

Nanoparticle actuated hollow drug delivery vehicles

Pliable Index Coding

Steiner Tree Approximation via Iterative Randomized Rounding

Constrained Binary Identification Problem

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\mathbb{F}_{2^{1971}}$ and $\mathbb{F}_{2^{3164}}$

On Repairing Ill-Typed Expressions

Detection of Floods In Sar Images with Non-Linear Kernel Clustering and Topographic Prior

Nanoparticle actuated hollow drug delivery vehicles

Overview of New Approaches for Approximating TSP

An overview of the Leon verification system: verification by translation to recursive functions

Effects of ZnO film growth route and nanostructure on electron transport and recombination in dye-sensitized solar cells

Pliable Index Coding