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.     

Approximation results for a min-max location-routing problem

This paper studies a min-max location-routing problem, which aims to determine both the home depots and the tours for a set of vehicles to service all the customers in a given weighted graph, so that the maximum working time of the vehicles is minimized. The min-max objective is motivated by the needs of balancing or fairness in vehicle routing applications. We have proved that unless NP=P, it is impossible for the problem to have an approximation algorithm that achieves an approximation ratio of less than 4/3. Thus, we have developed the first constant ratio approximation algorithm for the problem. Moreover, we have developed new approximation algorithms for several variants, which improve the existing best approximation ratios in the previous literature.     

Approximating the single source unsplittable min-cost flow problem

In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing. Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem. Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001     

平方度量动态设施选址问题的近似算法

研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题. 研究中首先利用原始对偶技巧得到 9-近似算法, 然后利用贪婪增广技巧将近似比改进到2.606, 最后讨论了该问题的相应变形问题.     

On a version of the problem of choosing a vector subset

The NP-completeness is proved of the problem of choosing some subset of “similar” vectors. One of the variants of the a posteriori (off-line) noise-proof detection problem of an unknown repeating vector in a numeric sequence can be reduced to this problem in the case of additive noise. An approximation polynomial algorithm with a guaranteed performance bound is suggested for this problem in the case of a fixed space dimension.     

Routing vehicles to minimize fuel consumption

We consider a generalization of the capacitated vehicle routing problem known as the cumulative vehicle routing problem in the literature. Cumulative VRPs are known to be a simple model for fuel consumption in VRPs. We examine four variants of the problem, and give constant factor approximation algorithms. Our results are based on a well-known heuristic of partitioning the traveling salesman tours and the use of the averaging argument.     

An investigation into two bin packing problems with ordering and orientation implications

This paper considers variants of the one-dimensional bin packing (and stock cutting) problem in which both the ordering and orientation of items in a container influences the validity and quality of a solution. Two new real-world problems of this type are introduced, the first that involves the creation of wooden trapezoidal-shaped trusses for use in the roofing industry, the second that requires the cutting and scoring of rectangular pieces of cardboard in the construction of boxes. To tackle these problems, two variants of a local search-based approximation algorithm are proposed, the first that attempts to determine item ordering and orientation via simple heuristics, the second that employs more accurate but costly branch-and-bound procedures. We investigate the inevitable trade-off between speed and accuracy that occurs with these variants and highlight the circumstances under which each scheme is advantageous.     

Reoptimization of the metric deadline TSP

The reoptimization version of an optimization problem deals with the following scenario: Given an input instance together with an optimal solution for it, the objective is to find a high-quality solution for a locally modified instance.In this paper, we investigate several reoptimization variants of the traveling salesman problem with deadlines in metric graphs (Δ-DlTSP). The objective in the Δ-DlTSP is to find a minimum-cost Hamiltonian cycle in a complete undirected graph with a metric edge cost function which visits some of its vertices before some prespecified deadlines. As types of local modifications, we consider insertions and deletions of a vertex as well as of a deadline.We prove the hardness of all of these reoptimization variants and give lower and upper bounds on the achievable approximation ratio which are tight in most cases.     

A scheme of approximation solution of problem 1 |r j|L max

The strongly NP-hard scheduling problem of minimizing the maximum lateness on one machine subject to job release dates is under study. We present a general scheme of approximation solution of the problem which is based on searching for a given problem instance another instance, closest to the original in some metric and belonging to a known polynomially solvable class of instances. For a few concrete variants of the scheme (using different polynomially solvable classes of instances) some analytic formulas are found that make it possible, given a problem instance, to compute easily an upper bound on the absolute error of the solution obtained by a chosen scheme.     

The complexity of maximum matroid-greedoid intersection and weighted greedoid maximization

The maximum intersection problem for a matroid and a greedoid, given by polynomial-time oracles, is shown NP-hard by expressing the satisfiability of boolean formulas in 3-conjunctive normal form as such an intersection. The corresponding approximation problems are shown NP-hard for certain approximation performance bounds. Moreover, some natural parameterized variants of the problem are shown W[P]-hard. The results are in contrast with the maximum matroid-matroid intersection which is solvable in polynomial time by an old result of Edmonds. We also prove that it is NP-hard to approximate the weighted greedoid maximization within 2^nO(1) where n is the size of the domain of the greedoid.     

Most probable explanations in Bayesian networks: Complexity and tractability

One of the key computational problems in Bayesian networks is computing the maximal posterior probability of a set of variables in the network, given an observation of the values of another set of variables. In its most simple form, this problem is known as the MPE-problem. In this paper, we give an overview of the computational complexity of many problem variants, including enumeration variants, parameterized problems, and approximation strategies to the MPE-problem with and without additional (neither observed nor explained) variables. Many of these complexity results appear elsewhere in the literature; other results have not been published yet. The paper aims to provide a fairly exhaustive overview of both the known and new results.     

Approximation hardness of min-max tree covers

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees. Our technique can also be applied to improve inapproximability bounds for min-max problems that use other covering objectives, such as stars, paths, and tours.     

Transfer function identification from impulse response via a new set of orthogonal hybrid functions (HF)

The present work proposes a new set of hybrid functions (HF) which evolved from the synthesis of sample-and-hold functions (SHF) and triangular functions (TF). Traditional block pulse functions (BPF) still continue to be attractive to many researchers in the arena of control theory. Block pulse functions also gave birth to a few useful variants. Two such variants are SHF and TF. The former is efficient for analyzing sample-and-hold control systems, while triangular functions established their superiority in obtaining piecewise linear solution of various control problems. After developing the basic theory of HF, a few square integrable functions are approximated via this set in a piecewise linear manner. For such approximation, it is shown, the mean integral square error (MISE) is much less than block pulse function based approximation. The operational matrices for integration in HF domain are also derived. Finally, this new set is employed for solving identification problem from impulse response data. The results are compared with the solutions obtained via BPF, SHF, TF, etc. and many illustrations are presented.     

Algorithms for separable nonlinear least squares with application to modelling time-resolved spectra

The multiexponential analysis problem of fitting kinetic models to time-resolved spectra is often solved using gradient-based algorithms that treat the spectral parameters as conditionally linear. We make a comparison of the two most-applied such algorithms, alternating least squares and variable projection. A numerical study examines computational efficiency and linear approximation standard error estimates. A new derivation of the Fisher information matrix under the full Golub-Pereyra gradient allows a numerical comparison of parameter precision under variable projection variants. Under the criteria of efficiency, quality of standard error estimates and parameter precision, we conclude that the Kaufman variable projection technique performs well, while techniques based on alternating least squares have significant disadvantages for application in the problem domain.     

Eigenvalue Problems for Fredholm Integral Operators

The calculation of an approximation to the eigenelements ofa Fredholm integral operator can be reduced, using the Nyströmmethod, to the solution of an algebraic eigenvalue problem.To reduce the size of the system of equations to be solved,we propose two iterative variants. In the case of a self-adjointoperator, a special integration rule can be used to regularizethe system of equations. In this case, orthogonality relationscan be introduced for close or multiple eigenvalues.     

Satisfactory graph partition,variants, and generalizations

The Satisfactory Partition problem asks for deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [M. Gerber, D. Kobler, Algorithmic approach to the satisfactory graph partitioning problem, European Journal of Operational Research 125 (2000) 283–291] and studied further by other authors. In this paper we first review some applications and related problems. Then, we survey structural, complexity, and approximation results obtained for Satisfactory Partition and for some of its variants and generalizations. A list of open questions concludes this survey.     

混合图上最小-最大圈覆盖问题的近似算法

考虑一个混合图上的最小-最大圈覆盖问题。给定一个正整数k和一个混合加权图G=（V,E,A）,这里V表示顶点集,E表示边集,A表示弧集。E中的每条边和A中的每条弧关联一个权重。问题的要求是确定k个环游,使得这k个环游能够经过A中的所有弧。目标是极小化最大环游的权重。该问题是运筹学和计算机科学中一个重要的组合优化问题,它和它的变形在诸如快递配送、垃圾收集、积雪清扫等相关行业具有广泛应用。针对该问题,通过结合二分搜索和环游撕裂的技巧,首次给出了一个近似比为37/5的近似算法。     

Stochastic recursive inclusions with non-additive iterate-dependent Markov noise

In this paper we study the asymptotic behaviour of stochastic approximation schemes with set-valued drift function and non-additive iterate-dependent Markov noise. We show that a linearly interpolated trajectory of such a recursion is an asymptotic pseudotrajectory for the flow of a limiting differential inclusion obtained by averaging the set-valued drift function of the recursion w.r.t. the stationary distributions of the Markov noise. The limit set theorem by Benaim is then used to characterize the limit sets of the recursion in terms of the dynamics of the limiting differential inclusion. We then state two variants of the Markov noise assumption under which the analysis of the recursion is similar to the one presented in this paper. Scenarios where our recursion naturally appears are presented as applications. These include controlled stochastic approximation, subgradient descent, approximate drift problem and analysis of discontinuous dynamics all in the presence of non-additive iterate-dependent Markov noise.     

Generalized assignment problem: Truthful mechanism design without money

We propose truthful approximation mechanisms for strategic variants of the generalized assignment problem (GAP) in a payment-free environment. In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In our strategic variant, bins are held by strategic agents and each agent may hide its willingness to receive some items in order to obtain items of higher values. The model has applications in auctions with budgeted bidders.     

Eigenvalue Characterization and Computation for the Laplacian on General 2-D Domains

In this paper, we address the problem of determining and efficiently computing an approximation to the eigenvalues of the negative Laplacian ? ? on a general domain Ω ? ?² subject to homogeneous Dirichlet or Neumann boundary conditions. The basic idea is to look for eigenfunctions as the superposition of generalized eigenfunctions of the corresponding free space operator, in the spirit of the classical method of particular solutions (MPS). The main novelties of the proposed approach are the possibility of targeting each eigenvalue independently without the need for extensive scanning of the positive real axis and the use of small matrices. This is made possible by iterative inclusion of more basis functions in the expansions and a projection idea that transforms the minimization problem associated with MPS and its variants into a relatively simple zero-finding problem, even for expansions with very few basis functions.