An active index algorithm for the nearest point problem in a polyhedral cone

We consider the problem of finding the nearest point in a polyhedral cone C={x∈R ⁿ :D x≤0} to a given point b∈R ⁿ , where D∈R ^m×n . This problem can be formulated as a convex quadratic programming problem with special structure. We study the structure of this problem and its relationship with the nearest point problem in a pos cone through the concept of polar cones. We then use this relationship to design an efficient algorithm for solving the problem, and carry out computational experiments to evaluate its effectiveness. Our computational results show that our proposed algorithm is more efficient than other existing algorithms for solving this problem.     

Optimal location with equitable loads

The problem considered in this paper is to find p locations for p facilities such that the weights attracted to each facility will be as close as possible to one another. We model this problem as minimizing the maximum among all the total weights attracted to the various facilities. We propose solution procedures for the problem on a network, and for the special cases of the problem on a tree or on a path. The complexity of the problem is analyzed, O(n) algorithms and an O(pn ³) dynamic programming algorithm are proposed for the problem on a path respectively for p=2 and p>2 facilities. Heuristic algorithms (two types of a steepest descent approach and tabu search) are proposed for its solution. Extensive computational results are presented.     

An extension of the edge covering problem

In this paper we define a weightedr-covering problem, and show that there exists an optimum solution of ther-covering problem which can be decomposed into the sum of a rounded down solution of its linear relaxation and an optimal solution of a weighted edge covering problem on a reduced graph. Vertexr-packing problem can also be reduced to ther-covering problem.     

Existence and uniqueness for a nonlinear inverse reaction‐diffusion problem with a nonlinear source in higher dimensions

This paper analyzes the existence and the uniqueness problem for an n‐dimensional nonlinear inverse reaction‐diffusion problem with a nonlinear source. A transformation is used to obtain a new inverse coefficient problem. Then, a parabolic differential operator L_λ is defined to establish the relation between the solution of L_λ = 0 and the new inverse problem. Following this, it is shown that the inverse problem has at least one solution in the class of admissible coefficients. Furthermore, it is proved that this solution is the unique solution of the undertaken inverse problem. A numerical example is given to illustrate ill‐posedness of the inverse problem. Copyright © 2013 John Wiley & Sons, Ltd.     

Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon

Given ann-vertex simple polygonP, the problem of computing the shortest weakly visible subedge ofPis that of finding a shortest line segmentson the boundary ofPsuch thatPis weakly visible froms(ifsexists). In this paper, we present new geometric observations that are useful for solving this problem. Based on these geometric observations, we obtain optimal sequential and parallel algorithms for solving this problem. Our sequential algorithm runs inO(n) time, and our parallel algorithm runs inO(log n) time usingO(n/log n) processors in the CREW PRAM computational model. Using the previously best known sequential algorithms to solve this problem would takeO(n²) time. We also give geometric observations that lead to extremely simple and optimal algorithms for solving, both sequentially and in parallel, the case of this problem where the polygons are rectilinear.     

Single machine batch scheduling to minimize the weighted number of late jobs

The single machine batch scheduling problem to minimize the weighted number of late jobs is studied. In this problem,n jobs have to be processed on a single machine. Each job has a processing time, a due date and a weight. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of this batch is processed. The completion time of each job in the batch coincides with the completion time of the last job in this batch. A job is late if it is completed after its due date. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find a schedule which minimizes the weighted number of late jobs. This problem isNP-hard even if all due dates are equal. For the general case, we present a dynamic programming algorithm which solves the problem with equal weights inO(n ³) time. We formulate a certain scaled problem and show that our dynamic programming algorithm applied to this scaled problem provides a fully polynomial approximation scheme for the original problem. Each algorithm of this scheme has a time requirement ofO(n ³/ +n ³ logn). A side result is anO(n logn) algorithm for the problem of minimizing the maximum weight of late jobs.Supported by INTAS Project 93-257.     

On Inessential Elements in Different Banach Algebras

If B is a subalgebra of a Banach algebra A we consider the problem of determining conditions that ensure that an element of B that exhibits a property in B also exhibits this property when viewed as an element of A. Further, we consider the converse problem whereby an element of B exhibiting a property in A also exhibits this property in B. We extend the analysis of this problem in the setting of inessential and quasi inessential elements. Secondly, we characterise positive quasi inessential elements in the setting of ordered Banach algebras. The quasi inessential elements are the analogues of quasi compact operators.     

A polynomial-time simplex method for the maximumk-flow problem

A generalization of the maximum-flow problem is considered in which every unit of flow sent from the source to the sink yields a payoff of $k. In addition, the capacity of any arce can be increased at a per-unit cost of $c _e . The problem is to determine how much arc capacity to purchase for each arc and how much flow to send so as to maximize the net profit. This problem can be modeled as a circulation problem. The main result of this paper is that this circulation problem can be solved by the network simplex method in at mostkmn pivots. Whenc _e = 1 for each arce, this yields a strongly polynomial-time simplex method. This result uses and extends a result of Goldfarb and Hao which states that the standard maximum-flow problem can be solved by the network simplex method in at mostmn pivots.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

Randomized k-server algorithms for growth-rate bounded graphs

The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total movement cost. While the deterministic competitive ratio is at least k, randomized k-server algorithms have the potential of reaching o(k)-competitive ratios. Prior to this work only few specific cases of this problem were solved. For arbitrary metric spaces, this goal may be approached by using probabilistic metric approximation techniques. This paper gives the first results in this direction, obtaining o(k)-competitive ratio for a natural class of metric spaces, including d-dimensional grids, and wide range of k.     

Minimum Color Sum of Bipartite Graphs

The problem ofminimum color sumof a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently it was shown that in general graphs this problem cannot be approximated withinn^{1 − ε}, for any ε > 0, unlessNP = ZPP(Bar-Noyet al., Information and Computation140(1998), 183–202). In the same paper, a 9/8-approximation algorithm was presented for bipartite graphs. The hardness question for this problem on bipartite graphs was left open. In this paper we show that the minimum color sum problem for bipartite graphs admits no polynomial approximation scheme, unlessP = NP. The proof is byL-reducing the problem of finding the maximum independent set in a graph whose maximum degree is four to this problem. This result indicates clearly that the minimum color sum problem is much harder than the traditional coloring problem, which is trivially solvable in bipartite graphs. As for the approximation ratio, we make a further step toward finding the precise threshold. We present a polynomial 10/9-approximation algorithm. Our algorithm uses a flow procedure in addition to the maximum independent set procedure used in previous solutions.     

A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

A t-spanner of an undirected, unweighted graph G is a spanning subgraph of G with the added property that for every pair of vertices in G, the distance between them in is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t2. For t5, the problem remains NP-hard for planar graphs, whereas for t{2,3,4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation.     

Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement

Given a complete graph K_n=(V,E)with edge weight c_e on each edge, we consider the problem of partitioning the vertices of graph K_n into subcliques that have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. In this paper, we consider using the branch-and-price method to solve the problem. We demonstrate the necessity of cutting planes for this problem and suggest effective ways of adding cutting planes in the branch-and-price framework. The NP hard pricing problem is solved as an integer programming problem. We present computational results on large randomly generated problems.     

On the least complete extension of complete subsemilattices

For a complete sublattice X of a complete lattice C, we consider the problem of the existence of the least complete meet subsemilattice of C having as least complete extension (i.e., the least complete sublattice of C containing it) X. We argue that this problem is not trivial, and we provide two results that, under certain conditions on C and X, give a positive answer to this problem. Received January 31, 1997; accepted in final form October 23, 1997.     

Approximation Algorithms for Steiner and Directed Multicuts

In this paper we consider theSteiner multicutproblem. This is a generalization of the minimum multicut problem where instead of separating nodepairs, the goal is to find a minimum weight set of edges that separates all givensetsof nodes. A set is considered separated if it is not contained in a single connected component. We show anO(log³(kt)) approximation algorithm for the Steiner multicut problem, wherekis the number of sets andtis the maximum cardinality of a set. This improves theO(t log k) bound that easily follows from the previously known multicut results. We also consider an extension of multicuts to directed case, namely the problem of finding a minimum-weight set of edges whose removal ensures that none of the strongly connected components includes one of the prespecifiedknode pairs. In this paper we describe anO(log² k) approximation algorithm for this directed multicut problem. Ifk ? n, this represents an improvement over theO(log n log log n) approximation algorithm that is implied by the technique of Seymour.     

On the coupling of regularization techniques and the boundary element method for a hemivariational inequality modelling a delamination problem

In this paper, we couple regularization techniques of nondifferentiable optimization with the h‐version of the boundary element method (h‐BEM) to solve nonsmooth variational problems arising in contact mechanics. As a model example, we consider the delamination problem. The variational formulation of this problem leads to a hemivariational inequality with a nonsmooth functional defined on the contact boundary. This problem is first regularized and then discretized by an h‐BEM. We prove convergence of the h‐BEM Galerkin solution of the regularized problem in the energy norm, provide an a priori error estimate and give a numerical examples. Copyright © 2016 John Wiley & Sons, Ltd.     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

A numerical method for the Benjamin-Ono equation

This paper is concerned with the numerical solution of the Cauchy problem for the Benjamin-Ono equationu _t +uu _x −Hu _xx =0, whereH denotes the Hilbert transform. Our numerical method first approximates this Cauchy problem by an initial-value problem for a corresponding 2L-periodic problem in the spatial variable, withL large. This periodic problem is then solved using the Crank-Nicolson approximation in time and finite difference approximations in space, treating the nonlinear term in a standard conservative fashion, and the Hilbert transform by a quadrature formula which may be computed efficiently using the Fast Fourier Transform.     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.      

η-Approximation Method for Non-convex Multiobjective Variational Problems

In this paper, we use the η-approximation method for a class of non-convex multiobjective variational problems with invex functionals. In this approach, for the considered multiobjective variational problem, the associated η-approximated multiobjective variational problem is constructed at the given feasible solution. The equivalence between (weakly) e?cient solutions in the original multiobjective variational problem and its associated η-approximated multiobjective variational problem is established under invexity hypotheses.     

A Zero-Space algorithm for Negative Cost Cycle Detection in networks

This paper is concerned with the problem of checking whether a network with positive and negative costs on its arcs contains a negative cost cycle. The Negative Cost Cycle Detection (NCCD) problem is one of the more fundamental problems in network design and finds applications in a number of domains ranging from Network Optimization and Operations Research to Constraint Programming and System Verification. As per the literature, approaches to this problem have been either Relaxation-based or Contraction-based. We introduce a fundamentally new approach for negative cost cycle detection; our approach, which we term as the Stressing Algorithm, is based on exploiting the connections between the NCCD problem and the problem of checking whether a system of difference constraints is feasible. The Stressing Algorithm is an incremental, comparison-based procedure which is as efficient as the fastest known comparison-based algorithm for this problem. In particular, on a network with n vertices and m edges, the Stressing Algorithm takes O(mn) time to detect the presence of a negative cost cycle or to report that none exists. A very important feature of the Stressing Algorithm is that it uses zero extra space; this is in marked contrast to all known algorithms that require Ω(n) extra space. It is well known that the NCCD problem is closely related to the Single Source Shortest Paths (SSSP) problem, i.e., the problem of determining the shortest path distances of all the vertices in a network, from a specified source; indeed most algorithms in the literature for the NCCD problem are modifications of approaches to the SSSP problem. At this juncture, it is not clear whether the Stressing Algorithm could be extended to solve the SSSP problem, even if O(n) extra space is available.