On the Multiplicity Problem and the Isomorphism Problem for the Four Subspace Algebra

Let Λ be the four subspace algebra. We show that for any Λ-module M there exists an algorithm (up to the problem of finding roots of the so-called characteristic polynomial of M) with relatively low polynomial complexity of determining multiplicities of all direct summands of M. Moreover, we give a fully algorithmic criterion for deciding if two Λ-modules M and N are isomorphic.     

Persistency in the assignment and transportation problems

LetG = (U,V,E) be a bipartite graph with weights of its edgesc _ij . For the assignment and transportation problem given by such a graph we propose efficient procedures for partitioning the edge setE into three classes:E _o is the set of edgesij withx _ij = 0 for each optimum solution (0-persistent edges);E ₁ is the set of edges withx _ij > 0 and constant for each optimum (1-persistent edges) andE _w is the set of edges such that there are two optimum solutions x, x withx _ij x _ij ¹ (weakly persistent edges).     

A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk²(logn+klogk)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomial-time algorithm with running time O(nk²log²n).     

Partition identities and the coin exchange problem

The number of partitions of n into parts divisible by a or b equals the number of partitions of n in which each part and each difference of two parts is expressible as a non-negative integer combination of a and b. This generalizes identities of MacMahon and Andrews. The analogous identities for three or more integers (in place of a,b) hold in certain cases.     

A Note on Noncancellable Varieties

Given two affine algebraic varieties X and Y such that X × ? ? Y × ?, it may happen that X and Y are not isomorphic. This is shown, for example, by so-called “Danielewski surfaces.” In this note, we give a simple construction of such varieties X, Y of an arbitrary dimension n > 1.     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

Exploring the Relationship Between Max-Cut and Stable Set Relaxations

The max-cut and stable set problems are two fundamental -hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.     

Optimization and optimality test for the Max-Cut Problem

We show that the following two problems are polynomially equivalent:

A uniqueness theorem from partial transmission eigenvalues and potential on a subdomain

It is well known that a spherically symmetric wave speed problem in a bounded spherical region may be reduced, by means of Liouville transform, to the Sturm–Liouville problem L(q) in a finite interval. In this work, a uniqueness theorem for the potential q of the derived Sturm–Liouville problem L(q) is proved when the data are partial knowledge of the given spectra and the potential. Copyright © 2016 John Wiley & Sons, Ltd.     

Matrix representation and gradient flows for NP-hard problems

Over the past decade, a number of connections between continuous flows and numerical algorithms were established. Recently, Brockett and Wong reported a connection between gradient flows on the special orthogonal groupLO(n) and local search solutions for the assignment problem. In this paper, we describe a uniform formulation for certain NP-hard combinatorial optimization problems in matrix form and examine their connection with gradient flows onLO(n). For these problems, there is a correspondence between the so-called 2-opt solutions and asymptotically stable critical points of an associated gradient flow.     

New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems

We consider the bounded integer knapsack problem (BKP) , subject to: , and x_j{0,1,…,m_j},j=1,…,n. We use proximity results between the integer and the continuous versions to obtain an O(n³W²) algorithm for BKP, where W=max_j=1,…,nw_j. The respective complexity of the unbounded case with m_j=∞, for j=1,…,n, is O(n²W²). We use these results to obtain an improved strongly polynomial algorithm for the multicover problem with cyclical 1’s and uniform right-hand side.     

An improved approximation ratio for the minimum latency problem

Given a tour visitingn points in a metric space, thelatency of one of these pointsp is the distance traveled in the tour before reachingp. Theminimum latency problem (MLP) asks for a tour passing throughn given points for which the total latency of then points is minimum; in effect, we are seeking the tour with minimum average arrival time. This problem has been studied in the operations research literature, where it has also been termed the delivery-man problem and the traveling repairman problem. The approximability of the MLP was first considered by Sahni and Gonzalez in 1976; however, unlike the classical traveling salesman problem (TSP), it is not easy to give any constant-factor approximation algorithm for the MLP. Recently, Blum et al. (A. Blum, P. Chalasani, D. Coppersimith, W. Pulleyblank, P. Raghavan, M. Sudan, Proceedings of the 26th ACM Symposium on the Theory of Computing, 1994, pp. 163–171) gave the first such algorithm, obtaining an approximation ratio of 144. In this work, we develop an algorithm which improves this ratio to 21.55; moreover, combining our algorithm with a recent result of Garg (N. Garg, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 302–309) provides an approximation ratio of 10.78. The development of our algorithm involves a number of techniques that seem to be of interest from the perspective of the TSP and its variants more generally. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by NSF contract 9302476-CCR and an NEC research grant.Author supported by an ONR Graduate Fellowship.     

Examples of max-flow and min-cut problems with duality gaps in continuous networks

Strang (Mathematical Programming 26, 1983) gave a method to establish a max-flow min-cut theorem in a domain of a Euclidean space. The method can be applied also to max-flow min-cut problems defined by Iri (Survey of Mathematical Programming, North-Holland, 1979) whenever the capacity functions of max-flow problems are bounded and continuous. This paper deals with max-flow min-cut problems of Strang and Iri with unbounded or noncontinuous capacity functions. It is proved that, in such problems, max-flow min-cut theorems may fail to hold.     

Valuations and Busemann–Petty type problems

Projection and intersection bodies define continuous and GL(n) contravariant valuations. They played a critical role in the solution of the Shephard problem for projections of convex bodies and its dual version for sections, the Busemann–Petty problem. We consider the question whether ΦKΦL implies V(K)V(L), where Φ is a homogeneous, continuous operator on convex or star bodies which is an SO(n) equivariant valuation. Important previous results for projection and intersection bodies are extended to a large class of valuations.     

Boundary Problems for Harmonic Functions and Norm Estimates for Inverses of Singular Integrals in Two Dimensions

In this paper, we establish sharp well-posedness results for tangential derivative problems for the Laplacian with data in L ^p , 1 < p < ∞, on curvilinear polygons. Furthermore, we produce norm estimates/formulas for inverses of singular integral operators relevant for the Dirichlet, Neumann, tangential derivative, and transmission boundary value problems associated with the Laplacian in a distinguished subclass of Lipschitz domains in two dimensions. Our approach relies on Calderón-Zygmund theory and Mellin transform techniques.     

A simultaneous approach to inverse source problem by Green's function

In this paper, we consider an inverse source problem of identification of F(t) function in the linear parabolic equation u_t = u_xx + F(t) and u₀(x) function as the initial condition from the measured final data and local boundary data. Based on the optimal control framework by Green's function, we construct Fréchet derivative of Tikhonov functional. The stability of the minimizer is established from the necessary condition. The CG algorithm based on the Fréchet derivative is applied to the inverse problem, and results are presented for a test example. Copyright © 2014 John Wiley & Sons, Ltd.     

An Application of a Mountain Pass Theorem

We are concerned with the following Dirichlet problem: −Δu(x) = f(x, u), x∈Ω, u∈H ¹ ₀(Ω), (P) where f(x, t) ∈C (×ℝ), f(x, t)/t is nondecreasing in t∈ℝ and tends to an L ^∞-function q(x) uniformly in x∈Ω as t→ + ∞ (i.e., f(x, t) is asymptotically linear in t at infinity). In this case, an Ambrosetti-Rabinowitz-type condition, that is, for some θ > 2, M > 0, 0 > θF(x, s) ≤f(x, s)s, for all |s|≥M and x∈Ω, (AR) is no longer true, where F(x, s) = ∫ ^s ₀ f(x, t)dt. As is well known, (AR) is an important technical condition in applying Mountain Pass Theorem. In this paper, without assuming (AR) we prove, by using a variant version of Mountain Pass Theorem, that problem (P) has a positive solution under suitable conditions on f(x, t) and q(x). Our methods also work for the case where f(x, t) is superlinear in t at infinity, i.e., q(x) ≡ +∞. Received June 24, 1998, Accepted January 14, 2000.     

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.      

Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems

In this paper, we consider two types of inverse sorting problems. The first type is an inverse sorting problem by minimizing the total weighted number of changes with bound constraints. We present an O(n ²) time algorithm to solve the problem. The second type is a partial inverse sorting problem and a variant of the partial inverse sorting problem. We show that both the partial inverse sorting problem and the variant can be solved by a combination of a sorting problem and an inverse sorting problem. Supported by the Hong Kong Universities Grant Council (CERG CITYU 103105) and the National Key Research and Development Program of China (2002CB312004) and the National Natural Science Foundation of China (700221001, 70425004).