Group Embeddings with Algorithmic Properties

We show that every countable group H with solvable word problem can be subnormally embedded into a 2-generated group G which also has solvable word problem. Moreover, the membership problem for H < G is also solvable. We also give estimates of time and space complexity of the word problem in G and of the membership problem for H < G.     

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.     

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.     

A Modified Regularization Method

We consider the Cauchy problem for the systems of the first-order ordinary differential equations with a small parameter E of degree q at the derivative. We study the possibility of solving this problem by means of the regularization method of the Lomov theory of singular perturbations. We show that, for q>1, an application of the procedure by Lomov leads only to the trivial solution to the problem in the class of resonance-free solutions. We suggest and describe a modification of the procedure which enables us to construct a nontrivial solution to the problem in the space of resonance-free solutions.     

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.     

Induction over Strategic Agents: a genetic algorithm solution

We study the problem called Induction over Strategic Agents. This problem has proven hard to solve, even for small problems. We start by reducing the problem to an unconstrained search over w∈ℜ ⁿ . Once we accomplish this, we develop a Genetic Algorithm to perform this search. We compare our results to those obtained on a Mixed Integer formulation.     

Sous ellipticite dans le cadre du calcul S(m,g)

Abstract

We study the regularity of the free boundary in the two membranes problem. We prove that around any point the free boundary is either a C ^{1, α} surface or a cusp, as in the obstacle problem. We also prove C ^{1, 1} regularity for the pair of functions solving the problem.     

An Improved Lower Bound for the Multimedian Location Problem

We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations.     

Two complexity results on c-optimality in experimental design

Finding a c-optimal design of a regression model is a basic optimization problem in statistics. We study the computational complexity of the problem in the case of a finite experimental domain. We formulate a decision version of the problem and prove its NP\boldsymbol{\mathit{NP}}-completeness. We provide examples of computationally complex instances of the design problem, motivated by cryptography. The problem, being NP\boldsymbol{\mathit{NP}}-complete, is then relaxed; we prove that a decision version of the relaxation, called approximate c-optimality, is P-complete. We derive an equivalence theorem for linear programming: we show that the relaxed c-optimality is equivalent (in the sense of many-one LOGSPACE-reducibility) to general linear programming.     

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     

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.     

On minimax optimization problems

We give a short proof that in a convex minimax optimization problem ink dimensions there exist a subset ofk + 1 functions such that a solution to the minimax problem with thosek + 1 functions is a solution to the minimax problem with all functions. We show that convexity is necessary, and prove a similar theorem for stationary points when the functions are not necessarily convex but the gradient exists for each function.     

Solvability of the Navier—Stokes System with L 2 Boundary Data

We prove the existence of the very weak solution of the Dirichlet problem for the Navier—Stokes system with L ² boundary data. Under the small data assumption we also prove the uniqueness. We use the penalization method to study the linearized problem and then apply Banach's fixed point theorem for the nonlinear problem with small boundary data. We extend our result to the case with no small data assumption by splitting the data on a large regular and small irregular part. Accepted 15 March 1999     

Improved algorithms for path partition and related problems

We study the L_∞ path partition problem: given a path of n weighted vertices and an integer k, remove k−1 edges from the path so that the maximum absolute deviation of the weights of the resulting k sub-paths from their mean is minimized. Previously, the best algorithm solves this problem in O(nklogk) time. We present an O(nk) time algorithm. We also give improved solutions for two related problems: the L_d path partition problem and the web proxies placement problem.     

The generalized linear complementarity problem revisited

Given a vertical block matrixA, we consider in this paper the generalized linear complementarity problem VLCP(q, A) introduced by Cottle and Dantzig. We formulate this problem as a linear complementarity problem with a square matrixM, a formulation which is different from a similar formulation given earlier by Lemke. Our formulation helps in extending many well-known results in linear complementarity to the generalized linear complementarity problem. We also show that the class of vertical block matrices which Cottle and Dantzig's algorithm can process is the same as the class of equivalent square matrices which Lemke's algorithm can process. We also present some degree-theoretic results on a vertical block matrix.     

Interpolation of functions from generalized Paley–Wiener spaces

We consider the problem of reconstruction of functions f from generalized Paley–Wiener spaces in terms of their values on complete interpolating sequence {z_n}. We characterize the set of data sequences {f(z_n)} and exhibit an explicit solution to the problem. Our development involves the solution of a particular problem.     

Kadomtsev–Petviashvili Equation on the Half-Plane

We study the boundary value problem for the Kadomtsev–Petviashvili equation on the half-plane y > 0 with a homogeneous condition along the boundary. We show that the problem can be efficiently solved using the dressing method. We present explicit solutions for particular cases of the boundary value problem.     

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.     

Nonnegative inverse eigenvalue problems with partial eigendata

In this paper we consider the inverse problem of constructing an n × n real nonnegative matrix A from the prescribed partial eigendata. We first give the solvability conditions for the inverse problem without the nonnegative constraint and then discuss the associated best approximation problem. To find a nonnegative solution, we reformulate the inverse problem as a monotone complementarity problem and propose a nonsmooth Newton-type method for solving its equivalent nonsmooth equation. Under some mild assumptions, the global and quadratic convergence of our method is established. We also apply our method to the symmetric nonnegative inverse problem and to the cases of prescribed lower bounds and of prescribed entries. Numerical tests demonstrate the efficiency of the proposed method and support our theoretical findings.     

A posteriori error analysis for linearization of nonlinear elliptic problems and their discretizations

The paper is devoted to a posteriori quantitative analysis for errors caused by linearization of non-linear elliptic boundary value problems and their finite element realizations. We employ duality theory in convex analysis to derive computable bounds on the difference between the solution of a non-linear problem and the solution of the linearized problem, by using the solution of the linearized problem only. We also derive computable bounds on differences between finite element solutions of the nonlinear problem and finite element solutions of the linearized problem, by using finite element solutions of the linearized problem only. Numerical experiments show that our a posteriori error bounds are efficient.