The inverse Fermat–Weber problem

Given n points in the plane with nonnegative weights, the inverse Fermat–Weber problem consists in changing the weights at minimum cost such that a prespecified point in the plane becomes the Euclidean 1-median. The cost is proportional to the increase or decrease of the corresponding weight. In case that the prespecified point does not coincide with one of the given n points, the inverse Fermat–Weber problem can be formulated as linear program. We derive a purely combinatorial algorithm which solves the inverse Fermat–Weber problem with unit cost using O(n) greedy-like iterations where each of them can be done in constant time if the points are sorted according to their slopes. If the prespecified point coincides with one of the given n points, it is shown that the corresponding inverse problem can be written as convex problem and hence is solvable in polynomial time to any fixed precision.     

Continuous model for software reliability demonstration testing considering damage size of software failures

This study proposes a continuous model for software reliability demonstration testing, which takes the damage size of software failures into consideration. In the proposed procedure, the software being tested is accepted if the number of software failures does not exceed a prespecified value, s and if the total damage size of software failures is less than another prespecified value, d. Based on the producer's and consumer's risks, an algorithm for designing a software reliability demonstration test is discussed.     

Inverse 1-median problem on trees under weighted Hamming distance

The inverse 1-median problem consists in modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. A linear time algorithm is first proposed for the inverse problem under weighted l _?? norm. Then two polynomial time algorithms with time complexities O(n log n) and O(n) are given for the problem under weighted bottleneck-Hamming distance, where n is the number of vertices. Finally, the problem under weighted sum-Hamming distance is shown to be equivalent to a 0-1 knapsack problem, and hence is ${\mathcal{NP}}$ -hard.     

Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees

This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(r_vnlogn) time where the parameter r_v is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang.     

Existence and regularity of the solution of a mixed boundary value problem for the Keldysh equation with a nonlinear absorption term

The Keldysh equation is a more general form of the classic Tricomi equation from fluid dynamics. Its well-posedness and the regularity of its solution are interesting and important. The Keldysh equation is elliptic in y>0 and is degenerate at the line y=0 in R². Adding a special nonlinear absorption term, we study a nonlinear degenerate elliptic equation with mixed boundary conditions in a piecewise smooth domain—similar to the potential fluid shock reflection problem. By means of an elliptic regularization technique, a delicate a priori estimate and compact argument, we show that the solution of a mixed boundary value problem of the Keldysh equation is smooth in the interior and Lipschitz continuous up to the degenerate boundary under some conditions. We believe that this kind of regularity result for the solution will be rather useful.     

Bicriteria sequencing methods for the mixed-model assembly line in just-in-time production systems

A mixed-model manufacturing facility operating in a pull production environment can be controlled by setting a production schedule only for the last process in the facility which is usually an assembly line of mixed-model type. In the mixed-model sequencing problems, two major goals are considered: (1) smoothing the workload on each workstation on the assembly line, and (2) keeping a constant rate of usage of all parts used on the assembly line. In this study, first, some well-known solution approaches with goal 2 are analyzed through minimizing the sum-of-deviations of actual production from the desired amount. The approaches that are found to be performing better than the others are extended for the bicriteria problem considering goals 1 and 2, simultaneously. It is also shown that the bicriteria problem with the sum-of-deviations type objective function can also be formulated as an assignment problem, and the optimal solution to the small-sized problems can thus be obtained by solving the assignment problem. Finally, the conditions when it is important to take the workload-smoothing goal into consideration are analyzed.     

A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case

In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to find the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m⁵logm).     

A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem

In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation of the minimum-adjacency vertex coloring problem which, given an interference graph $G$ representing the potential interference between the antennas and a set of prespecified colors/channels, asks for a vertex coloring of $G$ minimizing the number of edges receiving adjacent colors. We propose an integer programming model for this problem and present three families of facet-inducing valid inequalities. Based on these results, we implement a branch-and-cut algorithm for this problem, and we provide promising computational results.     

Rectilinear line segment intersection,layered segment trees,and dynamization

The aim of the present paper is to provide an efficient solution to the following problem: “Given a family of n rectilinear line segments in two-space report all intersections in the family with a query consisting of an arbitrary rectilinear line segment.” We provide an algorithm which takes O(nlog₂n) preprocessing time, o(nlog₂n) space and O(log₂n + k) query time, where k is the number of reported intersections. This solution serves to introduce a powerful new data structure, the layered segment tree, which is of independent interest. Second it yields, by way of recent dynamization techniques, a solution to the on-line version of the above problem, that is the operations INSERT and DELETE and QUERY with a line segment are allowed. Third it also yields a new nonscanning solution to the batched version of the above problem. Finally we apply these techniques to the problem obtained by replacing “line segment” by “rectangle” in the above problem, giving an efficient solution in this case also.     

An Uncertainty Principle of Paley and Wiener on Euclidean Motion Group

A classical result due to Paley and Wiener characterizes the existence of a non-zero function in \(L^2(\mathbb {R}),\) supported on a half line, in terms of the decay of its Fourier transform. In this paper we prove an analogue of this result for compactly supported continuous functions on the Euclidean motion group M(n). We also relate this result to a unique continuation property of solutions to the initial value problem for time-dependent Schrödinger equation on M(n).     

Quickest online selection of an increasing subsequence of specified size

Given a sequence of independent random variables with a common continuous distribution, we consider the online decision problem where one seeks to minimize the expected value of the time that is needed to complete the selection of a monotone increasing subsequence of a prespecified length n. This problem is dual to some online decision problems that have been considered earlier, and this dual problem has some notable advantages. In particular, the recursions and equations of optimality lead with relative ease to asymptotic formulas for mean and variance of the minimal selection time. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 235–252, 2016     

The parameterized complexity of the induced matching problem

Given a graph G and an integer k≥0, the NP-complete Induced Matching problem asks whether there exists an edge subset M of size at least k such that M is a matching and no two edges of M are joined by an edge of G. The complexity of this problem on general graphs, as well as on many restricted graph classes has been studied intensively. However, other than the fact that the problem is W[1]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs.     

Algorithms for projecting a point onto a level surface of a continuous function on a compact set

Given an equation f(x) = 0, the problem of finding its solution nearest to a given point is considered. In contrast to the authors’ previous works dealing with this problem, exact algorithms are proposed assuming that the function f is continuous on a compact set. The convergence of the algorithms is proved, and their performance is illustrated with test examples.     

On the splitting problem for selections

We investigate when does the Repovš-Semenov splitting problem for selections have an affirmative solution for continuous set-valued mappings in finite-dimensional Banach spaces. We prove that this happens when images of set-valued mappings or even their graphs are P-sets (in the sense of Balashov) or strictly convex sets. We also consider an example which shows that there is no affirmative solution of this problem even in the simplest case in R³. We also obtain affirmative solution of the approximate splitting problem for Lipschitz continuous selections in the Hilbert space.     

A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times

Consider an m-machine production line for processing identical parts served by a mobile robot. The problem is to find the minimum cycle time for 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. This work treats a special case of the 2-cyclic robot scheduling problem when the robot route is given and the operation durations are to be chosen from prescribed intervals. The problem was previously proved to be polynomially solvable in O(m⁸log m) time. This paper proposes an improved algorithm with reduced complexity O(m⁴).     

Existence and regularity of solution of mixed boundary value problem of a Busemann-equation with nonlinear absorb term

The Busemann-equation is a classical equation coming from fluid dynamics. The well-posed problem and regularity of solution of Busemann-equation with nonlinear term are interesting and important. The Busemann-equation is elliptic in y>0 and is degenerate at the line y=0 in R². With a special nonlinear absorb term, we study a nonlinear degenerate elliptic equation with mixed boundary conditions in a piecewise smooth domain. By means of elliptic regularization technique, a delicate prior estimate and compact argument, we show that the solution of mixed boundary value problem of Busemann-equation is smooth in the interior and Lipschitz continuous up to the degenerate boundary on some conditions. The result is better than the result of classical boundary degenerate elliptic equation.     

Minmax-distance approximation and separation problems: geometrical properties

A center hyperplane in the d-dimensional space minimizes the maximum of its distances from a finite set of points A with respect to possibly different gauges. In this note it is shown that a center hyperplane exists which is at (equal) maximum distance from at least d?+?1 points of A. Moreover the projections of the points among these which lie above the center hyperplane cannot be separated by another hyperplane from the projections of those that are below it. When all gauges involved are smooth, all center hyperplanes satisfy these properties. This geometric property allows us to improve and generalize previously existing results, which were only known for the case in which all distances are measured using a common norm. The results also extend to the constrained case where for some points it is prespecified on which side of the hyperplane (above, below or on) they must lie. In this case the number of points lying on the hyperplane plus those at maximum distance is at least d?+?1. It follows that solving such global optimization problems reduces to inspecting a finite set of candidate solutions. Extensions of these results to a separation problem are outlined.     

Lower bounds on the worst-case complexity of some oracle algorithms

To give a proper definition of the complexity of very general computational problems such as optimization problems over arbitrary independence systems or fixed-point problems for continuous functions, it is useful to consider the input for these problems as “oracles” R which can be called by the algorithms for some values x ∈ X and which then give back some information R(x) about x, e.g. whether x belongs to the independence system or the point into which x is mapped by the continuous function. A lower bound on the complexity of an algorithm using an oracle R is the number of calls on R in the worst case. Using this technique it is shown that there is no polynomial approximative algorithm for the maximization problem over a general independence system which has a better worst-case behaviour than the greedy algorithm. Moreover several formalizations of the problem of approximating a fixed point of a continuous function are considered, and it is shown that none of these problems can be solved by a bounded algorithm.     

A double smoothing technique for solving unconstrained nondifferentiable convex optimization problems

The aim of this paper is to develop an efficient algorithm for solving a class of unconstrained nondifferentiable convex optimization problems in finite dimensional spaces. To this end we formulate first its Fenchel dual problem and regularize it in two steps into a differentiable strongly convex one with Lipschitz continuous gradient. The doubly regularized dual problem is then solved via a fast gradient method with the aim of accelerating the resulting convergence scheme. The theoretical results are finally applied to an l ₁ regularization problem arising in image processing.     

Lipschitz stability of operators in Banach spaces

We consider approximations of an arbitrarymap F: X → Y between Banach spaces X and Y by an affine operator A: X → Y in the Lipschitz metric: the difference F — A has to be Lipschitz continuous with a small constant ? > 0. In the case Y = ? we show that if F can be affinely ?-approximated on any straight line in X, then it can be globally 2?-approximated by an affine operator on X. The constant 2? is sharp. Generalizations of this result to arbitrary dual Banach spaces Y are proved, and optimality of the conditions is shown in examples. As a corollary we obtain a solution to the problem stated by Zs. Páles in 2008. The relation of our results to the Ulam-Hyers-Rassias stability of the Cauchy type equations is discussed.