ﻻ يوجد ملخص باللغة العربية
The Double Travelling Salesman Problem with Multiple Stacks, DTSPMS, deals with the collect and delivery of n commodities in two distinct cities, where the pickup and the delivery tours are related by LIFO constraints. During the pickup tour, commodities are loaded into a container of k rows, or stacks, with capacity c. This paper focuses on computational aspects of the DTSPMS, which is NP-hard. We first review the complexity of two critical subproblems: deciding whether a given pair of pickup and delivery tours is feasible and, given a loading plan, finding an optimal pair of pickup and delivery tours, are both polynomial under some conditions on k and c. We then prove a (3k)/2 standard approximation for the MinMetrickDTSPMS, where k is a universal constant, and other approximation results for vario
Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval gr
Quantum walks have received a great deal of attention recently because they can be used to develop new quantum algorithms and to simulate interesting quantum systems. In this work, we focus on a model called staggered quantum walk, which employs adva
We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum
In this paper, we present a new, graph-based modeling approach and a polynomial-sized linear programming (LP) formulation of the Boolean satisfiability problem (SAT). The approach is illustrated with a numerical example.
Let $G$ be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of $k$ colors. Suppose that we are given two list edge-colorings $f_0$ and $f_r$ of $G$, and asked whether the