Search

We consider the Max-Buying Problem with Limited Supply, in which there are n items, with Ci copies of each item i, and m bidders such that every bidder b has valuation vib for item i. The goal is to find a pricing p and an allocation of items to bidders that maximize the profit, where every item is allocated to at most Ci bidders, every bidder receives at most one item and if a bidder b receives item i then pi ≤ vib. Briest and Krysta presented a 2-approximation for this problem and Aggarwal et al. presented a 4-approximation for the Price Ladder variant where the pricing must be non-increasing (that is, p1 ≥ p2 ≥ … ≥ pn). We present a randomized e/(e - 1)-approximation for the Max-Buying Problem with Limited Supply and, for every ε > 0, a (2 + ε)-approximation for the Price Ladder variant. [ABSTRACT FROM AUTHOR]

In this paper we propose the Online Connected Facility Location problem (OCFL), which is an online version of the Connected Facility Location problem (CFL). The CFL is a combination of the Uncapacitated Facility Location problem (FL) and the Steiner Tree problem (ST). We give a randomized O(log2n)-competitive algorithm for the OCFL via the sample-and-augment framework of Gupta, Kumar, Pál, and Roughgarden and previous algorithms for Online Facility Location (OFL) and Online Steiner Tree (OST). Also, we show that the same algorithm is a deterministic O(logn)-competitive algorithm for the special case of the OCFL with M = 1, where M is a scale factor for the edge costs. [ABSTRACT FROM AUTHOR]

Quantitative financial calculus is dominated by calculations of integrals related to various moments of probability distributions used for modelling. Here, we develop a general technique that facilitates the numerical calculations of options, prices for the difficult case of multi-assets, for the majority of European payoff contracts. The algorithms proposed here rely on known weak convergence results, hence making use of the gaussian probability kernel even when modelling with non-gaussian distributions. In addition, this technique can be employed for calculating greek parameters. We prove that the weak convergence characterizing condition can still be applied under some mild assumption on the payoff function of financial options. [ABSTRACT FROM AUTHOR]

In this paper we analyze the complexity of the maximum cardinality b-matching problem in k-uniform hypergraphs. b-matching is the following problem: for a given b ϵ ⇔ and a hypergraph ]> , |V| = n, a subset ]> with maximum cardinality is sought so that no vertex is contained in more than b hyperedges of M. The b-matching problem is a prototype of packing integer programs with right-hand side b ≥ 1. It has been studied in combinatorics and optimization. Positive approximation results are known for b ≥ 1 and k-uniform hypergraphs (Krysta 2005) and constant factor approximations for general hypergraphs for b = Ώ(logn), (Srinivasan 1999, Srivastav, Stangier 1996, Raghavan, Thompson 1987), but the inapproximability of the problem has been studied only for b = 1 and k-uniform and k-partite hypergraphs (Hazan, Safra, Schwartz 2006). Thus the range from b ϵ [2,logn] is almost unexplored. In this paper we give the first inapproximability result for k-uniform hypergraphs: for every 2 ≤ b ≤ k/logk there no polynomial-time approximation within any ratio smaller than ]> , unless ]> . Our result generalizes the result of Hazan, Safra and Schwartz from b = 1 to any fixed 2 ≤ b ≤ k/logk and k-uniform hypergraphs. But the crucial point is that for the first time we can see how b influences the non-approximability. We consider this result as a necessary step in further understanding the non-approximability of general packing problems. It is notable that the proof of Hazan, Safra and Schwartz cannot be lifted to b ≥ 2. In fact, some new techniques and ingredients are required; the probabilistic proof of the existence of a hypergraph with ″almost″ disjoint b-matching where dependent events have to be decoupled (in contrast to Hazan et al.) and the generation of some sparse hypergraph. [ABSTRACT FROM AUTHOR]

In the context of generating efficient, contention free schedules for inter-node communication through a switch fabric in cluster computing or data center type environments, all-to-all scheduling with equal sized data transfer requests has been studied in the literature [1,3,4]. In this paper, we propose a communication scheduling module (CSM) towards generating contention free communication schedules for many-to-many communication with arbitrary sized data. Towards this end, we propose three approximation algorithms - PST, LDT and SDT. From time to time, the CSM first generates a bipartite graph from the set of received requests, then determines which of these three algorithms gives the best approximation factor on this graph and finally executes that algorithm to generate a contention free schedule. Algorithm PST has a worst case run time of O( max (∆|E|, |E|log(|E|))) and guarantees an approximation factor of 2H2∆− 1, where |E| is the number of edges in the bipartite graph, ∆ is the maximum node degree of the bipartite graph and H2∆− 1 is the (2∆− 1)-th harmonic number. LDT runs in O(|E|2) and has an approximation factor of 2(1 + τ), where τ is a constant defined as a guard band or pause time to eliminate the possibility of contention (in an apparently contention free schedule) caused by system jitter and synchronization inaccuracies between the nodes. SDT gives an approximation factor of 4log(wmax) and has a worst case run time of O(∆|E|log(wmax)), where wmax represents the longest communication time in a set of received requests. [ABSTRACT FROM AUTHOR]

The r-domination search game on graphs is a game-theoretical approach to the investigation of several graph and hypergraph parameters including treewidth and hypertree width. The task is to identify the minimum number of cops sufficient to catch the visible and fast robber. In r-domination search, the robber is being arrested if he resides inside a ball of radius r around some cop. In this setting, the power of the cops does not depend only on how many they are but also on the local topology of the graph around them. This is the main reason why the approximation complexity of the r-domination search game varies considerably, depending on whether r = 0 or r ≥ 1. We prove that this discrepancy is canceled when the game is played in (non-trivial) graph classes that are closed under taking of minors. We give a constant factor approximation algorithm that for every fixed r and graph H, computes the minimum number of cops required to capture the robber in the r-domination game on graphs excluding H as a minor. [ABSTRACT FROM AUTHOR]

Given a graph H = (U,E) and connectivity requirements r = {r(u,v): u,v ϵ R ⊆ U }, we say that H satisfies r if it contains r(u,v) pairwise internally-disjoint uv-paths for all u,v ϵ R. We consider the Survivable Network with Minimum Number of Steiner Points (SN-MSP) problem: given a finite set V of points in a normed space ]> , and connectivity requirements, find a minimum size set S ⊂ M − V of additional points, such that the unit disc graph induced by V = S satisfies the requirements. In the (node-connectivity version of the) Survivable Network Design Problem (SNDP) we are given a graph G = (V,E) with edge costs and connectivity requirements, and seek a min-cost subgraph H of G that satisfies the requirements. Let ]> denote the maximum connectivity requirement. We will show a natural transformation of an SN-MSP instance (V,r) into an SNDP instance (G = (V,E),c,r), such that an α-approximation for the SNDP instance implies an α·O(k2)-approximation algorithm for the SN-MSP instance. In particular, for the most interesting case of uniform requirement r(u,v) = k for all u,v ϵ V, we obtain for SN-MSP the ratio O(k2 ln k), which solves an open problem from [3]. [ABSTRACT FROM AUTHOR]

In the k-edge-connected spanning subgraph problem we are given a graph (V, E) and costs for each edge, and want to find a minimum-cost F ⊂ E such that (V, F) is k-edge-connected. We show there is a constant ε> 0 so that for all k > 1, finding a (1 + ε)-approximation for k-ECSS is NP-hard, establishing a gap between the unit-cost and general-cost versions. Next, we consider the multi-subgraph cousin of k-ECSS, in which we purchase a multi-subsetF of E, with unlimited parallel copies available at the same cost as the original edge. We conjecture that a (1 + Θ(1/k))-approximation algorithm exists, and we describe an approach based on graph decompositions applied to its natural linear programming (LP) relaxation. The LP is essentially equivalent to the Held-Karp LP for TSP and the undirected LP for Steiner tree. We give a family of extreme points for the LP which are more complex than those previously known. [ABSTRACT FROM AUTHOR]

Given a graph with edge lengths and a set of pairs of vertices which should be connected (requirements) the Generalized Steiner Tree Problem (GSTP) asks for a minimum length subgraph that connects every requirement. For the Generalized Steiner Tree Problem restricted to complete graphs with edge lengths 1 and 2, we provide a 1.5-approximation algorithm. It is the first algorithm with the approximation ratio significantly better than 2 for a class of graphs for which GSTP is MAX SNP-hard. [ABSTRACT FROM AUTHOR]

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in O(n3m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial-time approximation algorithm was ]> . [ABSTRACT FROM AUTHOR]

In this paper, we investigate the problem of scheduling weighted jobs on a single machine with a maintenance whose starting time is prior to a given deadline and whose duration is a nondecreasing function of the starting time. We are asked not only to schedule the jobs but also the maintenance such that the total weighted job completion time is minimum. The problem is shown to be weakly NP-hard. In the case that the duration of the maintenance is a concave (and nondecreasing) function of its starting time, we provide two approximation algorithms with approximation ratio of 2 and at most ]> , respectively. [ABSTRACT FROM AUTHOR]

Some of the currently best-known approximation algorithms for network design are based on random sampling. One of the key steps of such algorithms is connecting a set of source nodes to a random subset of them. In a recent work [Eisenbrand,Grandoni,Rothvoβ,Schäfer-SODA΄08], a new technique, core-detouring, is described to bound the mentioned connection cost. This is achieved by defining a sub-optimal connection scheme, where paths are detoured through a proper connected subgraph (core). The cost of the detoured paths is bounded against the cost of the core and of the distances from the sources to the core. The analysis then boils down to proving the existence of a convenient core. For some problems, such as connected facility location and single-sink rent-or-buy, the choice of the core is obvious (i.e., the Steiner tree in the optimum solution). Other, more complex network design problems do not exhibit any such core. In this paper we show that core-detouring can be nonetheless successfully applied. The basic idea is constructing a convenient core by manipulating the optimal solution in a proper (not necessarily trivial) way. We illustrate that by presenting improved approximation algorithms for two well-studied problems: virtual private network design and single-sink buy-at-bulk. [ABSTRACT FROM AUTHOR]

The placement of regenerators in optical networks has become an active area of research during the last years. Given a set of lightpaths in a network G and a positive integer d, regenerators must be placed in such a way that in any lightpath there are no more than d hops without meeting a regenerator. While most of the research has focused on heuristics and simulations, the first theoretical study of the problem has been recently provided in [10], where the considered cost function is the number of locations in the network hosting regenerators. Nevertheless, in many situations a more accurate estimation of the real cost of the network is given by the total number of regenerators placed at the nodes, and this is the cost function we consider. Furthermore, in our model we assume that we are given a finite set of p possible traffic patterns (each given by a set of lightpaths), and our objective is to place the minimum number of regenerators at the nodes so that each of the traffic patterns is satisfied. While this problem can be easily solved when d = 1 or p = 1, we prove that for any fixed d,p ≥ 2 it does not admit a ]> , even if G has maximum degree at most 3 and the lightpaths have length ]> . We complement this hardness result with a constant-factor approximation algorithm with ratio ln (d ·p). We then study the case where G is a path, proving that the problem is NP-hard for any d,p ≥ 2, even if there are two edges of the path such that any lightpath uses at least one of them. Interestingly, we show that the problem is polynomial-time solvable in paths when all the lightpaths share the first edge of the path, as well as when the number of lightpaths sharing an edge is bounded. Finally, we generalize our model in two natural directions, which allows us to capture the model of [10] as a particular case, and we settle some questions that were left open in [10]. [ABSTRACT FROM AUTHOR]

We give a generalization of the method of pessimistic estimators [14], in which we compose estimators by multiplying them. We give conditions on the pessimistic estimators of two expectations, under which the product of the pessimistic estimators is a pessimistic estimator of the product of the two expectations. This approach can be useful when derandomizing algorithms for which one needs to bound a certain probability, which can be expressed as an intersection of multiple events; using our method, one can define pessimistic estimators for the probabilities of the individual events, and then multiply them to obtain a pessimistic estimator for the probability of the intersection of the events. We apply this method to give derandomizations of all known approximation algorithms for the maximum traveling salesman problem and the maximum triangle packing problem: we define simple pessimistic estimators based on the analysis of known randomized algorithms and show that we can multiply them to obtain pessimistic estimators for the expected weight of the solution. This gives deterministic algorithms with better approximation guarantees than what was previously known. [ABSTRACT FROM AUTHOR]

The problem of grooming is central in studies of optical networks. In graph-theoretic terms, it can be viewed as assigning colors to given paths in a graph, so that at most g (the grooming factor) paths of the same color can share an edge. Each path uses an ADM at each of its endpoints, and paths of the same color can share an ADM in a common endpoint. There are two sub-models, depending on whether or not paths that have the same color can use more than two edges incident with the same node (bifurcation allowed and bifurcation not allowed, resp.). The goal is to find a coloring that minimizes the total number of ADMs. In a previous work it was shown that the problem is NP-complete when bifurcation is allowed, even for a star network. In this paper we study the problem for a star network when bifurcation is not allowed. For the case of simple requests - in which only the case of g = 2 is of interest - we present a polynomial-time algorithm, and we study the structure of optimal solutions. We also present results for the case of multiple requests and g = 2, though the exact complexity of this case remains open. We provide two techniques, which lead to ]> -approximation algorithms. Our algorithms reduce the problem of traffic grooming in star networks to several variants of maximum matching problems. [ABSTRACT FROM AUTHOR]

In this paper we consider a sorting problem from railway optimization called train classification, which is NP-hard in general. We introduce two new variants of an earlier developed 2-approximation as well as a new heuristic for finding feasible classification schedules, i.e. solutions for the train classification problem. We evaluate the four algorithms experimentally using various synthetic and real-world traffic instances and further compare them to an exact IP approach. It turns out that the heuristic matches up to the basic approximation, but both are clearly outperformed by our heuristically improved 2-approximations. Finally, with an average objective value of only 5.4 % above optimal, the best algorithm gets close to the real-world schedules of the IP approach, so we obtain very satisfactory practical schedules extremely quickly. [ABSTRACT FROM AUTHOR]

A path is said to be ℓ-bounded if it contains at most ℓ edges. We consider two types of ℓ-bounded disjoint paths problems. In the maximum edge- or node-disjoint path problems MEDP(ℓ) and MNDP(ℓ), the task is to find the maximum number of edge- or node-disjoint ℓ-bounded (s,t)-paths in a given graph G with source s and sink t, respectively. In the weighted edge- or node-disjoint path problems WEDP(ℓ) and WNDP(ℓ), we are also given an integer k ϵ ⇔ and non-negative edge weights ce ϵ ⇔, e ϵ E, and seek for a minimum weight subgraph of G that contains k edge- or node-disjoint ℓ-bounded (s,t)-paths. Both problems are of great practical relevance in the planning of fault-tolerant communication networks, for example. Even though length-bounded cut and flow problems have been studied intensively in the last decades, the ]> -hardness of some 3- and 4-bounded disjoint paths problems was still open. In this paper, we settle the complexity status of all open cases showing that WNDP(3) can be solved in polynomial time, that MEDP(4) is ]> -complete and approximable within a factor of 2, and that WNDP(4) and WEDP(4) are ]> -hard and ]> -complete, respectively. [ABSTRACT FROM AUTHOR]

We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O(logn / loglogn) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on the recent result of Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi to obtain this guarantee. Furthermore, we show how our technique yields stronger approximation bounds in some cases, such as the bounded orientable genus case studied by Oveis Gharan and Saberi. [ABSTRACT FROM AUTHOR]

We consider optimization problems that can be formulated as minimizing the cost of a feasible solution wTx over an arbitrary combinatorial feasible set ]> . For these problems we describe a broad class of corresponding stochastic problems where the cost vector W has independent random components, unknown at the time of solution. A natural and important objective that incorporates risk in this stochastic setting is to look for a feasible solution whose stochastic cost has a small tail or a small convex combination of mean and standard deviation. Our models can be equivalently reformulated as nonconvex programs for which no efficient algorithms are known. In this paper, we make progress on these hard problems. Our results are several efficient general-purpose approximation schemes. They use as a black-box (exact or approximate) the solution to the underlying deterministic problem and thus immediately apply to arbitrary combinatorial problems. For example, from an available δ-approximation algorithm to the linear problem, we construct a δ(1 + ε)-approximation algorithm for the stochastic problem, which invokes the linear algorithm only a logarithmic number of times in the problem input (and polynomial in ]> ), for any desired accuracy level ε> 0. The algorithms are based on a geometric analysis of the curvature and approximability of the nonlinear level sets of the objective functions. [ABSTRACT FROM AUTHOR]

We study the problem of minimizing the diameter of a graph by adding k shortcut edges, for speeding up communication in an existing network design. We develop constant-factor approximation algorithms for different variations of this problem. We also show how to improve the approximation ratios using resource augmentation to allow more than k shortcut edges. We observe a close relation between the single-source version of the problem, where we want to minimize the largest distance from a given source vertex, and the well-known k-median problem. First we show that our constant-factor approximation algorithms for the general case solve the single-source problem within a constant factor. Then, using a linear-programming formulation for the single-source version, we find a (1 + ε)-approximation using O(klogn) shortcut edges. To show the tightness of our result, we prove that any ]> -approximation for the single-source version must use Ώ(klogn) shortcut edges assuming P ≠ NP. [ABSTRACT FROM AUTHOR]

This paper is our third step towards developing a theory of testing monomials in multivariate polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a πΣπ polynomial. We first prove that the first problem is #P-hard and then devise a O*(3ns(n)) upper bound for this problem for any polynomial represented by an arithmetic circuit of size s(n). Later, this upper bound is improved to O*(2n) for πΣπ polynomials. We then design fully polynomial-time randomized approximation schemes for this problem for πΣ polynomials. On the negative side, we prove that, even for πΣπ polynomials with terms of degree ≤ 2, the first problem cannot be approximated at all for any approximation factor ≥ 1, nor ″weakly approximated″ in a much relaxed setting, unless P=NP. For the second problem, we first give a polynomial time λ-approximation algorithm for πΣπ polynomials with terms of degrees no more a constant λ ≥ 2. On the inapproximability side, we give a n(1 − ε)/2 lower bound, for any ε> 0, on the approximation factor for πΣπ polynomials. When the degrees of the terms in these polynomials are constrained as ≤ 2, we prove a 1.0476 lower bound, assuming ]> ; and a higher 1.0604 lower bound, assuming the Unique Games Conjecture. [ABSTRACT FROM AUTHOR]

Given two comparative maps, that is two sequences of markers each representing a genome, the Maximal Strip Recovery problem (MSR) asks to extract a largest sequence of markers from each map such that the two extracted sequences are decomposable into non-overlapping strips (or synteny blocks). This aims at defining a robust set of synteny blocks between different species, which is a key to understand the evolution process since their last common ancestor. In this paper, we add a fundamental constraint to the initial problem, which expresses the biologically sustained need to bound the number of intermediate (non-selected) markers between two consecutive markers in a strip. We therefore introduce the problem δ-gap-MSR, where δ is a (usually small) non-negative integer that upper bounds the number of non-selected markers between two consecutive markers in a strip. Depending on the nature of the comparative maps (i.e., with or without duplicates), we show that δ-gap-MSR is NP-complete for any δ ≥ 1, and even APX-hard for any δ ≥ 2. We also provide two approximation algorithms, with ratio 1.8 for δ= 1, and ratio 4 for δ ≥ 2. [ABSTRACT FROM AUTHOR]

We consider the b-matching problem in a hypergraph on n vertices and edge cardinality bounded by ℓ. Oblivious greedy algorithms achieve approximations of ]> and (ℓ + 1)− 1 independently of b (Krysta 2005). Randomized rounding achieves constant-factor approximations of 1 − ε for large b, namely b = Ώ(ε− 2, ln n), (Srivastav and Stangier 1997). Hardness of approximation results exist for b = 1 (Gonen and Lehmann 2000; Hazan, Safra, and Schwartz 2006). In the range of 1 < b « ln n, no close-to-one, or even constant-factor, polynomial-time approximations are known. The aim of this paper is to overcome this algorithmic stagnation by proposing new algorithms along with the first experimental study of the b-matching problem in hypergraphs, and to provide a first theoretical analysis of these algorithms to some extent. We propose a non-oblivious greedy algorithm and a hybrid algorithm combining randomized rounding and non-oblivious greedy. Experiments on random and real-world instances suggest that the hybrid can, in terms of approximation, outperform the known techniques. The non-oblivious greedy also shows a better approximation in many cases than the oblivious one and is accessible to theoretic analysis. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be an edge-weighted graph, and let w(H) denote the sum of the weights of the edges in a subgraph H of G. Given a positive integer k, the balanced tree partitioning problem requires to cover all vertices in V by a set ]> of k trees of the graph so that the ratio α of ]> to w(T*)/k is minimized, where T* denotes a minimum spanning tree of G. The problem has been used as a core analysis in designing approximation algorithms for several types of graph partitioning problems over metric spaces, and the performance guarantees depend on the ratio α of the corresponding balanced tree partitioning problems. It is known that the best possible value of α is 2 for the general metric space. In this paper, we study the problem in the d-dimensional Euclidean space ℝd, and break the bound 2 on α, showing that ]> for d ≥ 3 and ]> for d = 2. These new results enable us to directly improve the performance guarantees of several existing approximation algorithms for graph partitioning problems if the metric space is an Euclidean space. [ABSTRACT FROM AUTHOR]

A general instance of a Degree-Constrained Subgraph problem consists of an edge-weighted or vertex-weighted graph G and the objective is to find an optimal weighted subgraph, subject to certain degree constraints on the vertices of the subgraph. This paper considers two natural Degree-Constrained Subgraph problems and studies their behavior in terms of approximation algorithms. These problems take as input an undirected graph G = (V,E), with |V| = n and |E| = m. Our results, together with the definition of the two problems, are listed below. The Maximum Degree-Bounded Connected Subgraph problem (MDBCSd) takes as input a weight function ]> and an integer d ≥ 2, and asks for a subset E' ⊆ E such that the subgraph G' = (V,E') is connected, has maximum degree at most d, and Σ e ϵ E'ω(e) is maximized. This problem is one of the classical NP-hard problems listed by Garey and Johnson in [Computers and Intractability, W.H. Freeman, 1979], but there were no results in the literature except for d = 2. We prove that MDBCSd is not in Apx for any d ≥ 2 (this was known only for d = 2) and we provide a ]> -approximation algorithm for unweighted graphs, and a ]> -approximation algorithm for weighted graphs. We also prove that when G has a low-degree spanning tree, in terms of d, MDBCSd can be approximated within a small constant factor in unweighted graphs. The Minimum Subgraph of Minimum Degree ≥ d (MSMDd) problem requires finding a smallest subgraph of G (in terms of number of vertices) with minimum degree at least d. We prove that MSMDd is not in Apx for any d ≥ 3 and we provide an ]> -approximation algorithm for the class of graphs excluding a fixed graph as a minor, using dynamic programming techniques and a known structural result on graph minors. [ABSTRACT FROM AUTHOR]

Energy has become a scarce and expensive resource. There is a growing awareness in society that energy saving is a critical issue. This paper surveys algorithmic solutions to reduce energy consumption in computing environments. We focus on the system and device level. More specifically, we study power-down mechanisms as well as dynamic speed scaling techniques in modern microprocessors. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the weighted number of tardy jobs ( ]> ) on an unbounded batch processing machine. The batch processing machine can process up to B (B ≥ n) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. For a batch of jobs, the processing time of the batch is equal to the largest processing time among the jobs in this batch. In this paper, we design a fully polynomial time approximation scheme (FPTAS) to solve the unbounded batch scheduling problem ]> This is the strongest possible polynomial time approximation result that we can derive for an NP-hard problem (unless P = NP holds). [ABSTRACT FROM AUTHOR]

We study the multiple-strip packing problem, in which the goal is to pack all the rectangles into m vertical strips of unit widths such that the maximum height among strips used is minimized. A number of on-line algorithms for this problem are proposed, in which the decision of delivering the rectangles to strips as well as packing the rectangles in strips must be done on-line. Both randomized and deterministic on-line algorithms are investigated, and all of them are guaranteed to have constant competitive ratios. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be the given graph and GR = (VR,ER) and GC = (VC,EC) be the sub graphs of G such that VR ∩ VC = ⵁ and VR = VC= V. GC is referred to as the cops region and GR is called as the robber region. Initially a robber is placed at some vertex of VR and the cops are placed at some vertices of VC. The robber and cops may move from their current vertices to one of their neighbours. While a cop can move only within the cops region, the robber may move to any neighbour. The robber and cops move alternatively. A vertex v ϵ VC is said to be attacked if the current turn is the robber΄s turn, the robber is at vertex u where u ϵ VR, (u,v) ϵ E and no cop is present at v. The guarding problem is to find the minimum number of cops required to guard the graph GC from the robber΄s attack. We first prove that the decision version of this problem when GR is an arbitrary undirected graph is PSPACE-hard. We also prove that the complexity of the decision version of the guarding problem when GR is a wheel graph is NP-hard. We then present approximation algorithms if GR is a star graph, a clique and a wheel graph with approximation ratios H(n1), 2 H(n1) and ]> respectively, where ]> and n1 = ǀ VR ǀ. [ABSTRACT FROM AUTHOR]

We consider an optimization problem arising in the design of optical networks. We are given a bipartite graph G = (L,R,E) over the node set L = R where the edge set is E ⊆ { [u,v]: u ϵ L, v ϵ R}, and implicitly a collection of all four-nodes cycles in the complete graph over V. The goal is to find a minimum size sub-collection of graphs G1,G2,...,Gp where for each iGi is isomorphic to a cycle over four nodes, and such that the edge set E is contained in the union (over all i) of the edge sets of Gi. Noting that every four edge cycle can be a part of the solution, this covering problem is a special case of the unweighted 4-set cover problem. This specialization allows us to obtain an improved approximation guarantee. Whereas the currently best known approximation algorithm for the general unweighted 4-set cover problem has an approximation ratio of ]> (where Hp denotes the p-th harmonic number), we show that for every εε> 0 there is a polynomial time ]> -approximation algorithm for our problem. Our analysis of the greedy algorithm shows that when applied to covering a bipartite graph using copies of Kq,q bicliques, it returns a feasible solution whose cost is at most ]> where OPT denotes the optimal cost, thus improving the approximation bound by a factor of almost 2. [ABSTRACT FROM AUTHOR]

We consider the scheduling of biprocessor jobs under sum objective (BPSMS). Given a collection of unit-length jobs where each job requires the use of two processors, find a schedule such that no two jobs involving the same processor run concurrently. The objective is to minimize the sum of the completion times of the jobs. Equivalently, we would like to find a sum edge coloring of the given multigraphs, i.e. a partition of its edge set into matchings M1,...,Mt minimizing ]> . This problem is APX-hard even in the case of bipartite graphs [M04]. This special case is closely related to the classic open shop scheduling problem. We give a 1.829-approximation algorithm for BPSMS that combines a configuration LP with greedy methods improving the previously best known ratio of 2 [BBH+98]. The algorithm uses the fractions derived from the configuration LP and a non-standard randomized rounding. We also give a purely combinatorial and practical algorithm for the case of simple graphs, with a 1.8861-approximation ratio. [ABSTRACT FROM AUTHOR]

This paper presents a new serial algorithm for selecting a nearly minimum number of vertex-guards so that all parts of a geographical surface modeled by a TIN (Triangulated Irregular Networks) is covered. Our algorithm selects fewer guards than the best existing algorithms on the average. Based on this approach, a new coarse-grain parallel algorithm for this problem is proposed. It has been showed that the upper bound for total number of guards, selected by this algorithm, is ]> where n is number of vertices in the TIN. Average case analysis and implementation results show that in real TINs even fewer than ]> guards (proved upper bound of needed guards in worse-case) are selected by our serial and parallel algorithms. [ABSTRACT FROM AUTHOR]

We consider the deadline problem and budget problem of the nonlinear time-cost tradeoff project scheduling model in a series-parallel activity network. We develop fully polynomial time approximation schemes for both problems using K-approximation sets and functions, together with series and parallel reductions. [ABSTRACT FROM AUTHOR]

We first consider the problem of finding a maximum stable matching if incomplete lists and ties are both allowed, but ties only for one gender. For this problem we give a simple, linear time 3/2-approximation algorithm, improving on the best known approximation factor 5/3 of Irving and Manlove [5]. Next, we show how this extends to the Hospitals/Residents problem with the same ratio if the residents have strict orders. We also give a simple linear time algorithm for the general problem with approximation factor 5/3, improving the best known 15/8-approximation algorithm of Iwama, Miyazaki and Yamauchi [7]. For the cases considered in this paper it is NP-hard to approximate within a factor of 21/19 by the result of Halldórsson et al. [3]. Our algorithms not only give better approximation ratios than the cited ones, but are much simpler and run significantly faster. Also we may drop a restriction used in [5] and the analysis is substantially more moderate. [ABSTRACT FROM AUTHOR]

The problem of interest is covering a given point set with homothetic copies of several convex containers C1, ..., Ck, while the objective is to minimize the maximum over the dilatation factors. Such k-containment problems arise in various applications, e.g. in facility location, shape fitting, data classification or clustering. So far most attention has been paid to the special case of the Euclidean k-center problem, where all containers Ci are Euclidean unit balls. New developments based on so-called core-sets enable not only better theoretical bounds in the running time of approximation algorithms but also improvements in practically solvable input sizes. Here, we present some new geometric inequalities and a Mixed-Integer-Convex-Programming formulation. Both are used in a very effective branch-and-bound routine which not only improves on best known running times in the Euclidean case but also handles general and even different containers among the Ci. [ABSTRACT FROM AUTHOR]

In the Connected Facility Location(ConFL) problem, we are given a graph G = (V, E) with nonnegative edge cost ce on the edges, a set of facilities ]> , a set of demands, i.e., clients ]> , and a parameter M ≥ 1. Each facility i has a nonnegative opening cost fi and each client j has dj units of demand. Our objective is to open some facilities, say ]> , assign each demand j to some open facility i(j) ϵ F and connect all open facilities using a Steiner tree T such that the total cost, which is ]> , is minimized. We give an improved primal-dual 6.55-approximation algorithm for the ConFL problem which improves the Swamy and Kumar΄s primal-dual 8.55-approximation algorithm [1]. [ABSTRACT FROM AUTHOR]

This paper deals with approximation algorithms for the prize collecting generalized Steiner forest problem, defined as follows. The input is an undirected graph G = (V,E), a collection T = {T1, ...,Tk}, each a subset of V of size at least 2, a weight function w:E →ℝ + , and a penalty function p:T →ℝ + . The goal is to find a forest F that minimizes the cost of the edges of F plus the penalties paid for subsets Ti whose vertices are not all connected by F. Our main result is a combinatorial ]> -approximation for the prize collecting generalized Steiner forest problem, where n ≥ 2 is the number of vertices in the graph. This obviously implies the same approximation for the special case called the prize collecting Steiner forest problem (all subsets Ti are of size 2). The approximation ratio we achieve is better than that of the best known combinatorial algorithm for this problem, which is the 3-approximation of Sharma, Swamy, and Williamson [13]. Furthermore, our algorithm is obtained using an elegant application of the local ratio method and is much simpler and practical, since unlike the algorithm of Sharma et al., it does not use submodular function minimization. Our approach gives a ]> -approximation for the prize collecting Steiner tree problem (all subsets Ti are of size 2 and there is some root vertex r that belongs to all of them). This latter algorithm is in fact the local ratio version of the primal-dual algorithm of Goemans and Williamson [7]. Another special case of our main algorithm is Bar-Yehuda΄s local ratio ]> -approximation for the generalized Steiner forest problem (all the penalties are infinity) [3]. Thus, an important contribution of this paper is in providing a natural generalization of the framework presented by Goemans and Williamson, and later by Bar-Yehuda. [ABSTRACT FROM AUTHOR]

Truthful mechanism, as a type of mechanism design is considered a subfield of economic theory. It is characterized by formulating rules of a game intended to attain a specific outcome, which is concept born out of the game theory, as well as, solution concept. In deadline scheduling problem, there is one central server and m machines. Give a set of jobs, the central server intends to distribute the jobs to each machine based on the reported deadline truthfully. In this paper, we first demonstrate the criteria for truthfulness in deadline scheduling, and we provide a mechanism, which consists of an allocation algorithm and a payment scheme, using randomized techniques. We also compute the competitive ratio for different objective functions. [ABSTRACT FROM AUTHOR]

A discussion on rotations, continued fractions and rotational approximation that appeared in the book "Dynamics in One Complex Variable," third edition, by John Milnor is presented.

Given a graph G, a k-dominating set of G is a subset S of its vertices with the property that every vertex of G is either in S or has at least k neighbors in S. We present a new incremental distributed algorithm to construct a k-dominating set. The algorithm constructs a monotone family of dominating sets D1 ⊆ D2... ⊆ Di ... ⊆ Dk such that each Di is an i-dominating set. For unit disk graphs, the size of each of the resulting i-dominating sets is at most six times the optimal. [ABSTRACT FROM AUTHOR]

A random geometric graph ]> is obtained by spreading n points uniformly at random in a unit square, and by associating a vertex to each point and an edge to each pair of points at Euclidian distance at most r. Such graphs are extensively used to model wireless ad-hoc networks, and in particular sensor networks. It is well known that, over a critical value of r, the graph is connected with high probability. In this paper we study the robustness of the connectivity of random geometric graphs in the supercritical phase, under deletion of edges. In particular, we show that, for a sufficiently large r, any cut which separates two components of Θ(n) vertices each contains Ώ(n2r3) edges with high probability. We also present a simple algorithm that, again with high probability, computes one such cut of size O(n2r3). From these two results we derive a constant expected approximation algorithm for the β-balanced cut problem on random geometric graphs: find an edge cut of minimum size whose two sides contain at least βn vertices each. [ABSTRACT FROM AUTHOR]

We study the following optimization problem: the input is a multigraph G=(V,E) and an integer parameter g. A feasible solution consists of a (not necessarily proper) coloring of E with colors 1, 2, ..., g. Denote by d(v,i) the number of edges colored i incident to v. The objective is to minimize ]> , which roughly corresponds to the ˵imbalance″ of the edge coloring. This problem was proposed by Berry and Modiano (INFOCOM 2004), with the goal of optimizing the deployment of tunable ports in optical networks. Following them we call the optimization problem MTPS – Minimum Tunable Port with Symmetric Assignments. Among other results, they give a reduction from Edge Coloring showing that MTPS is NP-Hard and then give a 2-approximation algorithm. We give a (3/2)-approximation algorithm. Key to this problem is the following question: given a multigraph G=(V,E) of maximum degree g, what fraction of the vertices can be properly edge-colored in a coloring with g colors, where a vertex is properly edge-colored if the edges incident to it have different colors? Our main lemma states that there is such a coloring with half of the vertices properly edge-colored. For g ≤4, two thirds of vertices can be made properly edge-colored. Our algorithm is based on g Maximum Matching computations (total running time ]> ) and a local optimization procedure, which by itself gives a 2-approximation. An interesting analysis gives an expected O((gn + m) log(gn +m)) running time for the local optimization procedure. [ABSTRACT FROM AUTHOR]