The transportation problem with exclusionary side constraints

We consider the so-called Transportation Problem with Exclusionary Side Constraints (TPESC), which is a generalization of the ordinary transportation problem. We confirm that the TPESC is NP-hard, and we analyze the complexity of different special cases. For instance, we show that in case of a bounded number of suppliers, a pseudo-polynomial time algorithm exists, whereas the case of two demand nodes is already hard to approximate within a constant factor (unless P = NP). This research was partially supported by FWO Grant No. G.0114.03.     

Integer knapsack problems with set-up weights

The Integer Knapsack Problem with Set-up Weights (IKPSW) is a generalization of the classical Integer Knapsack Problem (IKP), where each item type has a set-up weight that is added to the knapsack if any copies of the item type are in the knapsack solution. The k-item IKPSW (kIKPSW) is also considered, where a cardinality constraint imposes a value k on the total number of items in the knapsack solution. IKPSW and kIKPSW have applications in the area of aviation security. This paper provides dynamic programming algorithms for each problem that produce optimal solutions in pseudo-polynomial time. Moreover, four heuristics are presented that provide approximate solutions to IKPSW and kIKPSW. For each problem, a Greedy heuristic is presented that produces solutions within a factor of 1/2 of the optimal solution value, and a fully polynomial time approximation scheme (FPTAS) is presented that produces solutions within a factor of ε of the optimal solution value. The FPTAS for IKPSW has time and space requirements of O(nlog n+n/ε ²+1/ε ³) and O(1/ε ²), respectively, and the FPTAS for kIKPSW has time and space requirements of O(kn ²/ε ³) and O(k/ε ²), respectively.     

An approximation algorithm for the wireless gathering problem

The Wireless Gathering Problem is to find an interference-free schedule for data gathering in a wireless network in minimum time. We present a 4-approximate polynomial-time on-line algorithm for this NP-hard problem. We show that no shortest path following algorithm can have an approximation ratio better than 4.     

NP-Complete operations research problems and approximation algorithms

For a large number of discrete optimization problems like the traveling salesman problem, the quadratic assignment problem, the general flow-shop problem, the knapsack problem etc. all known algorithms have the discouraging property that their (worst-case) running times on a computer grow exponentially with the size of the problem. All efforts to find polynomial bounded algorithms for these problems have failed. Recent results in complexity theory show that these problems belong to the classes ofNP-complete orNP-hard problems. It is a common belief that for problems belonging to these classes no polynomial bounded algorithms exist. Heuristics or approximation algorithms should be applied to these problems.The aim of this tutorial paper is to give a survey onNP-complete andNP-hard problems and on approximation algorithms. All concepts introduced are illustrated by examples which are closely related to the knapsack problem and can be understood easily. References to most other problems of interest to operations researchers are given.

---

Zusammenfassung Für eine große Anzahl von diskreten Optimierungsproblemen wie das Traveling Salesman Problem, das quadratische Zuordnungsproblem, das allgemeine Flowshop Problem, das Rucksackproblem usw. haben alle bisherigen Lösungsansätze die unangenehme Eigenschaft, daß der Rechenumfang der entsprechenden Algorithmen exponentiell mit dem Umfang der Probleme wächst. Alle Bemühungen polynomial beschränkte Verfahren für solche Probleme zu finden waren bislang ergebnislos. Neuere Ergebnisse der Komplexitätstheorie besagen, daß diese Probleme zu den Klassen derNP-vollständigen bzw.NP-schwierigen Probleme gehören und somit nach allgemein verbreiteter Auffassung wohl niemals polynomial lösbar sein werden. Die Anwendung von heuristischen Verfahren oder approximativen Algorithmen scheint der einzige Ausweg in dieser Situation.Ziel der Arbeit ist es, einen einführenden Uberblick über die Theorie derNP-vollständigen undNP-schwierigen Probleme sowie über approximative Verfahren zu geben. Alle in der Arbeit einge-führten Begriffe werden an einfach verständlichen Beispielen erläutert, die eng mit dem Rucksack-problem verwandt sind.Für weitere Probleme, die den Unternehmensforscher interessieren, findet der Leser ausführliche Literaturübersichten.

---

---

An invited survey.     

Multilevel Monte Carlo for stochastic differential equations with additive fractional noise

We adopt the multilevel Monte Carlo method introduced by M. Giles (Multilevel Monte Carlo path simulation, Oper. Res. 56(3):607–617, 2008) to SDEs with additive fractional noise of Hurst parameter H>1/2. For the approximation of a Lipschitz functional of the terminal state of the SDE we construct a multilevel estimator based on the Euler scheme. This estimator achieves a prescribed root mean square error of order ε with a computational effort of order ε ⁻².     

On the Union of Cylinders in Three Dimensions

We show that the combinatorial complexity of the union of n infinite cylinders in ℝ³, having arbitrary radii, is O(n ^2+ε ), for any ε>0; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000), who established a nearly-quadratic bound for the restricted case of nearly congruent cylinders. Our result extends, in a significant way, the result of Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000), in particular, a simple specialization of our analysis to the case of nearly congruent cylinders yields a nearly-quadratic bound on the complexity of the union in that case, thus significantly simplifying the analysis in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000). Finally, we extend our technique to the case of “cigars” of arbitrary radii (that is, Minkowski sums of line-segments and balls) and show that the combinatorial complexity of the union in this case is nearly-quadratic as well. This problem has been studied in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000) for the restricted case where all cigars have (nearly) equal radii. Based on our new approach, the proof follows almost verbatim from the analysis for infinite cylinders and is significantly simpler than the proof presented in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000).     

New Models of the Generalized Minimum Spanning Tree Problem

We consider a generalization of the Minimum Spanning Tree Problem, called the Generalized Minimum Spanning Tree Problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present a stronger result regarding its complexity, namely, the GMST problem is NP-hard even on trees as well an exact exponential time algorithm for the problem based on dynamic programming. We describe new mixed integer programming models of the GMST problem, mainly containing a polynomial number of constraints. We establish relationships between the polytopes corresponding to their linear relaxations. Based on a new model of the GMST we present a solution procedure that solves the problem to optimality for graphs with nodes up to 240. We discuss the advantages of our method in comparison with earlier methods.     

Customer order scheduling to minimize the number of late jobs

In the order scheduling problem, every job (order) consists of several tasks (product items), each of which will be processed on a dedicated machine. The completion time of a job is defined as the time at which all its tasks are finished. Minimizing the number of late jobs was known to be strongly NP-hard. In this note, we show that no FPTAS exists for the two-machine, common due date case, unless P = NP. We design a heuristic algorithm and analyze its performance ratio for the unweighted case. An LP-based approximation algorithm is presented for the general multicover problem. The algorithm can be applied to the weighted version of the order scheduling problem with a common due date.     

Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries

We study a supply chain scheduling problem, where a common due date is assigned to all jobs and the number of jobs in delivery batches is constrained by the batch size. Our goal is to minimize the sum of the weighted number of tardy jobs, the due-date-assignment costs and the batch-delivery costs. We show that some well-known NP\mathcal{NP}-hard problems reduce to our problem. Then we propose a pseudo-polynomial algorithm for the problem, establishing that it is NP\mathcal{NP}-hard only in the ordinary sense. Finally, we convert the algorithm into an efficient fully polynomial time approximation scheme.     

A Non-linear Lower Bound for Planar Epsilon-nets

We show that the minimum possible size of an ε-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in \frac1e\frac{1}{\epsilon}. This settles a problem raised by Matoušek, Seidel and Welzl (Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16–22, 1990).     

An efficient representation of Benes networks and its applications

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications.     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.     

Removing Degeneracy in LP-Type Problems Revisited

LP-type problems is a successful axiomatic framework for optimization problems capturing, e.g., linear programming and the smallest enclosing ball of a point set. In Matoušek and Škovroň (Theory Comput. 3:159–177, 2007), it is proved that in order to remove degeneracies of an LP-type problem, we sometimes have to increase its combinatorial dimension by a multiplicative factor of at least 1+ε with a certain small positive constant ε. The proof goes by checking the unsolvability of a system of linear inequalities, with several pages of calculations. Here by a short topological argument we prove that the dimension sometimes has to increase at least twice. We also construct 2-dimensional LP-type problems with −∞ for which removing degeneracies forces arbitrarily large dimension increase.     

Justification of a quasistationary approximation for the Stefan problem

Unique solvability of the one-phase Stefan problem with a small multiplier ε at the time derivative in the equation is proved on a certain time interval independent of ε for ε ∈ (0, ε₀). The solution to the Stefan problem is compared with the solution to the Hele-Show problem, which describes the process of melting materials with zero specific heat ε and can be regarded as a quasistationary approximation for the Stefan problem. It is shown that the difference of the solutions has order . This provides a justification of the quasistationary approximation. Bibliography: 23 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 348, 2007, pp. 209–253.     

Bootstrap Approximation to Distributions of Finite Population U-statistics

We show that the without replacement bootstrap of Booth, Butler and Hall (J. Am. Stat. Assoc. 89, 1282–1289, 1994) provides second order correct approximation to the distribution function of a Studentized U-statistic based on simple random sample drawn without replacement. In order to achieve similar approximation accuracy for the bootstrap procedure due to Bickel and Freedman (Ann. Stat. 12, 470–482, 1984) and Chao and Lo (Sankhya Ser. A 47, 399–405, 1985) we introduce randomized adjustments to the resampling fraction.      

Construction of Solutions and L^1-error Estimates of Viscous Methods for Scalar Conservation Laws with Boundary

This paper is concerned with an initial boundary value problem for strictly convex conservation laws whose weak entropy solution is in the piecewise smooth solution class consisting of finitely many discontinuities. By the structure of the weak entropy solution of the corresponding initial value problem and the boundary entropy condition developed by Bardos-Leroux Nedelec, we give a construction method to the weak entropy solution of the initial boundary value problem. Compared with the initial value problem, the weak entropy solution of the initial boundary value problem includes the following new interaction type： an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary. According to the structure and some global estimates of the weak entropy solution, we derive the global L^1-error estimate for viscous methods to this initial boundary value problem by using the matching travelling wave solutions method. If the inviscid solution includes the interaction that an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary, or the inviscid solution includes some shock wave which is tangent to the boundary, then the error of the viscosity solution to the inviscid solution is bounded by O（ε^1/2） in L^1-norm; otherwise, as in the initial value problem, the L^1-error bound is O（ε｜ In ε｜）.