Approximating integer programs with positive right-hand sides

We study minimisation of integer linear programs with positive right-hand sides. We show that such programs can be approximated within the maximum absolute row sum of the constraint matrix A whenever the variables are allowed to take values in N. This result is optimal under the unique games conjecture. When the variables are restricted to bounded domains, we show that finding a feasible solution is NP-hard in almost all cases.     

Approximation algorithms for covering/packing integer programs

Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing . We give a bicriteria-approximation algorithm that, given ε∈(0,1], finds a solution of cost O(ln(m)/ε²) times optimal, meeting the covering constraints (Ax?a) and multiplicity constraints (x?d), and satisfying Bx?(1+ε)b+β, where β is the vector of row sums β_i=∑_jB_ij. Here m denotes the number of rows of A.This gives an O(lnm)-approximation algorithm for CIP—minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx?b. The previous best approximation ratio has been O(ln(max_j∑_iA_ij)) since 1982. CIP contains the set cover problem as a special case, so O(lnm)-approximation is the best possible unless P=NP.     

Approximation schemes for deal splitting and covering integer programs with multiplicity constraints

We consider the problem of splitting an order for R goods, R≥1, among a set of sellers, each having bounded amounts of the goods, so as to minimize the total cost of the deal. In deal splitting with packages (DSP), the sellers offer packages containing combinations of the goods; in deal splitting with price tables (DST), the buyer can generate such combinations using price tables. Our problems, which often occur in online reverse auctions, generalize covering integer programs with multiplicity constraints (CIP), where we must fill up an R-dimensional bin by selecting (with a bounded number of repetitions) from a set of R-dimensional items, such that the overall cost is minimized. Thus, both DSP and DST are NP-hard, already for a single good, and hard to approximate for arbitrary number of goods.In this paper we focus on finding efficient approximations for DSP and DST instances where the number of goods is some fixed constant. In particular, we develop polynomial time approximation schemes (PTAS) for several subclasses of instances of practical interest. Our results include a PTAS for CIP in fixed dimension, and a more efficient (combinatorial) scheme for CIP_∞, where the multiplicity constraints are omitted. Our approximation scheme for CIP_∞ is based on a non-trivial application of the fast scheme for the fractional covering problem, proposed by Fleischer [L. Fleischer, A fast approximation scheme for fractional covering problems with variable upper bounds, in: Proc. of the 15th ACM-SIAM Symposium on Discrete Algorithm, 2004, pp. 994-1003].     

On the maximum acyclic subgraph problem under disjunctive constraints

Disjunctively constrained versions of classic problems in graph theory such as shortest paths, minimum spanning trees and maximum matchings were recently studied. In this article we introduce disjunctive constrained versions of the Maximum Acyclic Subgraph problem. Negative disjunctive constraints state that a certain pair of edges cannot be contained simultaneously in a feasible solution. Positive disjunctive constraints enforces that at least one arc for the underlying pair is in a feasible solution. It is convenient to represent these disjunctive constraints in terms of an undirected graph, called constraint graph, whose vertices correspond to the arcs of the original graph, and whose edges encode the disjunctive constraints. For the Maximum Acyclic Subgraph problem under Negative Disjunctive Constraints we develop 1/2-approximative algorithms that are polynomial for certain classes of constraint graphs. We also show that determining if a feasible solution exists for an instance of the Maximum Acyclic Subgraph problem under Positive Disjunctive Constraints is an NP-Complete problem.     

Markowitz-based portfolio selection with cardinality constraints using improved particle swarm optimization

This work presents particle swarm optimization (PSO), a collaborative population-based meta-heuristic algorithm for solving the Cardinality Constraints Markowitz Portfolio Optimization problem (CCMPO problem). To our knowledge, an efficient algorithmic solution for this nonlinear mixed quadratic programming problem has not been proposed until now. Using heuristic algorithms in this case is imperative. To solve the CCMPO problem, the proposed improved PSO increases exploration in the initial search steps and improves convergence speed in the final search steps. Numerical solutions are obtained for five analyses of weekly price data for the following indices for the period March, 1992 to September, 1997: Hang Seng 31 in Hong Kong, DAX 100 in Germany, FTSE 100 in UK, S&P 100 in USA and Nikkei 225 in Japan. The test results indicate that the proposed PSO is much more robust and effective than existing PSO algorithms, especially for low-risk investment portfolios. In most cases, the PSO outperformed genetic algorithm (GA), simulated annealing (SA), and tabu search (TS).     

Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints

This paper considers the two-stage flexible flowshop scheduling problem with availability constraints. We discuss the complexity and the approximability of the problem, and provide some approximation algorithms with finite and tight worst case performance bounds for some special cases of the problem.     

Heuristics for the strip packing problem with unloading constraints

This article addresses the Strip Packing Problem with Unloading Constraints (SPU). In this problem, we are given a strip of fixed width and unbounded height, and n items of C different classes. As in the well-known two-dimensional Strip Packing problem, we have to pack all items minimizing the used height, but now we have the additional constraint that items of higher classes cannot block the way out of lower classes items. This problem appears as a sub-problem in the Two-Dimensional Loading Capacitated Vehicle Routing Problem (2L-CVRP), where one has to optimize the delivery of goods, demanded by a set of clients, that are transported by a fleet of vehicles of limited capacity based at a central depot. We propose two approximation algorithms and a GRASP heuristic for the SPU problem and provide an extensive computational experiment with these algorithms using well know instances for the 2L-CVRP problem as well as new instances adapted from the Strip Packing problem.     

Improved parallel approximation of a class of integer programming problems

We present a method to derandomizeRNC algorithms, converting them toNC algorithms. Using it, we show how to approximate a class of NP-hard integer programming problems inNC, to within factors better than the current-bestNC algorithms (of Berger and Rompel and Motwaniet al.); in some cases, the approximation factors are as good as the best-known sequential algorithms, due to Raghavan. This class includes problems such as global wire-routing in VLSI gate arrays and a generalization of telephone network planning in SONET rings. Also for a subfamily of the “packing” integer programs, we provide the firstNC approximation algorithms; this includes problems such as maximum matchings in hypergraphs, and generalizations. The key to the utility of our method is that it involves sums ofsuperpolynomially many terms, which can however be computed inNC; this superpolynomiality is the bottleneck for some earlier approaches, due to Berger and Rompel and Motwaniet al. A preliminary version of this work appeared inProc. International Colloquim on Automata, Languages and Programming, 1996, pages 562–573. Work done in parts at DIMACS (supported in part by NSF-STC91-19999 and by support from the N.J. Commission on Science and Technology), at the Institute for Advanced Study, Princeton (supported in part by Grant 93-6-6 of the Alfred P. Sloan Foundation), and at the National University of Singapore.     

A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2

The maximum weight matching problem is a fundamental problem in graph theory with a variety of important applications. Recently Manne and Mjelde presented the first self-stabilizing algorithm computing a 2-approximation of the optimal solution. They established that their algorithm stabilizes after O(2ⁿ) (resp. O(3ⁿ)) moves under a central (resp. distributed) scheduler. This paper contributes a new analysis, improving these bounds considerably. In particular it is shown that the algorithm stabilizes after O(nm) moves under the central scheduler and that a modified version of the algorithm also stabilizes after O(nm) moves under the distributed scheduler. The paper presents a new proof technique based on graph reduction for analyzing the complexity of self-stabilizing algorithms.     

Applying graphics hardware to achieve extremely fast geometric pattern matching in two and three dimensional transformation space

We present a GPU-based approach to geometric pattern matching. We reduce this problem to finding the depth (maximally covered point) of an arrangement of polytopes in transformation space and describe hardware assisted (GPU) algorithms which exploit the available set of graphics operations to perform a fast rasterized depth computation. We give two alternatives, one is for translation + scale and the other is for rigid transformations, both have 3-parameters transformation space. We give extensive experimental results showing the running time of our method and its dependence on various parameters.     

An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes

The input to the metric maximum clustering problem with given cluster sizes consists of a complete graph G=(V,E) with edge weights satisfying the triangle inequality, and integers c₁,…,cp. The goal is to find a partition of V into disjoint clusters of sizes c₁,…,cp, maximizing the sum of weights of edges whose two ends belong to the same cluster. We describe an approximation algorithms for this problem with performance guarantee that approaches 0.5 when the cluster sizes are large.     

Maintenance of implication integrity constraints under updates to constraints

Semantic integrity constraints are used for enforcing the integrity of the database as well as for improving the efficiency of the database utilization. Although semantic integrity constraints are usually much more static as compared to the data itself, changes in the data semantics may necessitate corresponding changes in the constraint base. In this paper we address the problems related with maintaining a consistent and non-redundant set of constraints satisfied by the database in the case of updates to the constraint base. We consider implication constraints as semantic integrity constraints. The constraints are represented as conjunctions of inequalities. We present a methodology to determine whether a constraint is redundant or contradictory with respect to a set of constraints. The methodology is based on the partitioning of the constraint base which improves the efficiency of algorithms that check whether a constraint is redundant or contradictory with respect to a constraint base. Received August 19, 1993 / Accepted July 7, 1997     

A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint

We study the problem of scheduling n preemptable jobs in a two-machine flow shop where the first machine is not available for processing during a given time interval. The objective is to minimize the makespan. We propose a polynomial-time approximation scheme for this problem. The approach is extended to solve the problem in which the second machine is not continuously available.     

Routing with multiple quality-of-services constraints: An approximation perspective

Finding a path that satisfies multiple Quality-of-Service (QoS) constraints is vital to the deployment of current emerged services. However, existing algorithms are not very efficient and effective at finding such a path. Moreover, few works focus on three or more QoS constraints. In this paper, we present an enhanced version of fully polynomial time approximation scheme (EFPTAS) for multiconstrainted path optimal (MCOP) problem. Specifically, we make four major contributions. We first allow the proposed algorithm to construct an auxiliary graph, through which the QoS parameters on each of the finding path can be guaranteed not to exceed the given constraints. Then we adopt a concept, called nonlinear definition of path constraints in EFPTAS for reducing both time and space complexity. Also, we enable EFPTAS to run iteratively to facilitate a progressive refinement of the finding result. In addition to these, we identify some “deployment” issues for proposed algorithm, the essential steps that how and when the EFPTAS takes place are presented. By analyzing the proposed algorithm theoretically, we find that the presented EFPTAS can find a (1+ε)-approximation path in the network with time complexity O(|E||V|/ε) (where |E| is the number of edges and |V| is the number of nodes), which outperforms the previous best-known algorithm for MCOP. We conduct an extensive comparison between the algorithm presented in this paper and previous best-known study experimentally, our results indicate that EFPTAS can find a path with low complexity and preferable quality.     

The Data Broadcast Problem with Non-Uniform Transmission Times

Abstract. The Data Broadcast Problem consists of finding an infinite schedule to broadcast a given set of messages so as to minimize a linear combination of the average service time to clients requesting messages, and of the cost of the broadcast. This problem also models the Maintenance Scheduling Problem and the Multi-Item Replenishment Problem. Previous work concentrated on a discrete-time restriction where all messages have transmission time equal to 1. Here, we study a generalization of the model to a setting of continuous time and messages of non-uniform transmission times. We prove that the Data Broadcast Problem is strongly NP -hard, even if the broadcast costs are all zero, and give 3 -approximation algorithms.     

Optimization under uncertainty with applications to design of truss structures

Many real-world engineering design problems are naturally cast in the form of optimization programs with uncertainty-contaminated data. In this context, a reliable design must be able to cope in some way with the presence of uncertainty. In this paper, we consider two standard philosophies for finding optimal solutions for uncertain convex optimization problems. In the first approach, classical in the stochastic optimization literature, the optimal design should minimize the expected value of the objective function with respect to uncertainty (average approach), while in the second one it should minimize the worst-case objective (worst-case or min–max approach). Both approaches are briefly reviewed in this paper and are shown to lead to exact and numerically efficient solution schemes when the uncertainty enters the data in simple form. For general uncertainty dependence however, the problems are numerically hard. In this paper, we present two techniques based on uncertainty randomization that permit to solve efficiently some suitable probabilistic relaxation of the indicated problems, with full generality with respect to the way in which the uncertainty enters the problem data. In the specific context of truss topology design, uncertainty in the problem arises, for instance, from imprecise knowledge of material characteristics and/or loading configurations. In this paper, we show how reliable structural design can be obtained using the proposed techniques based on the interplay of convex optimization and randomization.     

Solving quality control problems with an algorithm for minimax programs with coupled constraints

We propose a systematic algorithm to tackle a set of acceptance sampling problems introduced by Seidel [1] and their generalization when no prior knowledge is assumed. The problems are modeled as minimax problems with coupled or decoupled constraints. We use ideas from recent work on bi-level programming, reformulating the problem as a semi-infinite program with disjunctive constraints and employing a two phase discretization method to solve it. We use the KKT conditions of the inner problem of minimax to tighten the relaxation of the semi-infinite problem obtained by discretization. In addition, to avoid convergence trouble, a strategy based on a feasibility test relative to the objective value of the outer program is used.