Search

In this paper, we consider k-echelon extensions of the deterministic one warehouse multi-retailer problem. We give constant factor approximation algorithms for some of these extensions when k is fixed. We focus first on the case without backorders and we give a (2k-1)-approximation algorithm under general assumptions on the evolution of the holding costs as products move toward the final customers. We then improve this result to a k-approximation when the holding costs are monotonically non-increasing or non-decreasing (which is a natural situation in practice). Finally we address problems with backorders: we give a 3-approximation for the one-warehouse multi-retailer problem with backlog and a k-approximation algorithm for the k-level Joint Replenishment Problem with backlog (a variant where inventory can only be kept at the final retailers). Ours results are the first constant approximation algorithms for those problems. In addition, we demonstrate the potential of our approach on a practical case. Our preliminary experiments show that the average optimality gap is around 15%. [ABSTRACT FROM AUTHOR]

The efficient modeling of execution price path of an asset to be traded is an important aspect of the optimal trading problem. In this paper an execution price path based on the second order autoregressive process is proposed. The proposed price path is a generalization of the existing first order autoregressive price path in literature. Using dynamic programming method the analytical closed form solution of unconstrained optimal trading problem under the second order autoregressive process is derived. However in order to incorporate non-negativity constraints in the problem formulation, the optimal static trading problems under second order autoregressive price process are formulated. For a risk neutral investor, the optimal static trading problem of minimizing expected execution cost subject to non-negativity constraints is formulated as a quadratic programming problem. Whereas, for a risk averse investor the variance of execution cost is considered as a measure for the timing risk, and the mean-variance problem is formulated. Moreover, the optimal static trading problem subject to stochastic dominance constraints with mean-variance static trading strategy as the reference strategy is studied. Using Static approximation method the algorithm to solve proposed optimal static trading problems is presented. With numerical illustrations conducted on simulated data and the real market data, the significance of second order autoregressive price path, and the optimal static trading problems is presented. [ABSTRACT FROM AUTHOR]

This paper analyzes a single-server discrete-time queueing model with general independent arrivals, where the service process of the server is characterized in two steps. Specifically, the model assumes that (1) each customer represents a random, arbitrarily distributed, amount of work for the server, the service demand, and (2) the server disposes of a fixed number of work units that can be executed per slot, the service capacity. For this non-classical queueing model, we obtain explicit closed-form results for the probability generating functions (pgf's) of the unfinished work in the system (expressed in work units) and the queueing delay of an arbitrary customer (expressed in time slots). Deriving the pgf of the number of customers in the system turns out to be hard, in general. Nevertheless, we derive this pgf explicitly in a number of special cases, i.e., either for geometrically distributed service demands, and/or for Bernoulli arrivals or geometric arrivals. The obtained results show that the tail distributions of the unfinished work, the customer delay and the system content all exhibit a geometric decay, with semi-analytic formulas for the decay rates available. Another interesting conclusion is that, for a given system load, the mean customer delay converges to constant limiting values when the service capacity per slot goes to infinity, and either the mean arrival rate or the mean service demand increases proportionally. Accurate approximative analytical expressions are available for these limiting values. [ABSTRACT FROM AUTHOR]

We consider a two-class processor sharing queueing system scheduled by the discriminatory processor sharing discipline. Poisson arrivals of customers and exponential amounts of service requirements are assumed. At any moment of being served, a customer can leave the system without completion of its service. In the asymptotic regime, where the ratio of the time scales of the two-class customers is infinite, we obtain the conditional sojourn time distribution of each class customers. Numerical experiments show that the time scale decomposition approach developed in this paper gives a good approximation to the conditional sojourn time distribution as well as the expectation of it. [ABSTRACT FROM AUTHOR]

In this paper, we consider adjustable robust versions of convex optimization problems with uncertain constraints and objectives and show that under fairly general assumptions, a static robust solution provides a good approximation for these adjustable robust problems. An adjustable robust optimization problem is usually intractable since it requires to compute a solution for all possible realizations of uncertain parameters, while an optimal static solution can be computed efficiently in most cases if the corresponding deterministic problem is tractable. The performance of the optimal static robust solution is related to a fundamental geometric property, namely, the symmetry of the uncertainty set. Our work allows for the constraint and objective function coefficients to be uncertain and for the constraints and objective functions to be convex, thereby providing significant extensions of the results in Bertsimas and Goyal (Math Oper Res 35:284-305, ) and Bertsimas et al. (Math Oper Res 36: 24-54, ) where only linear objective and linear constraints were considered. The models in this paper encompass a wide variety of problems in revenue management, resource allocation under uncertainty, scheduling problems with uncertain processing times, semidefinite optimization among many others. To the best of our knowledge, these are the first approximation bounds for adjustable robust convex optimization problems in such generality. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study a relaxed extragradient method for finding solutions of a general system of variational inequalities with inverse-strongly monotone mappings in a real Hilbert space. First, this system of variational inequalities is proven to be equivalent to a fixed point problem of nonexpansive mapping. Second, by using the demi-closedness principle for nonexpansive mappings, we prove that under quite mild conditions the iterative sequence defined by the relaxed extragradient method converges strongly to a solution of this system of variational inequalities. In addition, utilizing this result, we provide some applications of the considered problem not just giving a pure extension of existing mathematical problems. [ABSTRACT FROM AUTHOR]

This paper is concerned with the analysis and comparison of semidefinite programming (SDP) relaxations for the satisfiability (SAT) problem. Our presentation is focussed on the special case of 3-SAT, but the ideas presented can in principle be extended to any instance of SAT specified by a set of boolean variables and a propositional formula in conjunctive normal form. We propose a new SDP relaxation for 3-SAT and prove some of its theoretical properties. We also show that, together with two SDP relaxations previously proposed in the literature, the new relaxation completes a trio of linearly sized relaxations with increasing rank-based guarantees for proving satisfiability. A comparison of the relative practical performances of the SDP relaxations shows that, among these three relaxations, the new relaxation provides the best tradeoff between theoretical strength and practical performance within an enumerative algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider a nonsmooth optimization problem with a convex feasible set described by constraint functions which are neither convex nor differentiable nor locally Lipschitz necessarily. Utilizing upper regular convexificators, we characterize the normal cone of the feasible set and derive KKT type necessary and sufficient optimality conditions. Under some assumptions, we show that the set of KKT multipliers is bounded. We also characterize the set of optimal solutions and introduce a linear approximation corresponding to the original problem which is useful in checking optimality. The obtained outcomes extend various results existing in the literature to a more general setting. [ABSTRACT FROM AUTHOR]

Abstract. In this paper, we introduce the concept of approximate solutions for set-valued mappings and provide a sufficient condition for the existence of approximate solutions of set-valued mappings. We obtain an approximate variational principle for set-valued mappings. [ABSTRACT FROM AUTHOR]

We consider the problem of optimally allocating the seats on a single flight leg to the demands from multiple fare classes that arrive sequentially. It is well-known that the optimal policy for this problem is characterized by a set of protection levels. In this paper, we develop a new stochastic approximation method to compute the optimal protection levels under the assumption that the demand distributions are not known and we only have access to the samples from the demand distributions. The novel aspect of our method is that it works with the nonsmooth version of the problem where the capacity can only be allocated in integer quantities. We show that the sequence of protection levels generated by our method converges to a set of optimal protection levels with probability one. We discuss applications to the case where the demand information is censored by the seat availability. Computational experiments indicate that our method is especially advantageous when the total expected demand exceeds the capacity by a significant margin and we do not have good a priori estimates of the optimal protection levels. [ABSTRACT FROM AUTHOR]

The geometric duality theory of Heyde and Löhne (2006) defines a dual to a multiple objective linear programme (MOLP). In objective space, the primal problem can be solved by Benson’s outer approximation method (Benson 1998a,b) while the dual problem can be solved by a dual variant of Benson’s algorithm (Ehrgott et al. 2007). Duality theory then assures that it is possible to find the (weakly) nondominated set of the primal MOLP by solving its dual. In this paper, we propose an algorithm to solve the dual MOLP approximately but within specified tolerance. This approximate solution set can be used to calculate an approximation of the weakly nondominated set of the primal. We show that this set is a weakly ε-nondominated set of the original primal MOLP and provide numerical evidence that this approach can be faster than solving the primal MOLP approximately. [ABSTRACT FROM AUTHOR]

In this paper, we propose a modification of Benson’s algorithm for solving multiobjective linear programmes in objective space in order to approximate the true nondominated set. We first summarize Benson’s original algorithm and propose some small changes to improve computational performance. We then introduce our approximation version of the algorithm, which computes an inner and an outer approximation of the nondominated set. We prove that the inner approximation provides a set of $${\varepsilon}$$ -nondominated points. This work is motivated by an application, the beam intensity optimization problem of radiotherapy treatment planning. This problem can be formulated as a multiobjective linear programme with three objectives. The constraint matrix of the problem relies on the calculation of dose deposited in tissue. Since this calculation is always imprecise solving the MOLP exactly is not necessary in practice. With our algorithm we solve the problem approximately within a specified accuracy in objective space. We present results on four clinical cancer cases that clearly illustrate the advantages of our method. [ABSTRACT FROM AUTHOR]

In this paper, we study Levitin–Polyak type well-posedness for generalized vector variational inequality problems with abstract and functional constraints. Various criteria and characterizations for these types of well-posednesses are given. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of stochastic mathematical programs with equilibrium constraints introduced by Birbil et al. (Math Oper Res 31:739–760, 2006). Firstly, by means of a Monte Carlo method, we obtain a nonsmooth discrete approximation of the original problem. Then, we propose a smoothing method together with a penalty technique to get a standard nonlinear programming problem. Some convergence results are established. Moreover, since quasi-Monte Carlo methods are generally faster than Monte Carlo methods, we discuss a quasi-Monte Carlo sampling approach as well. Furthermore, we give an example in economics to illustrate the model and show some numerical results with this example. [ABSTRACT FROM AUTHOR]

This paper is focused on approximate ( $$\varepsilon$$ -efficient) solutions of multiobjective mathematical programs. We introduce a new $$\varepsilon$$ -efficiency concept which extends and unifies different notions of approximate solution defined in the literature. We characterize these $$\varepsilon$$ -efficient solutions in convex multiobjective programs through approximate solutions of linear scalarizations, which allow us to obtain parametric representations of different $$\varepsilon$$ -efficiency sets. Several classical $$\varepsilon$$ -efficiency notions are considered in order to show the concepts introduced and the results obtained. [ABSTRACT FROM AUTHOR]

In this paper, we consider constrained noncooperative N-person stochastic games with discounted cost criteria. The state space is assumed to be countable and the action sets are compact metric spaces. We present three main results. The first concerns the sensitivity or approximation of constrained games. The second shows the existence of Nash equilibria for constrained games with a finite state space (and compact actions space), and, finally, in the third one we extend that existence result to a class of constrained games which can be “approximated” by constrained games with finitely many states and compact action spaces. Our results are illustrated with two examples on queueing systems, which clearly show some important differences between constrained and unconstrained games. [ABSTRACT FROM AUTHOR]

In multicriteria optimization, several objective functions have to be minimized simultaneously. For this kind of problem, approximations to the whole solution set are of particular importance to decision makers. Usually, approximating this set involves solving a family of parameterized optimization problems. It is the aim of this paper to argue in favour of parameterized quadratic objective functions, in contrast to the standard weighting approach in which parameterized linear objective functions are used. These arguments will rest on the favourable numerical properties of these quadratic scalarizations, which will be investigated in detail. Moreover, it will be shown which parameter sets can be used to recover all solutions of an original multiobjective problem where the ordering in the image space is induced by an arbitrary convex cone. [ABSTRACT FROM AUTHOR]

In this paper, a new trust region method for the system of non-linear equations is presented in which the determining of the trust region radius incorporates the information of its natural residual. The global convergence is obtained under mild conditions. Unlike traditional trust region method, the superlinear convergence of the method is proven under the local error bound condition. This condition is weaker than the non-degeneracy assumption which is necessary for superlinear convergence of traditional trust region method. We also propose an approximate algorithm for the trust region subproblem. Preliminary numerical experiments are reported. [ABSTRACT FROM AUTHOR]

Abstract. Finite potential games are determined, i.e have Nash equilibria in pure strategies. In this paper we investigate the determinateness of potential games, in which one or more players have infinitely many pure strategies. [ABSTRACT FROM AUTHOR]

A multi-objective evolutionary algorithm which can be applied to many nonlinear multi-objective optimization problems is proposed. Its aim is to quickly obtain a fixed size Pareto-front approximation. It adapts ideas from different multi-objective evolutionary algorithms, but also incorporates new devices. In particular, the search in the feasible region is carried out on promising areas (hyperspheres) determined by a radius value, which decreases as the optimization procedure evolves. This mechanism helps to maintain a balance between exploration and exploitation of the search space. Additionally, a new local search method which accelerates the convergence of the population towards the Pareto-front, has been incorporated. It is an extension of the local optimizer SASS and improves a given solution along a search direction (no gradient information is used). Finally, a termination criterion has also been proposed, which stops the algorithm if the distances between the Pareto-front approximations provided by the algorithm in three consecutive iterations are smaller than a given tolerance. To know how far two of those sets are from each other, a modification of the well-known Hausdorff distance is proposed. In order to analyze the algorithm performance, it has been compared to the reference algorithms NSGA-II and SPEA2 and the state-of-the-art algorithms MOEA/D and SMS-EMOA. Several quality indicators have been considered, namely, hypervolume, average distance, additive epsilon indicator, spread and spacing. According to the computational tests performed, the new algorithm, named FEMOEA, outperforms the other algorithms. [ABSTRACT FROM AUTHOR]

Numerical dynamic programming algorithms typically use Lagrange data to approximate value functions over continuous states. Hermite data can be easily obtained from solving the Bellman equation and used to approximate the value functions. We illustrate the use of Hermite data with one-, three-, and six-dimensional examples. We find that Hermite approximation improves the accuracy in value function iteration (VFI) by one to three digits using little extra computing time. Moreover, VFI with Hermite approximation is significantly faster than VFI with Lagrange approximation for the same accuracy, and this advantage increases with the dimension of the continuous states. [ABSTRACT FROM AUTHOR]

n approach to constructing a Pareto front approximation to computationally expensive multiobjective optimization problems is developed. The approximation is constructed as a sub-complex of a Delaunay triangulation of a finite set of Pareto optimal outcomes to the problem. The approach is based on the concept of inherent nondominance. Rules for checking the inherent nondominance of complexes are developed and applying the rules is demonstrated with examples. The quality of the approximation is quantified with error estimates. Due to its properties, the Pareto front approximation works as a surrogate to the original problem for decision making with interactive methods. [ABSTRACT FROM AUTHOR]

Stock exchanges are modeled as nonlinear closed-loop systems where the plant dynamics is defined by known stock market regulations and the actions of agents are based on their beliefs and behavior. The decision of the agents may contain a random element, thus we get a nonlinear stochastic feedback system. The market is in equilibrium when the actions of the agents reinforce their beliefs on the price dynamics. Assuming that linear predictors are used for prediction of the price process, a stochastic approximation procedure for finding market equilibrium is described. The proposed procedure is analyzed using the theory of Benveniste et al. (Adaptive algorithms and stochastic approximations. Springer, Berlin, 1990). A simulation result is also presented. [ABSTRACT FROM AUTHOR]

Abstract. In this paper, we deal with the extended well-posedness and strongly extended well-posedness of set-valued optimization problems. These two concepts are generalizations of the extended well-posedness of real-valued optimization problems defined by Zolezzi. We obtain some criteria and characterizations of these two types of extended well-posedness, further generalizing most results obtained by Zolezzi for the extended well-posedness of scalar optimization problems. In the mean time, many results obtained by us for the extended well-posedness of vector optimization problems have been generalized to set-valued optimization. Finally, we present an approximate variational principle for set-valued maps, derive a necessary approximate optimality condition for set-valued optimization, based on which we introduce a condition, which is somewhat analogous to the Palais-Smale condition (C), and provide sufficient conditions for the extended and strongly extended well-posedness of set-valued optimization problems. [ABSTRACT FROM AUTHOR]

We study a discrete time queueing system where deterministic arrivals have i.i.d. exponential delays ξi. We describe the model as a bivariate Markov chain, prove its ergodicity and study the joint equilibrium distribution. We write a functional equation for the bivariate generating function, finding the solution on a subset of its domain. This solution allows us to prove that the equilibrium distribution of the chain decays super-exponentially fast in the quarter plane. We exploit the latter result and discuss the numerical computation of the solution through a simple yet effective approximation scheme in a wide region of the parameters. Finally, we compare the features of this queueing model with the standard M / D / 1 system, showing that the congestion turns out to be very different when the traffic intensity is close to 1. [ABSTRACT FROM AUTHOR]

We consider a type of optimal switching problems with non-uniform execution delays and ramping. Such problems frequently occur in the operation of economical and engineering systems. We first provide a solution to the problem by applying a probabilistic method. The main contribution is, however, a scheme for approximating the optimal control by limiting the information in the state-feedback. In a numerical example the approximation routine gives a considerable computational performance enhancement when compared to a conventional algorithm. [ABSTRACT FROM AUTHOR]

We consider an energy production network with zones of production and transfer links. Each zone representing an energy market (a country, part of a country or a set of countries) has to satisfy the local demand using its hydro and thermal units and possibly importing and exporting using links connecting the zones. Assuming that we have the appropriate tools to solve a single zonal problem (approximate dynamic programming, dual dynamic programming, etc.), the proposed algorithm allows us to coordinate the productions of all zones. We propose two reformulations of the dynamic model which lead to different decomposition strategies. Both algorithms are adaptations of known monotone operator splitting methods, namely the alternating direction method of multipliers and the proximal decomposition algorithm which have been proved to be useful to solve convex separable optimization problems. Both algorithms present similar performance in theory but our numerical experimentation on real-size dynamic models have shown that proximal decomposition is better suited to the coordination of the zonal subproblems, becoming a natural choice to solve the dynamic optimization of the European electricity market. [ABSTRACT FROM AUTHOR]

Flow lines process discrete workpieces on consecutive machines, which are coupled by buffers. Their operating environment is often stochastic and time-dependent. For the flow line under consideration, the stochasticity is generated by random breakdowns and successive stochastic repair times, whereas the processing times are deterministic. However, the release rate of workpieces to the line is time-dependent, due to changes in demand. The buffers between the machines may be finite or infinite. We introduce two new sampling approaches for the performance evaluation of such flow lines: one method utilizes an approximation based on a mixed-integer program in discrete time with discrete material, while the other approximation is based on partial and ordinary differential equations in continuous time and with a continuous flow of material. In addition, we sketch a proof that these two approximations are equivalent under some linearity assumptions. A computational study demonstrates the accuracy of both approximations relative to a discrete-event simulation in continuous time. Furthermore, we reveal some effects occurring in unreliable flow lines with time-dependent processing rates. [ABSTRACT FROM AUTHOR]

We computationally assess policies for the elevator control problem by a new column-generation approach for the linear programming method for discounted infinite-horizon Markov decision problems. By analyzing the optimality of given actions in given states, we were able to provably improve the well-known nearest-neighbor policy. Moreover, with the method we could identify an optimal parking policy. This approach can be used to detect and resolve weaknesses in particular policies for Markov decision problems. [ABSTRACT FROM AUTHOR]

We study optimal stopping with exponentially distributed exercise lag. We formalize the problem first in a general Markovian setting and derive a set of conditions under which the solution exists. In particular, no semicontinuity assumptions of the payoff function are needed. We analyze also some specific classes of lagged optimal stopping problems with one-dimensional diffusion dynamics where the solution can be characterized in closed form. Finally, the results are illustrated with an explicit example. [ABSTRACT FROM AUTHOR]

We are interested in structures and efficient methods for mixed-integer nonlinear programs (MINLP) that arise from a first discretize, then optimize approach to time-dependent mixed-integer optimal control problems (MIOCPs). In this study we focus on combinatorial constraints, in particular on restrictions on the number of switches on a fixed time grid. We propose a novel approach that is based on a decomposition of the MINLP into a NLP and a MILP. We discuss the relation of the MILP solution to the MINLP solution and formulate bounds for the gap between the two, depending on Lipschitz constants and the control discretization grid size. The MILP solution can also be used for an efficient initialization of the MINLP solution process. The speedup of the solution of the MILP compared to the MINLP solution is considerable already for general purpose MILP solvers. We analyze the structure of the MILP that takes switching constraints into account and propose a tailored Branch and Bound strategy that outperforms cplex on a numerical case study and hence further improves efficiency of our novel method. [ABSTRACT FROM AUTHOR]

We consider a production model with two facilities sharing a resource during a time horizon consisting of a number of time periods. Cumulative production levels at the ends of consecutive periods are linked with constraints of a general form. This allows us to give different interpretations related to scheduling and input–output analysis. The model may arise either separately or in the structure of more general production models. In both cases it is reasonable to find an optimal or near-optimal distribution of resources between these two facilities. This helps either to develop a new production plan or to improve an existing one. The problem in question is NP-hard. We show that our approach leads to fully polynomial time approximation schemes (FPTASs). [ABSTRACT FROM AUTHOR]

We investigate M/ M/1/∞-systems with inventory management, continuous review, exponentially distributed lead times and backordering. We compute performance measures and derive optimality conditions under different order policies. For performance measures, which are not explicitly at hand, we present an approximation scheme for all possible parameter combinations. Although we cannot completely determine analytically the steady state probabilities for the system we are able to derive functional relations between interesting probabilities and show surprising insensitivity properties of several performance measures. For the approximations we develop an algorithm adapted to the system structure which suggests easy adaption to other systems. [ABSTRACT FROM AUTHOR]

In this work, we apply the strong stability method to obtain an estimate for the proximity of the performance measures in the M/ G/1 queueing system to the same performance measures in the M/ M/1 system under the assumption that the distributions of the service time are close and the arrival flows coincide. In addition to the proof of the stability fact for the perturbed M/ M/1 queueing system, we obtain the inequalities of the stability. These results give with precision the error, on the queue size stationary distribution, due to the approximation. For this, we elaborate from the obtained theoretical results, the STR-STAB algorithm which we execute for a determined queueing system: M/ Coxian − 2/1. The accuracy of the approach is evaluated by comparison with simulation results. [ABSTRACT FROM AUTHOR]

We consider Karush-Kuhn-Tucker (KKT) systems, which depend on a parameter. Our contribution concerns with the existence of solution of the directionally perturbed KKT system, approximating the given primal-dual base solution. To our knowledge, we give the first explicit result of this kind in the situation where the multiplier associated with the base primal solution may not be unique. The condition we employ can be interpreted as the 2-regularity property of a smooth reformulation of the KKT system. We also give a strictly sharper, compared to other statements in the literature, estimate for the contingent derivative of the KKT solution multifunction. [ABSTRACT FROM AUTHOR]

Understanding the behavior of an idle time of a limited resource is the key to increase productivity in service operations. When the system consists of nonexponential properties of time distributions it becomes difficult to provide results for the general case. We derive the MacLaurin series for the moments of the idle time with respect to the parameters in the service time and interarrival time distributions for aGI/G/1 queue. The light traffic derivatives are obtained to investigate the quality of a well-known MacLaurin series. The expected error bound under this approach is identified. The coefficients in these series are expressed in terms of the derivatives of the interarrival time density function evaluated at zero and the moments of the service time distribution, which can be easily calculated through a simple recursive procedure. The result for the idle period is easily taken as input to the calculation of other performance measures of the system, e.g., cycle time or interdeparture time distributions. Numerical examples are given to illustrate these results. [ABSTRACT FROM AUTHOR]

We consider nonlinear stochastic optimization problems with probabilistic constraints. The concept of ap-efficient point of a probability distribution is used to derive equivalent problem formulations, and necessary and sufficient optimality conditions. We analyze the dual functional and its subdifferential. Two numerical methods are developed based on approximations of thep-efficient frontier. The algorithms yield an optimal solution for problems involvingr-concave probability distributions. For arbitrary distributions, the algorithms provide upper and lower bounds for the optimal value and nearly optimal solutions. The operation of the methods is illustrated on a cash matching problem with a probabilistic liquidity constraint. [ABSTRACT FROM AUTHOR]

Algorithms generating piecewise linear approximations of the nondominated set for general, convex and nonconvex, multicriteria programs are developed. Polyhedral distance functions are used to construct the approximation and evaluate its quality. The functions automatically adapt to the problem structure and scaling which makes the approximation process unbiased and self-driven. Decision makers preferences, if available, can be easily incorporated but are not required by the procedure. [ABSTRACT FROM AUTHOR]

We first prove that the minimum and maximum traveling salesman problems, their metric versions as well as some versions defined on parameterized triangle inequalities (called sharpened and relaxed metric traveling salesman) are all equi-approximable under an approximation measure, called differential-approximation ratio, that measures how the value of an approximate solution is placed in the interval between the worst- and the best-value solutions of an instance. We next show that the 2[sub OPT] , one of the most-known traveling salesman algorithms, approximately solves all these problems within differential-approximation ratio bounded above by 1/2. We analyze the approximation behavior of 2[sub OPT] when used to approximately solve traveling salesman problem in bipartite graphs and prove that it achieves differential-approximation ratio bounded above by 1/2 also in this case. We also prove that, for any ε>0, it is NP-hard to differentially approximate metric traveling salesman within better than 649/650 + ε and traveling salesman with distances 1 and 2 within better than 741/742 + ε. Finally, we study the standard approximation of the maximum sharpened and relaxed metric traveling salesman problems. These are versions of maximum metric traveling salesman defined on parameterized triangle inequalities and, to our knowledge, they have not been studied until now. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating optima of integer programs { max cx | Ax≤b,0≤x≤1, x - integral} where b>0, c≥0 are rational vectors and A is an arbitrary rational m ×n matrix. Using randomized rounding we find an efficiently verifiable sufficient condition for optima of such integer programs to be close to the optima q of their linear relaxations. We show that our condition guarantees that for any constant ε>0 and sufficiently large n there exists a feasible integral solution z such that q≥ cz≥(1-ε)q. [ABSTRACT FROM AUTHOR]

Abstract. We consider the combinatorial stack-up problem motivated by stacking up bins from a conveyor onto pallets. The stack-up problem is to decide whether a given list q of labeled objects can be processed by removing step by step one of the first s objects of q so that the following holds. After each removal there are at most p labels for which the first object is already removed from q and the last object is still contained in q. We give some NP-completeness results and we introduce and analyze a polynomial time approximation algorithm for the stack-up problem. [ABSTRACT FROM AUTHOR]