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.     

Supporting the development of algebraic thinking in middle school: a closer look at students’ informal strategies

This study investigated how 31 sixth-, seventh-, and eighth-grade middle school students who had not previously, nor were currently taking a formal Algebra course, approached word problems of an algebraic nature. Specifically, these algebraic word problems were of the form x + (x + a) + (x + b) = c or ax + bx + cx = d. An examination of students’ understanding of the relationships expressed in the problems and how they used this information to solve problems was conducted. Data included the students’ written responses to problems, field notes of researcher-student interactions while working on the problems, and follow-up interviews. Results showed that students had many informal strategies for solving the problems with systematic guess and check being the most common approach. Analysis of researcher-student interactions while working on the problems revealed ways in which students struggled to engage in the problems. Support mechanisms for students who struggle with these problems are suggested. Finally, implications are provided for drawing upon students’ informal and intuitive knowledge to support the development of algebraic thinking.     

A note on the approximability of cutting stock problems

Cutting stock problems and bin packing problems are basically the same problems. They differ essentially on the variability of the input items. In the first, we have a set of items, each item with a given multiplicity; in the second, we have simply a list of items (each of which we may assume to have multiplicity 1). Many approximation algorithms have been designed for packing problems; a natural question is whether some of these algorithms can be extended to cutting stock problems. We define the notion of “well-behaved” algorithms and show that well-behaved approximation algorithms for one, two and higher dimensional bin packing problems can be translated to approximation algorithms for cutting stock problems with the same approximation ratios.     

Problem posing via “what if not?” strategy in solid geometry — a case study

The study describes the kinds of problems posed by pre-service teachers on the basis of complex solid geometry tasks using the “what if not?” strategy and the educational value of such an activity. Twenty-eight pre-service teachers participated in two workshops in which they had to pose problems on the basis of given problems. Analysis of the posed problems revealed a wide range of problems including those containing a change of one of the numerical data to another specific one, to a proof problem. Different kinds of posed problems enlightened some phenomena such as a bigger frequency of posed problems with another numerical value and a lack of posed problems including formal generalization. We also discuss the educational strengths of problem posing in solid geometry using the “what if not?” strategy, which could make the learner rethink the geometrical concepts he uses while creating new problems, make connections between the given and the new concepts and as a result deepen his understanding of them.     

Noncontinuous data boundary value problems for Schrödinger equation in Lipschitz domains

The noncontinuous data boundary value problems for Schrödinger equations in Lipschitz domains and its progress are pointed out in this paper. Particularly, the L ^p boundary value problems with p > 1, and H ^p boundary value problems with p < 1 have been studied. Some open problems about the Besov-Sobolev and Orlicz boundary value problems are given.     

The external constraint 4 nonempty part sandwich problem

List partitions generalize list colourings. Sandwich problems generalize recognition problems. The polynomial dichotomy (NP-complete versus polynomial) of list partition problems is solved for 4-dimensional partitions with the exception of one problem (the list stubborn problem) for which the complexity is known to be quasipolynomial. Every partition problem for 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem (the 2K₂-partition problem) for which the complexity of the corresponding list problem is known to be NP-complete. The present paper considers external constraint 4 nonempty part sandwich problems. We extend the tools developed for polynomial solutions of recognition problems obtaining polynomial solutions for most corresponding sandwich versions. We extend the tools developed for NP-complete reductions of sandwich partition problems obtaining the classification into NP-complete for some external constraint 4 nonempty part sandwich problems. On the other hand and additionally, we propose a general strategy for defining polynomial reductions from the 2K₂-partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of 2K₂-hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem.     

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.      

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.     

Strong vector F-complementary problem and least element problem of feasible set

In this paper we introduce several classes of strong vector F-complementary problems and give some existence results for these problems in Banach spaces. We also discuss the least element problems of feasible sets and present their relations with the strong vector F-complementary problems.     

A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems

This paper is concerned with a practical algorithm for solving low rank linear multiplicative programming problems and low rank linear fractional programming problems. The former is the minimization of the sum of the product of two linear functions while the latter is the minimization of the sum of linear fractional functions over a polytope. Both of these problems are nonconvex minimization problems with a lot of practical applications. We will show that these problems can be solved in an efficient manner by adapting a branch and bound algorithm proposed by Androulakis–Maranas–Floudas for nonconvex problems containing products of two variables. Computational experiments show that this algorithm performs much better than other reported algorithms for these class of problems.     

Location problems

Recent developments for several location problems are surveyed. These include: graph theoretic and combinatorial formulations of the simple plant location problem, the NP-hardness of some p-center problems, worst-case bounds for several polynomial-time heuristics for some p-center problems, and a general solution to a class of one facility network problems with convex cost functions.     

Time complexity of single machine scheduling with stochastic precedence constraints

This paper deals with single machine scheduling problems with stochastic precedence relations (so calledGERT networks). Until now most investigations on such problems, dealt with algorithms running in polynomial time. On the other hand, for scheduling problems with deterministic precedence relations exist a lot of results about time complexity. Therefore, the object of this paper is to consider time complexity of scheduling problems with stochastic precedence constraints and to describe the boundary between theNP-hard problems and those which can be solved in polynomial time.     

Optimality criteria in E-convex programming

Necessary and sufficient optimality criteria in nonlinear programming are discussed for a class of E-convex programming problems which is considered more general than a class of convex programming problems. We also modify the Fritz John and the Kuhn–Tucker problems to E-Fritz John and E-Kuhn–Tucker problems.     

Polymatroids and mean-risk minimization in discrete optimization

We study discrete optimization problems with a submodular mean-risk minimization objective. For 0–1 problems a linear characterization of the convex lower envelope is given. For mixed 0–1 problems we derive an exponential class of conic quadratic valid inequalities. We report computational experiments on risk-averse capital budgeting problems with uncertain returns.     

Equilibrium and least element problems for multivalued functions

The principal aim of this paper is to extend some recent results which concern problems involving bifunctions to similar generalized problems for multivalued bifunctions. To this end, by using the appropriate notions of strict pseudomonotonicity we establish the relationships between generalized vector equilibrium problems and generalized minimal element problems of feasible sets. Moreover relationships between generalized least element problems of feasible sets and generalized vector equilibrium problems are studied by employing the concept of Z-multibifunctions.     

On <Emphasis Type="Italic">G</Emphasis>-invex multiobjective programming. Part II. Duality

This paper represents the second part of a study concerning the so-called G-multiobjective programming. A new approach to duality in differentiable vector optimization problems is presented. The techniques used are based on the results established in the paper: On G-invex multiobjective programming. Part I. Optimality by T.Antczak. In this work, we use a generalization of convexity, namely G-invexity, to prove new duality results for nonlinear differentiable multiobjective programming problems. For such vector optimization problems, a number of new vector duality problems is introduced. The so-called G-Mond–Weir, G-Wolfe and G-mixed dual vector problems to the primal one are defined. Furthermore, various so-called G-duality theorems are proved between the considered differentiable multiobjective programming problem and its nonconvex vector G-dual problems. Some previous duality results for differentiable multiobjective programming problems turn out to be special cases of the results described in the paper.     

Further Results on Generalized Intersection Searching Problems: Counting,Reporting, and Dynamization

In a generalized intersection searching problem, a set, S, of colored geometric objects is to be preprocessed so that given some query object, q, the distinct colors of the objects intersected by q can be reported efficiently or the number of such colors can be counted efficiently. In the dynamic setting, colored objects can be inserted into or deleted from S. These problems generalize the well-studied standard intersection searching problems and are rich in applications. Unfortunately, the techniques known for the standard problems do not yield efficient solutions for the generalized problems. Moreover, previous work (R. Janardan and M. Lopez, Generalized intersection searching problems, Internat. J. Comput. Geom. Appl.3 (1993), 39-69) on generalized problems applies only to the static reporting problems. In this paper, a uniform framework is presented to solve efficiently the counting/reporting versions of a variety of generalized intersection searching problems in static/dynamic settings. These problems include 1-, 2-, and 3-dimensional range searching, quadrant searching, interval intersection searching, 1- and 2-dimensional point enclosure searching, and orthogonal segment intersection searching.     

A modified VNS metaheuristic for max-bisection problems

Variable neighborhood search (VNS) metaheuristic as presented in Festa et al. [Randomized heuristics for the MAX-CUT problem, Optim. Methods Software 17 (2002) 1033–1058] can obtain high quality solution for max-cut problems. Therefore, it is worthwhile that VNS metaheuristic is extended to solve max-bisection problems. Unfortunately, comparing with max-cut problems, max-bisection problems have more complicated feasible region via the linear constraint e^Tx=0. It is hard to directly apply the typical VNS metaheuristic to deal with max-bisection problems. In this paper, we skillfully combine the constraint e^Tx=0 with the objective function, obtain a new optimization problem which is equivalent to the max-bisection problem, and then adopt a distinct greedy local search technique to the resulted problem. A modified VNS metaheuristic based on the greedy local search technique is applied to solve max-bisection problems. Numerical results indicate that the proposed method is efficient and can obtain high equality solution for max-bisection problems.     

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.     

Equivalence of Equilibrium Problems and Least Element Problems

In this paper, we introduce the concept of feasible set for an equilibrium problem with a convex cone and generalize the notion of a Z-function for bifunctions. Under suitable assumptions, we derive some equivalence results of equilibrium problems, least element problems, and nonlinear programming problems. The results presented extend some results of [Riddell, R.C.: Equivalence of nonlinear complementarity problems and least element problems in Banach lattices. Math. Oper. Res. 6, 462–474 (1981)] to equilibrium problems. This work was supported by the National Natural Science Foundation of China (10671135) and Specialized Research Fund for the Doctoral Program of Higher Education (20060610005) and the Educational Science Foundation of Chongqing (KJ051307).