Cut problems in graphs with a budget constraint

We study budgeted variants of classical cut problems: the Multiway Cut problem, the Multicut problem, and the k-Cut problem, and provide approximation algorithms for these problems. Specifically, for the budgeted multiway cut and the k-cut problems we provide constant factor approximation algorithms. We show that the budgeted multicut problem is at least as hard to approximate as the sparsest cut problem, and we provide a bi-criteria approximation algorithm for it.     

Time optimal factorizations on compact Lie groups

In this paper we study the relationship between factorization problems on SU(2ⁿ) or more generally on compact Lie groups G and time optimal control problems. Both types of problems naturally arise in physics, such as in quantum computing and in controlling coupled spin systems (NMR‐spectroscopy). In the first part we show that certain factorization problems can be reformulated as time optimal control problems on G. In the second part a necessary condition for the existence of finite optimal factorizations is discussed. At the end we illustrate our results by an example on Euler angle factorizations. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Generalized p-Center problems: Complexity results and approximation algorithms

In an earlier paper, two alternative p-Center problems, where the centers serving costumers must be chosen so that exactly one node from each of p prespecified disjoint pairs of nodes is selected, were shown to be NP-complete. This paper considers a generalized version of these problems, in which the nodes from which the p servers are to be selected are partitioned into k sets and the number of servers selected from each set must be within a prespecified range. We refer to these problems as the ‘Set’ p-Center problems. We establish that the triangle inequality (Δ-inequality) versions of these problems, in which the edge weights are assumed to satisfy the triangle inequality, are also NP-complete. We also provide a polynomial time approximation algorithm for the two Δ-inequality Set p-Center problems that is optimal for one of the problems in the sense that no algorithm with polynomial running time can provide a better constant factor performance guarantee, unless P = NP. For the special case ‘alternative’ p-Center problems, which we refer to as the ‘Pair’ p-Center problems, we extend the previous results in several ways. For example, the results mentioned above for the Set p-Center problems also apply to the Pair p-Center problems. Furthermore, we establish and exploit a correspondence between satisfiability and the dominating set type of problems that naturally arise when considering the decision versions of the Pair p-Center problems.     

Finite Energy Solutions of Maxwell''s Equations and Constructive Hodge Decompositions on Nonsmooth Riemannian Manifolds

We consider two basic potential theoretic problems in Riemannian manifolds: Hodge decompositions and Maxwell's equations. Here we are concerned with smoothness and integrability assumptions. In the context of L^p forms in Lipschitz domains, we show that both are well posed provided that 2−<p<2+, for some >0, depending on the domain. Our approach is constructive (in the sense that we produce integral representation formulas for the solutions) and emphasizes the intimate connections between the two problems at hand. Applications to other related PDEs, such as boundary problems for the Hodge Dirac operator, are also presented.     

On Backward p(x)-Parabolic Equations for Image Enhancement

In this study, we investigate the backward p(x)-parabolic equation as a new methodology to enhance images. We propose a novel iterative regularization procedure for the backward p(x)-parabolic equation based on the nonlinear Landweber method for inverse problems. The proposed scheme can also be extended to the family of iterative regularization methods involving the nonlinear Landweber method. We also investigate the connection between the variable exponent p(x) in the proposed energy functional and the diffusivity function in the corresponding Euler-Lagrange equation. It is well known that the forward problems converges to a constant solution destroying the image. The purpose of the approach of the backward problems is twofold. First, solving the backward problem by a sequence of forward problems, we obtain a smooth image which is denoised. Second, by choosing the initial data properly, we try to reduce the blurriness of the image. The numerical results for denoising appear to give improvement over standard methods as shown by preliminary results.     

Tractability of quasilinear problems I: General results

The tractability of multivariate problems has usually been studied only for the approximation of linear operators. In this paper we study the tractability of quasilinear multivariate problems. That is, we wish to approximate nonlinear operators S_d(·,·) that depend linearly on the first argument and satisfy a Lipschitz condition with respect to both arguments. Here, both arguments are functions of d variables. Many computational problems of practical importance have this form. Examples include the solution of specific Dirichlet, Neumann, and Schrödinger problems. We show, under appropriate assumptions, that quasilinear problems, whose domain spaces are equipped with product or finite-order weights, are tractable or strongly tractable in the worst case setting.This paper is the first part in a series of papers. Here, we present tractability results for quasilinear problems under general assumptions on quasilinear operators and weights. In future papers, we shall verify these assumptions for quasilinear problems such as the solution of specific Dirichlet, Neumann, and Schrödinger problems.     

A coordinate gradient descent method for <Emphasis Type="Italic">ℓ</Emphasis><Subscript>1</Subscript>-regularized convex minimization

In applications such as signal processing and statistics, many problems involve finding sparse solutions to under-determined linear systems of equations. These problems can be formulated as a structured nonsmooth optimization problems, i.e., the problem of minimizing ℓ ₁-regularized linear least squares problems. In this paper, we propose a block coordinate gradient descent method (abbreviated as CGD) to solve the more general ℓ ₁-regularized convex minimization problems, i.e., the problem of minimizing an ℓ ₁-regularized convex smooth function. We establish a Q-linear convergence rate for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We propose efficient implementations of the CGD method and report numerical results for solving large-scale ℓ ₁-regularized linear least squares problems arising in compressed sensing and image deconvolution as well as large-scale ℓ ₁-regularized logistic regression problems for feature selection in data classification. Comparison with several state-of-the-art algorithms specifically designed for solving large-scale ℓ ₁-regularized linear least squares or logistic regression problems suggests that an efficiently implemented CGD method may outperform these algorithms despite the fact that the CGD method is not specifically designed just to solve these special classes of problems.     

Vector and matrix apportionment problems and separable convex integer optimization

The problems of (bi-)proportional rounding of a nonnegative vector or matrix, resp., are written as particular separable convex integer minimization problems. Allowing any convex (separable) objective function we use the notions of vector and matrix apportionment problems. As a broader class of problems we consider separable convex integer minimization under linear equality restrictions Ax = b with any totally unimodular coefficient matrix A. By the total unimodularity Fenchel duality applies, despite the integer restrictions of the variables. The biproportional algorithm of Balinski and Demange (Math Program 45:193–210, 1989) is generalized and derives from the dual optimization problem. Also, a primal augmentation algorithm is stated. Finally, for the smaller class of matrix apportionment problems we discuss the alternating scaling algorithm, which is a discrete variant of the well-known Iterative Proportional Fitting procedure.     

Solvability of elliptic systems with square integrable boundary data

We consider second order elliptic divergence form systems with complex measurable coefficients A that are independent of the transversal coordinate, and prove that the set of A for which the boundary value problem with L ₂ Dirichlet or Neumann data is well posed, is an open set. Furthermore we prove that these boundary value problems are well posed when A is either Hermitean, block or constant. Our methods apply to more general systems of partial differential equations and as an example we prove perturbation results for boundary value problems for differential forms.     

The C 3 Theorem and a D 2 Algorithm for Large Scale Stochastic Mixed-Integer Programming: Set Convexification

This paper considers the two-stage stochastic integer programming problem, with an emphasis on instances in which integer variables appear in the second stage. Drawing heavily on the theory of disjunctive programming, we characterize convexifications of the second stage problem and develop a decomposition-based algorithm for the solution of such problems. In particular, we verify that problems with fixed recourse are characterized by scenario-dependent second stage convexifications that have a great deal in common. We refer to this characterization as the C³ (Common Cut Coefficients) Theorem. Based on the C³ Theorem, we develop a decomposition algorithm which we refer to as Disjunctive Decomposition (D²). In this new class of algorithms, we work with master and subproblems that result from convexifications of two coupled disjunctive programs. We show that when the second stage consists of 0-1 MILP problems, we can obtain accurate second stage objective function estimates after finitely many steps. This result implies the convergence of the D² algorithm.This research was funded by NSF grants DMII 9978780 and CISE 9975050.     

Vector Equilibrium Problems,Minimal Element Problems and Least Element Problems

In this paper we introduce some concepts of feasible sets for vector equilibrium problems and some classes of Z-maps for vectorial bifunctions. Under strict pseudomonotonicity assumptions, we investigate the relationship between minimal element problems of feasible sets and vector equilibrium problems. By using Z-maps, we further study the least element problems of feasible sets for vector equilibrium problems. Finally, we prove a generalized sublattice property of feasible sets for vector equilibrium problems associated with Z-maps. This work was supported by the National Natural Science Foundation of China and the Applied Research Project of Sichuan Province (05JY029-009-1). The authors thank Professor Charalambos D. Aliprantis and the referees for valuable comments and suggestions leading to improvements of this paper.     

Some existence results for solutions of generalized vector quasi-equilibrium problems

In this paper, we consider more general forms of generalized vector quasi-equilibrium problems for multivalued maps which include many known vector quasi-equilibrium problems and generalized vector quasi-variational inequality problems as special cases. We establish some existence results for solutions of these problems under pseudomonotonicity and u-hemicontinuity/ℓ-hemicontinuity assumptions.      

Gradient Estimates for the Perfect and Insulated Conductivity Problems with Multiple Inclusions

In this paper, we study the perfect and the insulated conductivity problems with multiple inclusions imbedded in a bounded domain in ? ⁿ , n ≥ 2. For these two extreme cases of the conductivity problems, the gradients of their solutions may blow up as two inclusions approach each other. We establish the gradient estimates for the perfect conductivity problems and an upper bound of the gradients for the insulated conductivity problems in terms of the distances between any two closely spaced inclusions.     

Optimal <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-Control in Coefficients for Dirichlet Elliptic Problems: <Emphasis Type="Italic">W</Emphasis>-Optimal Solutions

In this paper, we study a Dirichlet optimal control problem associated with a linear elliptic equation the coefficients of which we take as controls in the class of integrable functions. The coefficients may degenerate and, therefore, the problems may exhibit the so-called Lavrentieff phenomenon and non-uniqueness of weak solutions. We consider the solvability of this problem in the class of W-variational solutions. Using a concept of variational convergence of constrained minimization problems in variable spaces, we prove the existence of W-solutions to the optimal control problem and provide the way for their approximation. We emphasize that control problems of this type are important in material and topology optimization as well as in damage or life-cycle optimization.     

Generic Stability and Essential Components of Generalized KKM Points and Applications

We propose the definition of T-KKM points and consider generic stability of T-KKM mappings and essential components of sets of T-KKM points. As applications, using a unified approach, we derive from these results the existence of essential components of solution sets to various optimization-related problems. We do this in two steps. First, we deduce the corresponding results for variational inclusions, which are new. Then we obtain, as consequences, the existence of essential components of solutions to other problems, which are new or include recent ones in the literature.     

Intelligent variable orderings and re-orderings in DAC-based solvers for WCSP

Weighted constraint satisfaction problems (WCSPs) is a well-known framework for combinatorial optimization problems with several domains of application. In the last few years, several local consistencies for WCSPs have been proposed. Their main use is to embed them into a systematic search, in order to detect and prune unfeasible values as well as to anticipate the detection of deadends. Some of these consistencies rely on an order among variables but nothing is known about which orders are best. Therefore, current implementations use the lexicographic order by default. In this paper we analyze the effect of heuristic orders at three levels of increasing overhead: i) compute the order prior to search and keep it fixed during the whole solving process (we call this a static order), ii) compute the order at every search node using current subproblem information (we call this a dynamic order) and iii) compute a sequence of different orders at every search node and sequentially enforce the local consistency for each one (we call this dynamic re-ordering). We performed experiments in three different problems: Max-SAT, Max-CSP and warehouse location problems. We did not find an alternative better than the rest for all the instances. However, we found that inverse degree (static order), sum of unary weights (dynamic order) and re-ordering with the sum of unary weights are good heuristics which are always better than a random order. This research is supported by the MEC through project TIC-2002-04470-C03.     

Two-sided inequalities for the Struve and Lommel functions

Abstract

Mathematical inequalities and other results involving such widely- and extensively-studied special functions of mathematical physics and applied mathematics as (for example) the Bessel, Struve and Lommel functions as well as the associated hypergeometric functions are potentially useful in many seemingly diverse areas of applications, especially in situations in which these functions are involved in solutions of mathematical, physical and engineering problems which can be modeled by ordinary and partial di?erential equations. With this objective in view, our present investigation is motivated by some open problems involving inequalities for a number of particular forms of the hypergeometric function ₁F₂(a; b, c; z). Here, in this paper, we apply a novel approach to such problems and obtain presumably new two-sided inequalities for the Struve function, the associated Struve function and the modified Struve function by first investigating inequalities for the general hypergeometric function ₁F₂(a; b, c; z). We also briefly discuss the analogous new inequalities for the Lommel function under some conditions and constraints. Finally, as special cases of our main results, we deduce several inequalities for the modified Lommel function and the normalized Lommel function.     

Generating highly balanced sudoku problems as hard problems

Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold interesting area, in fact. On the one side Sudoku problems, being a variant of Gerechte Designs and Latin Squares, are being actively used for experimental design, as in Bailey et al. (Am. Math. Mon. 115:383–404, 2008; J. Agron. Crop Sci. 165:121–130, 1990), Morgan (Latin squares and related experimental designs. Wiley, New York, 2008) and Vaughan (Electron. J. Comb. 16, 2009). On the other hand, Sudoku problems, as simple as they seem, are really hard structured combinatorial search problems, and thanks to their characteristics and behavior, they can be used as benchmark problems for refining and testing solving algorithms and approaches. Also, thanks to their high inner structure, their study can contribute more than studies of random problems to our goal of solving real-world problems and applications and understanding problem characteristics that make them hard to solve. In this work we use two techniques for solving and modeling Sudoku problems, namely, Constraint Satisfaction Problem (CSP) and Satisfiability Problem (SAT) approaches. To this effect we define the Generalized Sudoku Problem (GSP), where regions can be of rectangular shape, problems can be of any order, and solution existence is not guaranteed. With respect to the worst-case complexity, we prove that GSP with block regions of m rows and n columns with m≠n is NP-complete. For studying the empirical hardness of GSP, we define a series of instance generators, that differ in the balancing level they guarantee between the constraints of the problem, by finely controlling how the holes are distributed in the cells of the GSP. Experimentally, we show that the more balanced are the constraints, the higher the complexity of solving the GSP instances, and that GSP is harder than the Quasigroup Completion Problem (QCP), a problem generalized by GSP. Finally, we provide a study of the correlation between backbone variables—variables with the same value in all the solutions of an instance—and hardness of GSP.     

Gauss-seidel method for least-distance problems

In this paper, we reformulate the least-distance problems with bounded inequality constraints as an unconstrained convex minimization problem, which is equivalent to a system of piecewise linear equationsA(a+A ^T y) _c ^d =b. The proposed Gauss-Seidel method for solving the problems is easy to implement and behaves very well when the number of rows ofA is much less than the number of columns ofA. Moreover, we prove that the Gauss-Seidel method has a linear convergence rate.The authors would like to thank Jinshui Qin who did some preliminary numerical testing for their research.     

An implicit Landweber method for nonlinear ill-posed operator equations

In this paper, we are interested in the solution of nonlinear inverse problems of the form F(x)=y. We propose an implicit Landweber method, which is similar to the third-order midpoint Newton method in form, and consider the convergence behavior of the implicit Landweber method. Using the discrepancy principle as a stopping criterion, we obtain a regularization method for ill-posed problems. We conclude with numerical examples confirming the theoretical results, including comparisons with the classical Landweber iteration and presented modified Landweber methods.