Publications related to NP-completeness

New Results in Integer and Lattice Programming

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

A Computational Method for Identifying the Optimum Buffer Size in the Era of Zero Defect Manufacturing

Ali Boujemaoui

Decreasing defects, waste time, meeting customer demand and being adaptable are the goals of a Zero Defect Manufacturing (ZDM) strategy. Scheduling is an important tool to perform that. It should take in account buffer size allocation. In this study, a met ...

SPRINGER INTERNATIONAL PUBLISHING AG2020

Second-order guarantees in centralized, federated and decentralized nonconvex optimization

Ali H. Sayed, Stefan Vlaski

Rapid advances in data collection and processing capabilities have allowed for the use of increasingly complex models that give rise to nonconvex optimization problems. These formulations, however, can be arbitrarily difficult to solve in general, in the s ...

INT PRESS BOSTON, INC2020

Catechol Containing Polyelectrolyte Complex Nanoparticles as Local Drug Delivery System for Bortezomib at Bone Substitute Materials

Martin Guillermo Mueller, Jeremy Pak Hei Wong

The proteasome inhibitor bortezomib (BZM) is one of the most potent anti-cancer drugs in the therapy of multiple myeloma. In this study, an adhesive drug delivery system (DDS) for BZM was developed. Therefore, we extended the present DDS concept of polyele ...

2020

Simple Realizability of Complete Abstract Topological Graphs Simplified

Jan Kyncl

An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exac ...

SPRINGER2020

Design of a quality control network for an international food company

Philippe Wieser, Nicolas Zufferey, Simone Lydia Voldrich

In this article, the design of a quality control network is considered in an entire supply chain, in the context of an international food and beverage company, denoted as ABC. For each possible control point of the network, two decisions have to be made: ( ...

TAYLOR & FRANCIS INC2020

Boolean satisfiability in quantum compilation

Giovanni De Micheli, Mathias Soeken, Fereshte Mozafari Ghoraba, Heinz Riener, Giulia Meuli, Bruno Schmitt Antunes

Quantum compilation is the task of translating a quantum algorithm implemented in a high-level quantum programming language into a technology-dependent instructions flow for a physical quantum computer. To tackle the large gap between the quantum program a ...

ROYAL SOC2020

A Crowdsourced Gameplay for Whole-Genome Assembly via Short Reads

Next-generation sequencing has revolutionized the field of genomics by producing accurate, rapid and cost-effective genome analysis with the use of high throughput sequencing technologies. This has intensified the need for accurate and performance efficien ...

INT ASSOC ONLINE ENGINEERING2020

Complete coordination of robotic fiber positioners for massive spectroscopic surveys

Denis Gillet, Jean-Paul Richard Kneib, Matin Macktoobian

Robotic fiber positioners play a vital role in the generation of massive spectroscopic surveys. The more complete a positioners set is coordinated, the more information its corresponding spectrograph receives during an observation. The complete coordinatio ...

2019

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

Igor Malinovic

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

EPFL2019

NP-completeness

Graph Chatbot

Chat with Graph Search

New Results in Integer and Lattice Programming

A Computational Method for Identifying the Optimum Buffer Size in the Era of Zero Defect Manufacturing

Second-order guarantees in centralized, federated and decentralized nonconvex optimization

Catechol Containing Polyelectrolyte Complex Nanoparticles as Local Drug Delivery System for Bortezomib at Bone Substitute Materials

Simple Realizability of Complete Abstract Topological Graphs Simplified

Design of a quality control network for an international food company

Boolean satisfiability in quantum compilation

A Crowdsourced Gameplay for Whole-Genome Assembly via Short Reads

Complete coordination of robotic fiber positioners for massive spectroscopic surveys

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

A Computational Method for Identifying the Optimum Buffer Size in the Era of Zero Defect Manufacturing

Catechol Containing Polyelectrolyte Complex Nanoparticles as Local Drug Delivery System for Bortezomib at Bone Substitute Materials

New Results in Integer and Lattice Programming

Second-order guarantees in centralized, federated and decentralized nonconvex optimization

Simple Realizability of Complete Abstract Topological Graphs Simplified

A Crowdsourced Gameplay for Whole-Genome Assembly via Short Reads

Design of a quality control network for an international food company

Boolean satisfiability in quantum compilation

Complete coordination of robotic fiber positioners for massive spectroscopic surveys

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