text:
Fixed-Parameter Approximations for k-Center Problemsin Low Highway Dimension GraphsI would like to thank Jochen Könemann for reading an early draft of this paper. Also I would like to thank two anonymous reviewers for their insightful remarks that helped to greatly improve the paper. A preliminary version appeared at the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015). This work was supported by ERC Starting Grant PARAMTIGHT (No. 280152), project CE-ITI (GAČR no. P202/12/G061) of the Czech Science Foundation, and by the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004).

# Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs††thanks: I would like to thank Jochen Könemann for reading an early draft of this paper. Also I would like to thank two anonymous reviewers for their insightful remarks that helped to greatly improve the paper. A preliminary version appeared at the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015). This work was supported by ERC Starting Grant PARAMTIGHT (No. 280152), project CE-ITI (GAČR no. P202/12/G061) of the Czech Science Foundation, and by the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004).

Andreas Emil Feldmann KAM, Charles University, Czechia
feldmann.a.e@gmail.com
###### Abstract

We consider the -Center problem and some generalizations. For -Center a set of center vertices needs to be found in a graph with edge lengths, such that the distance from any vertex of  to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by Abraham et al. [SODA 2010].

We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations, where the two paradigms are combined. In particular, we prove that for any computing a -approximation is W[2]-hard for parameter , and NP-hard for graphs with highway dimension . The latter does not rule out fixed-parameter -approximations for the highway dimension parameter , but implies that such an algorithm must have at least doubly exponential running time in if it exists, unless ETH fails. On the positive side, we show how to get below the approximation factor of  by combining the parameters and : we develop a fixed-parameter -approximation with running time . Additionally we prove that, unless P=NP, our techniques cannot be used to compute fixed-parameter -approximations for only the parameter .

We also provide similar fixed-parameter approximations for the weighted -Center and -Partition problems, which generalize -Center.

\newaliascnt

lemthm \newaliascntcrlthm \newaliascntdfnthm \newaliascntpropthm \aliascntresetthelem \aliascntresetthecrl \aliascntresetthedfn \NewEnvirondoitall\noexpandarg\IfSubStr\BODY\IfSubStr\BODY
\IfSubStr\BODY&

 \BODY

## 1 Introduction

In this paper we consider the -Center problem and some of its generalizations. For the problem, locations need to be found in a network, so that every node in the network is close to a location. More formally, the input is specified by an integer and a graph with positive edge lengths. A feasible solution to the problem is a set of centers such that . The aim is to minimize the maximum distance between any vertex and its closest center. That is, let denote the shortest-path distance between two vertices of according to the edge lengths, and be the ball of radius around . We need to minimize the cost of the solution , which is the smallest value  for which . We say that a center covers a vertex if . Hence we can see the problem as finding centers covering all vertices of with balls of minimum radius.

The -Center problem naturally arises in transportation networks, where, for instance, it models the need to find locations for manufacturing plants, hospitals, police stations, or warehouses under a budget constraint. Unfortunately it is NP-hard to solve the problem in general [29], and the same holds true in various models for transportation networks, such as planar graphs [28] and metrics using Euclidean (), Manhattan (), or Chebyshev () distance measures [14]. A more recent model for transportation networks uses the highway dimension, which was introduced as a graph parameter by Abraham et al. [1]. The intuition behind its definition comes from the empirical observation [7, 8] that in a road network, starting from any point and travelling to a sufficiently far point along the quickest route, one is bound to pass through some member of a sparse set of “access points”. There are several formal definitions for the highway dimension that differ slightly [1, 3, 2, 16]. All of them, however, imply the existence of locally sparse shortest path covers. Therefore, in this paper we consider this as a generalization of the original highway dimension definitions.

###### Definition \thedfn.

Given a graph with edge lengths and a scale , let contain all vertex sets given by shortest paths in of length more than and at most . A shortest path cover is a hitting set for the set system , i.e., for each . We call the vertices in hubs. A hub set is called locally -sparse if for every vertex the ball of radius around contains at most vertices from . The highway dimension of is the smallest integer such that there is a locally -sparse shortest path cover for every scale in .

Abraham et al. [1] introduced the highway dimension in order to explain the fast running times of various shortest-path heuristics. However, they also note that “conceivably, better algorithms for other [optimization] problems can be developed and analysed under the small highway dimension assumption”. In this paper we investigate the -Center problem and focus on graphs with low highway dimension as a model for transportation networks. One advantage of using such graphs is that they do not only capture road networks but also networks with transportation links given by air-traffic or railroads. For instance, introducing connections due to airplane traffic will render a network non-planar, while it can still be argued to have low highway dimension: longer flight connections tend to be served by bigger but sparser airports, which act as hubs. This can, for instance, be of interest in applications where warehouses need to be placed to store and redistribute goods of globally operating enterprises. Unfortunately however, in this paper we show that the -Center problem also remains NP-hard on graphs with low highway dimension.

Two popular and well-studied ways of coping with NP-hard problems is to devise approximation [29, 30] and parameterized [13, 11] algorithms. For the former we demand polynomial running times but allow the computed solution to deviate from the optimum cost. That is, we compute a -approximation, which is a feasible solution with a cost that is at most times worse than the best possible for the given instance. A problem that allows a polynomial-time -approximation for any input is -approximable, and is called the approximation factor of the corresponding algorithm. The rationale behind parameterized algorithms is that some parameter of the input is small and we can therefore afford running times that are super-polynomial in , while, however, we demand optimum solutions. That is, we compute a solution with optimum cost in time for some computable function that is independent of the input size . A problem that has a fixed-parameter algorithm for a parameter is called fixed-parameter tractable (FPT) for . What however, if a problem is neither approximable nor FPT? In this case it may be possible to overcome the complexity by combining these two paradigms. In particular, the objective becomes to develop fixed-parameter -approximation (-FPA) algorithms that compute a -approximation in time for a parameter .

The idea of combining the paradigms of approximation and fixed-parameter tractability has been suggested before. However, only few results are known for this setting (cf. [26]). In this paper we show that for the -Center problem it is possible to overcome lower bounds for its approximability and its fixed-parameter tractability using parameterized approximations. For many different input classes, such as planar graphs [28], and - and -metrics [14], the -Center problem is -approximable via the algorithm for general metrics of Hochbaum and Shmoys [19], but not -approximable for any , unless P=NP. We show that, unless FPT=W[2], for general graphs there is no -FPA algorithm for the parameter . Additionally, we prove that, unless P=NP, -Center is not -approximable on graphs with highway dimension . This does not rule out -FPA algorithms for the highway dimension parameter, and we leave this as an open problem. However, the result implies that if such an algorithm exists, then its running time must be enormous. In particular, unless the exponential time hypothesis (ETH) [21, 22] fails, there can be no -FPA algorithm with doubly exponential running time in the highway dimension .

In face of these hardness results, it seems tough to beat the approximation factor of for -Center, even when considering fixed-parameter approximations for either the parameter or the highway dimension. Our main result, however, is that we can obtain a significantly better approximation factor for -Center when combining these two parameters. Such an algorithm is useful when aiming for high quality solutions, for instance, in a setting where only few warehouses should be built in a transportation network, since warehouses are expensive or stored goods should not be too dispersed for logistical reasons.

It is known [2] that locally -sparse shortest path covers can be computed for graphs of highway dimension in polynomial time, if each shortest path is unique. We will assume that the latter is always the case, since we can slightly perturb the edge lengths. In particular, using a folklore method we may distort distances such that any -approximation in the perturbed instance also is a -approximation in the original instance. In the following theorem summarizing our main result, the first given running time assumes approximate shortest path covers. In general it is NP-hard to compute the highway dimension [16], but it is unknown whether this problem is FPT. If this is the case and the running time is sufficiently small, this can be used as an oracle in our algorithm.

###### Theorem 1.

For any graph with vertices and highway dimension , there is an algorithm that computes a -approximation to the -Center problem in time . If locally -sparse shortest path covers are given by an oracle, the running time is .

We leave open whether approximation factors better than can be obtained for the combined parameter . It was recently proved [15] that -Center is W[1]-hard for this parameter , but no inapproximability is implied by this result. We note that a recent result by Becker et al. [10] obtains a fixed-parameter approximation scheme for -Center in low highway dimension graphs, i.e., an algorithm computing a -approximation in time for any . However, this result needs a more restrictive definition of the highway dimension than used in this paper. In particular, there are graphs that have bounded highway dimension due to Section 1, but for which the algorithm by Becker et al. [10] is not applicable (for a more detailed discussion on the relation between different definitions of highway dimension we refer to [16, Section 9]). Although we also leave open whether -FPA algorithms exist for the parameter alone, we are able to prove that the techniques we use for Theorem 1 cannot omit using both and as parameters. To obtain a -FPA algorithm with running time for any function independent of , a lot more information of the input would need to be exploited than the algorithm of Theorem 1 does. To explain this, we now turn to the used techniques.

### 1.1 Used techniques

A crucial observation for our algorithm is that at any scale , a graph of low highway dimension is structured in the following way (see Figure 1). We will prove that the vertices are either at distance at most from some hub, or they lie in clusters of diameter at most that are at distance more than from each other. Hence, for the cost of the optimum -Center solution, at scale a center that resides in a cluster cannot cover any vertices of some other cluster. In this sense the clusters are “independent” of each other. At the same time we are able to bound the number of hubs of scale in terms of and the highway dimension. Roughly, this is comparable to graphs with small vertex cover, since the vertices that are not part of a vertex cover form an independent set. In this sense the highway dimension is a generalization of the vertex cover number (this is in fact the reason why computing the highway dimension is NP-hard [16]).

At the same time the -Center problem is a generalization of the Dominating Set problem. This problem is W[2]-hard [13], which, as we will show, is also why -Center is W[2]-hard to approximate for parameter . However, Dominating Set is FPT using the vertex cover number as the parameter [5]. This is one of the reasons why combining the two parameters and yields a -FPA algorithm for -Center. In fact the similarity seems so striking at first that one is tempted to reduce the problem of finding a -approximation for -Center on low highway dimension graphs to solving Dominating Set on a graph of low vertex cover number. However, it is unclear how this can be made to work. Instead we devise an involved algorithm that is driven by the intuition that the two problems are similar.

The algorithm will guess the cost of the optimum solution in order to exploit the structure of the graph given by the locally -sparse shortest path cover for scale . In particular, the shortest path covers of other scales do not need to be locally sparse in order for the algorithm to succeed. We will show that there are graphs for which -Center is not -approximable, unless P=NP, and for which the shortest path cover for scale is locally -sparse. Hence our techniques, which only consider the shortest path cover of scale , cannot yield a -FPA algorithm for parameter . The catch is though that the reduction produces graphs which do not have locally sparse shortest path covers for scales significantly larger than . Hence a -FPA algorithm for parameter might still exist. However, such an algorithm would have to take larger scales into account than just , and as mentioned above, it would have to have at least doubly exponential running time in .

Proving that no -FPA algorithm for parameter exists for -Center, unless FPT=W[2], is straightforward given the original reduction of Hsu and Nemhauser [20] from the W[2]-hard Dominating Set problem. For parameter , however, we develop some more advanced techniques. For the reduction we show how to construct a graph of low highway dimension given a metric of low doubling dimension (see Section 4 for a formal definition), so that distances between vertices are preserved by a factor. The doubling dimension [18] is a parameter that captures the bounded volume growth of metrics, such as given by Euclidean and Manhattan distances. Since -Center is not -approximable in -metrics [14], unless P=NP, and these have constant doubling dimension, we are able to conclude that the hardness translates to graphs of highway dimension .

### 1.2 Generalizations

In addition to -Center, in Section 5 we obtain similar positive results for two generalizations of the problem by appropriately modifying our techniques. For the weighted -Center problem, the vertices have integer weights and the objective is to choose centers of total weight at most to cover all vertices with balls of minimum radius. This problem is -approximable [19, 29] and no better approximation factor is known. However, we are able to modify our techniques to obtain a -FPA algorithm for the combined parameter .

An alternative way to define the -Center problem is in terms of finding a star cover of size in a metric, where the cost of the solution is the longest of any star edge in the solution. More generally, in their seminal work Hochbaum and Shmoys [19] defined the -Partition problem. Here a family of (unweighted) graphs is given and the aim is to partition the vertices of a metric into sets and connect the vertices of each set by a graph from the family . The solution cost is measured by the “bottleneck”, which is the longest distance between any two vertices of the metric that are connected by an edge in a graph from the family . The case when contains only stars is exactly the -Center problem, given the shortest-path metric as input. The -Partition problem is -approximable [19], where is the largest diameter of any graph in . We show that a -FPA algorithm for the combined parameter exists, where is the largest radius of any graph in . Hence for graph families in which this improves on the general algorithm by Hochbaum and Shmoys [19]. This is for example the case when contains “stars of paths”, i.e., stars for which each edge is replaced by a path of length at most . The diameter of such a graph can be , while the radius is at most , and hence .

### 1.3 Related work

Given its applicability to various problems in transportation networks, but also in other contexts such as image processing and data-compression, the -Center problem has been extensively studied in the past. We only mention closely related results here, that were not mentioned before. For parameters clique-width and tree-width, Katsikarelis et al. [23] show that -Center is W[1]-hard, but they also give fixed-parameter approximation schemes for each of these parameters. For the tree-depth parameter, they show that the problem is FPT. For unweighted planar and map graphs the -Center problem is FPT [12] for the combined parameter , where is the cost of the optimum solution. Note though that and are somewhat opposing parameters in the sense that typically if is small then will be large, and vice versa. A very recent result [24] gives an efficient polynomial-time approximation scheme (EPTAS) for -Center on weighted planar graphs, which approximates both the optimum cost and the number of centers . That is, in time the algorithm computes a -approximation that uses at most centers, for any . Interestingly, this immediately implies a fixed-parameter approximation scheme for parameters and on weighted planar graphs: setting to a value smaller than forces the algorithm to compute a solution with at most centers (since is an integer), while the cost is within an -factor of the optimum. Marx and Pilipczuk [27] prove that in planar graphs an optimum -Center solution can be computed in time . On the other hand, a recent result [15] shows that -Center is W[1]-hard in planar graphs with constant doubling dimension, for the combined parameter , where is the highway dimension and the treewidth of the input graph. Thus this problem remains hard, even when assuming that it abides to all aforementioned models of transportation networks at once. For any metric an -FPA algorithm for the combined parameter can be obtained [4], where is the dimension of the geometric space. This can also be generalized [15] to an -FPA algorithm for the combined parameter , where is the doubling dimension.

Abraham et al. [1] introduced the highway dimension, and study it in several papers [1, 3, 2]. Their main interest is in explaining the good performance of various shortest-path heuristics assuming low highway dimension. In [2] they show that a locally -sparse shortest path cover can be computed in polynomial time for any scale if the highway dimension of the input graph is , and each shortest path is unique. Feldmann et al. [16] consider computing approximations for various other problems that naturally arise in transportation networks. They show that quasi-polynomial time approximation schemes can be obtained for problems such as Travelling Salesman, Steiner Tree, or Facility Location, if the highway dimension is constant. For this however a more restrictive definition of the highway dimension than used here is needed (see [16, Section 9] for more details). The algorithms are obtained by probabilistically embedding a low highway dimension graph into a bounded treewidth graph while introducing arbitrarily small distortions of distances. Known algorithms to compute optimum solutions on low treewidth graphs then imply the approximation schemes. It is interesting to note that this approach does not work for the -Center problem since, in contrast to the above mentioned problems, its objective function is not linear in the edge lengths. As noted before however, a recent result by Becker et al. [10] obtains a fixed-parameter approximation scheme for -Center for combined parameter using a deterministic embedding, building on the results in [16]. But again, for this the more restrictive definition of highway dimension also used in [16] is needed. The only other theoretical results on the highway dimension that we are aware of at this point are by Bauer et al. [9] and by Kosowski and Viennot [25]. Bauer et al. [9] show that for any graph there exist edge lengths such that the highway dimension is , where is the pathwidth of . Kosowski and Viennot [25] introduce the skeleton dimension of a graph and compare it to the highway dimension in the context of shortest path heuristics.

## 2 k-Center and highway dimension versus Dominating Set and vertex covers

We begin by observing that the vertices of a low highway dimension graph are highly structured for any scale : the vertices that are far from any hub of a shortest path cover for scale are clustered into sets of small diameter and large inter-cluster distance (see Figure 1). A similar observation was already made in [16], where clusters were called towns. We need a slightly different definition of clusters than in [16] however, which is why we do not use the same terminology here. For a set let be the shortest-path distance from to the closest vertex in .

###### Definition \thedfn.

Fix and a shortest path cover for scale in a graph . We call an inclusion-wise maximal set with for all a cluster, and we denote the set of all clusters by . The non-cluster vertices are those which are not contained in any cluster of .

Note that the set is specific for the scale and the hub set . The following lemma summarizes the structure of the clusters and non-cluster vertices. Here we let be the minimum distance between vertices of two sets and .

###### Lemma \thelem.

Let be the cluster set for a scale and a shortest path cover . For each non-cluster vertex , . The diameter of any cluster is at most , and for any distinct pair of clusters .

###### Proof.

The first two claims follow immediately from the definition of the clusters. For the third claim let , such that any cluster is a subset of . We first argue that there are no vertices for which . If these existed, by Section 1 there would be a hub hitting the shortest path between them. However, this path would have length since and  are at distance more than  from , contradicting our assumption that .

As a consequence, for any three vertices with and we have , and since we know that , this implies that in fact . Hence the relation of being at distance at most in is transitive, and it is obviously also symmetric and reflexive, i.e., it is an equivalence relation on . Moreover, any two vertices that do not belong to the same equivalence class, i.e. , must be at distance more than , as . By Section 2 the clusters are exactly the equivalence classes of , and so for any two distinct clusters . ∎

A vertex cover is a subset of vertices such that every edge is incident to some vertex of . In particular, if all edges have unit length, then a shortest path cover for scale is a vertex cover. Hence shortest path covers are generalizations of vertex covers. A dominating set is a subset of vertices such that every vertex is adjacent to some vertex of . In a graph with unit edge lengths, a feasible -Center solution of cost  is a dominating set. In this sense the -Center problem is a generalization of the Dominating Set problem, for which a dominating set of minimum size needs to be found. The Dominating Set problem is -hard [13] for its canonical parameter (i.e., the size of the optimum dominating set), but it is FPT [5] for the parameter given by the vertex cover number, which is the size of the smallest vertex cover of a given graph. As the following simple lemma shows, if is the cost of the optimum -Center solution, the number of hubs of the shortest path cover is bounded in and the local sparsity of . Thus our setting generalizes the Dominating Set problem on graphs with bounded vertex cover number. It is interesting to note that in contrast to the Dominating Set problem being FPT for the vertex cover number [5], our more general setting is W[1]-hard [15].

###### Lemma \thelem.

Let be the optimum cost of the -Center problem in a given instance . If a shortest path cover of for scale is locally -sparse, then .

###### Proof.

The optimum -Center solution covers the whole graph with balls of radius each. By Section 1 there are at most hubs of in each ball. ∎

We are able to exploit this intuition for our algorithm in Section 3. On a high level, our algorithm follows the lines of the following simple procedure to solve Dominating Set on graphs with bounded vertex cover number. As a subroutine we will solve an instance of the Set Cover problem, for which a collection of subsets of a universe  is given together with a subset of the universe.111Usually but for convenience we define the problem slightly more general here. A set cover for is a collection of the sets in covering , i.e., . The aim is to compute a minimum-sized set cover for the set system . Given an input graph and a vertex cover of small size (which can, for instance, be an approximation), we perform the following three steps, in each of which we find a respective subset , , of the optimum dominating set of .

1. Guess the subset of vertices in the vertex cover that belong to the dominating set .

2. Since the vertices not in the vertex cover form an independent set, any vertex of , which is not adjacent to a vertex in must be in . Thus we can let consist of all such vertices from .

3. By our choice of , if there are any vertices left in that are not adjacent to , they must be in . Furthermore these vertices must be adjacent to some vertices in contained in , by our choice of . We can thus solve an instance of Set Cover, where is given by the subset of vertices in that are not adjacent to , and the set system  is given by the neighbourhoods of vertices in restricted to . The remaining set consists of the vertices in whose neighbourhoods form the smallest solution of this Set Cover instance.

For the first step of the above algorithm there are possible guesses for . For each such guess, the second step can be performed in polynomial time. For the third step we need to solve Set Cover for an instance with a small universe . This can be done in time using the algorithm of Fomin et al. [17]. Since in our case and , this amounts to a running time of . This Set Cover algorithm is based on dynamic programming. During its execution the smallest set cover for every subset of the universe is computed, and these optimum solutions are stored in a table. Therefore, instead of running an algorithm for Set Cover for each guess of  in the third step above, we may run the algorithm of Fomin et al. [17] only once beforehand: we set the universe to all of , and the set system will contain all neighbourhood sets of vertices in . This way the needed optimum solution for the corresponding subset of  can be retrieved in constant time in the third step of our procedure. As we need to retrieve an optimum set cover for every guess of , this improves the overall running time, which is now .

In our -Center algorithm we will use the same method of pre-computing a table containing all optimum Set Cover solutions for subsets of a universe. We summarize the properties of the needed Set Cover algorithm in the following.

###### Theorem 2 ([17, 11]).

Given a set system we can compute a table , which for any subset contains the smallest set cover for in the entry . For any subset , the optimum set cover for can be retrieved in constant time from , and can be computed in time.

## 3 The fixed-parameter approximation algorithm

We begin with a brief high-level description of the algorithm. As observed in Section 2, we can think of solving -Center in a low highway dimension graph as a generalization of solving Dominating Set in a graph with bounded vertex cover number. Our algorithm (see Algorithm 1) is driven by this intuition. After guessing the optimum -Center cost  and computing together with its cluster set , we will see how the algorithm computes three approximate center sets , , and  (analogous to the three respective sets , , for Dominating Set). For the first set  the algorithm guesses a subset of the hubs of that are close to the optimum center set. This can be done in time exponential in and the local sparsity of the hub set, because there are at most that many hubs for scale  by Section 2. We will observe that by Section 2 an optimum center lying in a cluster cannot cover any vertices that are part of another cluster. This makes it easy to determine a second set of approximate centers, each of which will lie in a cluster that must contain an optimum center. The third set of centers  will consist of cluster vertices that cover the remaining vertices not yet covered by and . These remaining uncovered vertices will all be non-cluster vertices, and we find by solving a Set Cover instance, similar to the third step in our procedure for Dominating Set.

More concretely, consider an input graph with an optimum -Center solution of cost . In Algorithm 1 to Algorithm 1 of Algorithm 1 we try scales  in increasing order, to guess the correct value for which . For each guessed value of the algorithm computes a shortest path cover together with its cluster set in Algorithm 1. By [2], locally -sparse shortest path covers are computable in polynomial time if the input graph has highway dimension . In Algorithm 1 we therefore set to the bound of the local sparsity guaranteed in [2] (if locally -sparse shortest path covers are given by an oracle, we may at this point set ). In order to keep the running time low, the algorithm checks that the number of hubs is not too large in Algorithm 1: since by Section 2 we have , we can dismiss any shortest path cover containing more hubs.

Assume that was found. In the following, for an index we denote by and the regions covered by some set of optimum centers (with balls of radius ) and approximate centers (with balls of radius ), respectively. In Algorithm 1 the algorithm guesses a minimum-sized set of hubs in , such that the balls of radius around hubs in cover all optimum non-cluster centers. That is, if denotes the set of optimum non-cluster centers, each of which is at distance at most from some hub in , then and is a minimum-sized such set. We choose this set of hubs as the first set of centers for our approximate solution in Algorithm 1. Note that due to the minimality of we have . Also since for any center in there is a center (i.e., a hub) at distance at most in .

The next step is to compute a set of centers so that all clusters of the cluster set of are covered. Some of the clusters are already covered by the first set of centers , and thus in this step we want to take care of all remaining uncovered clusters, i.e., those contained in . By the definition of , any remaining optimum center in must lie in a cluster. Furthermore, the distance between clusters of is more than  by Section 2, so that a center of in a cluster cannot cover any vertices of another cluster . Hence if we guessed correctly, we can be sure that each cluster must contain a center of . For each (remaining) cluster we thus pick an arbitrary vertex in Algorithm 1 and declare it a center of the second set for our approximate solution. Hence if the optimum set of centers for is , we have (if some cluster of contains more than one optimum center in order to cover different parts of the non-cluster vertices, may be larger than ). Moreover, since the diameter of each cluster is at most  by Section 2, we get .

At this time we know that all clusters in are covered by the region . Hence if any uncovered vertices remain in for our current approximate solution, they must be non-cluster vertices. Just as , by our definition of , every remaining optimum center in lies in some cluster. Since and , any remaining uncovered vertex of must be in the region covered by centers in . Next we show how to compute a set such that the region includes all remaining vertices of the graph and . Note that the latter means that the number of centers in is at most , since , , and are disjoint.

To control the size of we will compute the smallest number of centers that cover parts of  with balls of radius . In particular, in Algorithm 1 we guess the set of hubs that lie in the region  (note that we exclude hubs of from this set). We then compute a center set of minimum size such that . For this we reduce the problem of computing centers covering to the Set Cover problem with fixed universe size, as shown in Algorithm 1 to Algorithm 1. This reduction is performed before entering the loops guessing and to optimize the running time. The universe of the Set Cover instance consists of all hubs in the shortest path cover , while the set system of the instance is obtained by restricting the balls of radius around cluster vertices to the hubs. By Theorem 2 there is an algorithm that computes the optimum Set Cover solution for every subset of the universe. This algorithm is called in Algorithm 1 of Algorithm 1 to fill a lookup table  with these optima. We can thus retrieve the optimum Set Cover solution for the subset in Algorithm 1, and let contain each cluster vertex for which the set of hubs contained in the ball is part of the optimum solution covering , which is stored in the entry of the table. As the next lemma shows, we obtain the required properties for .

###### Lemma \thelem.

Assume the algorithm guessed the correct scale and the correct sets and . The set is of size at most  and .

###### Proof.

The second property clearly follows since the sets in form a set cover for , such that every hub in is at distance at most from some . To see that , it suffices to show that the vertices in correspond to a feasible Set Cover solution for . If  was guessed correctly, this set contains only hubs in the region . As is covered by balls of radius around the centers in , the union contains . Moreover, these sets are contained in the set system , since all centers of are contained in clusters by definition of . Thus the sets form a set cover for in the instance . ∎

It remains to show that the three computed center sets , , and cover all vertices of , which we do in the following lemma. In particular, the union will pass the feasibility test in Algorithm 1 of the algorithm.

###### Lemma \thelem.

Assume the algorithm guessed the correct scale and the correct sets and . The approximate center sets , , and cover all vertices of , i.e., .

###### Proof.

The proof is by contradiction: assume there is a that is not covered by the computed approximate center sets. The idea is to identify a hub on the shortest path between and an optimum center covering . We will show that this hub must however be in and therefore is in fact in , since also turns out to be close to .

To show the existence of , we begin by arguing that the closest hub to is neither in nor in . We know that each cluster of is in , so that must be a non-cluster vertex. Thus by Section 2, . The region in particular contains all vertices that are at distance at most from any hub in . Since and , this means that . From we can also conclude that as follows. By Section 3, covers all hubs of with balls of radius . Hence if then would be at distance at most from a center of , i.e., .

From we can conclude the existence of as follows. Consider an optimum center that covers , i.e., . Recall that and . Since , this means that is neither in nor in  so that . By definition of , any hub at distance at most from a center in is in , unless it is in . Hence, as , the distance between and must be more than . Since , we get . We also know that , because covers . Hence the shortest path cover must contain a hub  that lies on the shortest path between and . In particular, and . Analogous to the argument used for above, in particular contains all vertices at distance at most from , so that since . However, then the distance bound for and yields , as .

Since contains all non-cluster centers but , by Section 2 we get , which implies . But then is contained in the ball , which we know is part of the third region since . This contradicts the assumption that was not covered by the approximate center set. ∎

Note that the proof of Section 3 does not imply that , as was the case for and . It suffices though to establish the correctness of the algorithm. Finally, we conclude the proof of Theorem 1 by analysing the runtime of the algorithm.

###### Proof of Theorem 1.

By Section 2 and Section 3, if Algorithm 1 correctly guesses the cost and the two hub sets and , then and . By Section 2, so that the correct value for will not be skipped in Algorithm 1. Hence by trying all possible values for in increasing order, Algorithm 1 will terminate with a feasible solution that covers all vertices with balls of radius , due to Algorithm 1. To prove Theorem 1 it remains to bound the running time.

There are at most possible values for that need to be tried by the outermost loop, one for every pair of vertices. Hence the only steps of Algorithm 1 that incur exponential running times are when guessing and  and when filling the table of the dynamic program for the Set Cover problem. These steps are only performed for shortest path covers of size at most due to Algorithm 1. Since we explicitly exclude the hubs in when choosing , each hub of a shortest path cover can either be in , in , or in none of them when trying all possibilities. Hence this gives possible outcomes. Filling the table takes time according to Theorem 2, while retrieving an optimum solution for in Algorithm 1 can be done in constant time. Thus the total running time to compute a -approximation is . If the input graph has highway dimension , Abraham et al. [2] show how to compute -approximations of shortest path covers in polynomial time if shortest paths have unique lengths. The latter can be assumed by slightly perturbing the edge lengths in such a way that any -approximation in the perturbed instance also is a -approximation in the original instance. Therefore we can set during the execution of our algorithm. If there is an oracle that gives locally -sparse shortest path covers for each scale, then we can set instead. Thus the claimed running times follow. ∎

## 4 Hardness results

We begin by observing that the original reduction of Hsu and Nemhauser [20] for -Center also implies that there are no -FPA algorithms.

###### Theorem 3.

It is W[2]-hard for parameter to compute a -approximation to the -Center problem for any .

###### Proof (cf. [20, 29]).

The reduction is from the Dominating Set problem, which is W[2]-hard [13] for the standard parameter, i.e., the size of the smallest dominating set of the input graph . The reduction simply introduces unit lengths for each edge of , guesses the size of , and sets . Any feasible center set of cost corresponds to a dominating set, and vice versa. On the other hand, a center set has cost at least if and only if it is not a dominating set. Hence if the size of is guessed in increasing order starting from ,  must be equal to the first time a -approximation of cost is obtained by an algorithm for -Center. By guessing the size of in increasing order, this would result in an time algorithm to compute the optimum dominating set if there was a -FPA algorithm for parameter for -Center. ∎

We now turn to proving that -approximations are hard to compute on graphs with low highway dimension. For this we introduce a general reduction from low doubling metrics to low highway dimension graphs in the next lemma. A metric has doubling dimension if for every , each set of diameter is the union of at most sets of diameter . The aspect ratio of a metric is the maximum distance between any two vertices of divided by the minimum distance, i.e., .

###### Lemma \thelem.

Given any metric with constant doubling dimension and aspect ratio , for any  there is a graph of highway dimension on the same vertex set such that for all , Furthermore, can be computed in polynomial time from the metric.

###### Proof.

First off, by scaling we may assume w.l.o.g. that the minimum distance of the given metric is . In particular this means that the maximum distance is . A fundamental property [18] of low doubling dimension metrics is that for any set of points with aspect ratio , the number of points can be at most . The proof of this property is a simple recursive application of the doubling dimension definition. For each scale where we will identify a sparse set , which in any ball of radius  has aspect ratio . The idea is to use the vertices of as hubs in a shortest path cover for scale , which then are locally sparse in any such ball. We will make sure that there is an index with a hub set for any possible distance between vertex pairs in the resulting graph . We need to make sure though that the shortest path for any pair of vertices passes through a corresponding hub of some . We achieve this by adding edges between the hubs in , which act as shortcuts. That is, the edges of will be slightly longer than the distances in the metric given by , and we will make the distances shorter with increasing scales in order to guarantee that the shortest paths pass through corresponding hubs.

More concretely, consider any set of vertices. A subset is a -cover of if for every there is a such that , and is a -packing of if for all distinct . A -net of is a set that is a -cover and a -packing of . It is easy to see that such a net can be computed greedily in time. We will use sets that form a hierarchy of nets as hubs. In particular, and is a -net of for each , where is the index of the largest scale. Note that due to the triangle inequality of the metric, each is a -cover of .

In , for each we connect two vertices by an edge of length . If a vertex pair is contained in several sets of different scales, we only add the shortest edge according to the above rule, i.e., the edge for the largest index . Hence the distance in between any is at most . In particular, for any since . Note also that and hence .

To bound the highway dimension of , consider any pair , and let be such that . Recall that the minimum distance according to is (as ), while the maximum distance is . Accordingly, in all distances lie in so the index exists. We show that the shortest path between and passes through a hub of . We do this by upper bounding in terms of using a path that contains vertices of . Then we lower bound the length of any path that does not pass through and show that it is longer than the shortest path.

Let be the closest hub to and let be the closest hub to . We begin by determining some distance bounds for these vertices. Since is a -cover of in the metric according to , the distances in from to and from to are at most each. It also means that , since we can get from to through and in the metric. We know that and thus we have . Using these bounds we get

We now show that every path that does not use any hub of is longer than . Since the hub sets of different scales form a hierarchy, any hub of scale with is also a hub for scale . Hence if does not pass through any hub of , it also cannot contain any vertex of where . Thus, if where and , any edge on will be of length at least . The sum


text:
# Double delta-function potential

Consider the double delta-function potential

$V(x)=-\alpha\left[\delta(x+a)+\delta(x-a)\right]$

where $\alpha$ and $a$ are positive constants.

a) Plot the potential.

b) Compute the eigenenergies for the ground state and the first 3 excited states.

c) Let the depth of the potential develop in time, plot and observe the evolution of the eigenenergies.

format: plain


text:
4.9k views

Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The send and receive window sizes are 5 packets each. Data packets (sent only from A to B) are all 1000 bytes long and the transmission time for such a packet is 50 μs. Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200 $\mu$s. What is the maximum achievable throughput in this communication?

1. $7.69 \times 10^6$ Bps

2. $11.11 \times 10^6$ Bps

3. $12.33 \times 10^6$ Bps

4. $15.00 \times 10^6$ Bps

edited | 4.9k views
+12

Isn't answer should be 88.88 X 10bps?

–1

Ur Rght

option c is correct

since the solution is

Throughput=total size/total time

=1500*4/(60+2*170)*10^-6

=6000/400*10^-6

=15*10^6 Bytes/sec

0
in the options they have used bps(small b which bits/sec) so what should we consider it in exam bytes or bits /sec
0
What happen when half duplex is given.
0
In case of half duplex the acknowledgements would need to be sent on a different channel. That will not affect throughput in this case since ack is considered to be negligible.
0
@anirudh @saurabh rai

I think all 5 packet reach to receiver within 250 microseconds so in another 200 microseconds ack trevel alone so there is no effect in throughput even in half duplex.
0
if they ask us to consider ack also and the link is half duplex

+3

Wiki says  " For the highest possible throughput, it is important that the transmitter is not forced to stop sending by the sliding window protocol earlier than one round-trip delay time(RTT). "   https://en.wikipedia.org/wiki/Sliding_window_protocol

So that means  though the connection is full duplex, next window will be sent only after acknowledgement will be received by sender because it is following  Sliding Window protocol which has independent acknowledgements.

so you have to use RTT here and RTT = 2 * prop time + Transmission Time = 2 * 200 + 50 = 450

If it is half duplex  answer will be half of this answer  .

For throughput .

2*bandwidth*Tp = for full duplex link

bandwith*tp = for half duplex

+3
Throughput in half Duplex = ( Throughput in Full duplex / 2 )

So channel type (means half duplex or full duplex) will just affect capacity or Throughput.. It does Not effect transmission time nor bandwidth.
0
@Bikram sir according to you

If I calculate the throughout it is 4MB/sec

Please correct me if I am wrong
0
what is the correct answer of this question/
0

The correct answer is 88.88 X 10bps(bit per sec) or 11.11X106 Bps(Bytes per sec).

The correct Option is,(B) 11.11X106 Bps

0

Answer should be 7.69 * 106

We need the maximum throughput, and for that we need to send as much data
as possible to fully utilize the bandwidth.

so, maximum packets that can be sent $=1 + 2a = 9$ (after calculation) for $100\%$ efficiency.

But we have a window size of 5 only, so we can send only $5$ packets at max.

Efficiency $=\dfrac{5}{9}$

Now, $\dfrac{A}{Q},$ Bandwidth of the channel $(BW) =\dfrac{L}{T_t}$
$=\dfrac{1000}{(50\times 10^{-6})}$

$= 20\times 10^{6} \text{bytes/sec}.$

So, max. throughput achievable $=\text{Efficiency$\times $BW}$

$=\dfrac{5}{9}\times 20\times 10^{6}= 11.11\times 10^{6} \text{bytes/sec}.$
edited
+5
This seems to me a more sensible answer than the currently accepted one.
0
can u plzz tell me ahat will b throughput for half duplex ??
0
Is the sliding window protocol is even possible for half duplex?
0
well explained concept.....thnks
0
best way of explaination....great job :)
+1

Throughput

bandwith*tp=for half duplex

+4
@Bikram sir

if capacity of link is asked in question then it will be

bandwith*tp=for half duplex
+1

Yes, you are correct

Capacity = 2*bandwidth*Tp  for Full duplex link  and bandwith *tp=for half duplex link.... this is correct .

Here we need to found Throughput ..  we consider capacity = throughput

Maximum throughput is generally same as digital bandwidth capacity.

the term capacity is used many places in different way..throughput is one of them https://en.wikipedia.org/wiki/Computer_data_storage#Capacity

0

can u plzz tell me ahat will b throughput for half duplex ?

The value of Throughput in Half duplex is Half of the value we found in Full duplex.

Throughput in half Duplex = ( Throughput in Full duplex / 2 )

0
perfect
0
What will be the change in the calculation part, if it is given the half duplex link?
0

Anwer should be 7.69 $\times$ 106 bps

Total time = 50 + 200(till this time all packet will come one link i.e. 50 $\times$ 4) + 200 for Ack till 4th paket + 200 for 5th packet = 650 micro sec

since TT given for one packet.

Throughput = $\frac{5 \times 1000}{650 \times 10^{6}} = 7.69 \times 10^{6} Bps$

I think options are given in bytes per sec instead of bits per sec.

Transmission time $=50 \text{ micro sec}$
Propagation time $=200\text{ micro sec}$

RTT$= 50+2\times 200=450 \text{ microsec}$

(Receiver can send an $\text{ACK}$ as soon as the first packet is received)

Total number of bits transmitted before first $\text{ACK}$ is received,
$=1000\times 5\times 8\text{ bits}=40000\text{ bits}$

After first $\text{ACK}$ is received, the same cycle of action repeats.

So, Throughput$=\left(\dfrac{40000}{450}\right)\times10^{6} \text{ bits}$

$= 88.88\times 10^{6} \text{bits per sec}$

$=11.11\times 10^{6}\text{ bytes per sec}$
edited
0

----

The send and receive window sizes are 5 packets each

though the connection is full duplex, next window will be sent only after acknowledgement will be received by sender because it is following  Sliding Window protocol which has independent acknowledgements.

So the main point is : Sender is waiting for cumulative ack.

0

@Bikram Sir, I have a doubt in the line which I have written

That;s why it require TT of data, and in this TT it sends all 5 packets,

if it is sending 5 packets then TT should be 5*TT of each packet as given in the question

the transmission time for such a packet is 50 μs

if it is so then we should get (5* 50 + 2*200 ) micro seconds but why isn't so???

+1

This is very simple concept. What i have learnt from taenenbaum is that

Maximum sender window is the number of frames that will be sent in TT+2PT or TT+RTT

So 5 frames can be sent in 50+2*400 =450.

You can read this from tanenbaum for clarification

0
Ok so whatever be the window size means what ever no of packet we sent it will always TT+2PT
0
Yes. Maximum sender window size =Number of frames in 2*bandwidth +1 = Number of frames in TT+RTT because in one RTT is same as 2*BD and one TT is time for one frame so all are same
0
@rahul

the definition of RTT is not 2*PT , Its only in tanenbaum, but other books quote it differently.

0
which other books?
+1
@rahul

RTT have no worldwide standard definition..in Kurose you can check it may be different there..

in above discussions we discuss what actually RTT is and in which cases what value of RTT should we use !
0

can't we follow the approach, throughput=bytes sent(5*50) / total bytes that can be sent(5*50+RTT*Bandwidth )   in the way it has been followed in the solution to

# GATE2008-IT-64

by Danish

I am confused where we are supposed to add the Transmission time for all sent packets or single packet to compute the efficiency , Please help me in that

0
@Bikram Sir,

One doubt. If the transmission would have happened both A->B and B->A at the same time in this full duplex,then answer would be 22.22×10^6bytes/sec.
5000 bytes are being sent in 200 + 50×5 us.so troughput =5000/450  ×10^6 =》11.11×10^6 option b.
+1 vote
In this question we need not to add acknowledgement time of last packet because here for throughput they are assuming that this tramsmission is continuous for indefinite time(It is a real system based question)

so Tt=250 micro sec

Tp=200 microsecond

N= 5000 bytes

so throughput= 5000/450 microsec = b option


text:
Between 1977 and 1989, the percentage of income paid to : GMAT Critical Reasoning (CR)
Check GMAT Club Decision Tracker for the Latest School Decision Releases https://gmatclub.com/AppTrack

 It is currently 22 Feb 2017, 17:31

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# Between 1977 and 1989, the percentage of income paid to

Author Message
TAGS:

### Hide Tags

Intern
Joined: 04 Jul 2003
Posts: 7
Location: Chennai
Followers: 0

Kudos [?]: 11 [3] , given: 0

Between 1977 and 1989, the percentage of income paid to [#permalink]

### Show Tags

21 Aug 2003, 00:31
3
KUDOS
10
This post was
BOOKMARKED
00:00

Difficulty:

75% (hard)

Question Stats:

50% (02:36) correct 50% (01:57) wrong based on 546 sessions

### HideShow timer Statistics

Between 1977 and 1989, the percentage of income paid to federal taxes by the richest one percent of Americans decreased from 40 percent to 25 percent. By the end of that same period, however, the richest one percent of Americans were paying a larger proportion of all federal tax revenues from 12.7 percent in 1977 to 16.2 percent in 1989.

Which of the following, if true, contributes most to an explanation of the discrepancy described above ?

(A) Between 1977 and 1989, the IRS increased the percentage of its staff members responsible for audits and tax collection.

(B) Between 1977 and 1989, the before-tax income of the richest one percent of Americans increased by over 75 percent when adjusted for inflation.

(C) Between 1977 and 1989, many of the richest one percent of Americans shifted their investments from taxable to untaxable.

(D) Between 1977 and 1989, the tax rate paid by middle-income Americans was reduced, but several tax loopholes were eliminated.

(E) Between 1977 and 1989, the amount of federal taxes paid by the richest one percent of American increased by $45 billion, while the amount paid by all Americans rose by$50 billion.
[Reveal] Spoiler: OA
If you have any questions
New!
GMAT Instructor
Joined: 07 Jul 2003
Posts: 770
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 25

Kudos [?]: 207 [0], given: 0

Re: Kaplan CR Question Doubt [#permalink]

### Show Tags

21 Aug 2003, 01:11
tina wrote:
Between 1977 and 1989, the percentage of income paid to federal taxes by the richest one percent of Americans decreased from 40 percent to 25 percent. By the end of that same period, however, the richest one percent of Americans were paying a larger proportion of all federal tax revenues from 12.7 percent in 1977 to 16.2 percent in 1989.

Which of the following, if true, contributes most to an explanation of the discrepancy described above ?

(A) Between 1977 and 1989, the IRS increased the percentage of its staff members responsible for audits and tax collection.

(B) Between 1977 and 1989, the before-tax income of the richest one percent of Americans increased by over 75 percent when adjusted for inflation.

(C) Between 1977 and 1989, many of the richest one percent of Americans shifted their investments from taxable to untaxable.

(D) Between 1977 and 1989, the tax rate paid by middle-income Americans was reduced, but several tax loopholes were eliminated.

(E) Between 1977 and 1989, the amount of federal taxes paid by the richest one percent of American increased by $45 billion, while the amount paid by all Americans rose by$50 billion.

I would like to know why it is not C ?

Thank You.

You are trying to explain how the proportion of taxes paid by the top 1% earners actually went up despite a rate decrease.

B correctly explains that the top 1% earners could have been earning a lot more, hence every though their tax rate was lower, their overall tax was higher.

C, OTOH, describes why the top 1% should be paying EVEN LESS (by moving money into taxfree earnings, their tax burden is reduce even further) hence it does nothing to explain why the proportion of taxes paid increased.
_________________

Best,

AkamaiBrah
Former Senior Instructor, Manhattan GMAT and VeritasPrep
Vice President, Midtown NYC Investment Bank, Structured Finance IT
MFE, Haas School of Business, UC Berkeley, Class of 2005
MBA, Anderson School of Management, UCLA, Class of 1993

Manager
Joined: 28 Feb 2003
Posts: 147
Location: Kiev
Followers: 1

Kudos [?]: 9 [0], given: 0

### Show Tags

21 Aug 2003, 01:50
AkamaiBrah

Could you explain what "OTOH" means, pls
_________________

Too much is not enough...

Senior Manager
Joined: 22 May 2003
Posts: 333
Location: Uruguay
Followers: 1

Kudos [?]: 147 [3] , given: 0

### Show Tags

21 Aug 2003, 05:47
3
KUDOS
My guess is: On The Other Hand
Manager
Joined: 28 Feb 2003
Posts: 147
Location: Kiev
Followers: 1

Kudos [?]: 9 [0], given: 0

### Show Tags

21 Aug 2003, 06:23
Thanks!
_________________

Too much is not enough...

GMAT Instructor
Joined: 07 Jul 2003
Posts: 770
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 25

Kudos [?]: 207 [0], given: 0

### Show Tags

21 Aug 2003, 20:01
bono wrote:
Thanks!
\

I use these a lot:

OTOH: on the other hand
IMO: in my opinion
IMHO: in my humble opinion
GIGO: garbage in, garbage out
_________________

Best,

AkamaiBrah
Former Senior Instructor, Manhattan GMAT and VeritasPrep
Vice President, Midtown NYC Investment Bank, Structured Finance IT
MFE, Haas School of Business, UC Berkeley, Class of 2005
MBA, Anderson School of Management, UCLA, Class of 1993

Manager
Joined: 19 Oct 2003
Posts: 72
Location: USA
Followers: 1

Kudos [?]: 0 [0], given: 0

Re: Kaplan CR Question Doubt [#permalink]

### Show Tags

27 Oct 2003, 20:52
B is not correct. What if the income of the rest 99% increase 10000000%.
I like E.
For reasoning:
The formular is Rate77*Income77; Rate89*income89.
proportion: Rate77*Income77/total tax77 = P77
rate89*income89/total tax89 = p89

Arguement: Rate77>rate89 BUT p77<p89 --> WHY?
1. Income89 much larger than income77 AND there is not much change in total tax or the rest 99% DOESN'Tcontribute much more!
2. Income89*rate89 < income77*rate77 AND total tax (or the tax of the rest 99%) reduces even much much more.
So the answer here much has something to do with BOTH sides (the richest and the rest 99%)
That is why B cannot be correct
The only one sound correct is E. richest increase tax 45 m while the rest increase only 5 (50-45)

tina wrote:
Between 1977 and 1989, the percentage of income paid to federal taxes by the richest one percent of Americans decreased from 40 percent to 25 percent. By the end of that same period, however, the richest one percent of Americans were paying a larger proportion of all federal tax revenues from 12.7 percent in 1977 to 16.2 percent in 1989.

Which of the following, if true, contributes most to an explanation of the discrepancy described above ?

(A) Between 1977 and 1989, the IRS increased the percentage of its staff members responsible for audits and tax collection.

(B) Between 1977 and 1989, the before-tax income of the richest one percent of Americans increased by over 75 percent when adjusted for inflation.

(C) Between 1977 and 1989, many of the richest one percent of Americans shifted their investments from taxable to untaxable.

(D) Between 1977 and 1989, the tax rate paid by middle-income Americans was reduced, but several tax loopholes were eliminated.

(E) Between 1977 and 1989, the amount of federal taxes paid by the richest one percent of American increased by $45 billion, while the amount paid by all Americans rose by$50 billion.

I would like to know why it is not C ?

Thank You.

_________________

I have 2 month for gmat.

GMAT Instructor
Joined: 07 Jul 2003
Posts: 770
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 25

Kudos [?]: 207 [0], given: 0

### Show Tags

28 Oct 2003, 02:50
You are correct that you can solve for numbers in E that will be consistent. However, this does not do much to explain the discrepancy of why a smaller tax rate for the rich contributes more to the overall tax burden.

Choice B states that the "rich people" pie is much bigger. Hence, it shows that by taking a smaller piece out of a much larger pie, the overall tax burden borne by the rich can still increase as a percentage of all tax payers. Hence, B does a better job of explaining the discrepancy and is IMO the better answer.
_________________

Best,

AkamaiBrah
Former Senior Instructor, Manhattan GMAT and VeritasPrep
Vice President, Midtown NYC Investment Bank, Structured Finance IT
MFE, Haas School of Business, UC Berkeley, Class of 2005
MBA, Anderson School of Management, UCLA, Class of 1993

Director
Joined: 29 Oct 2004
Posts: 863
Followers: 4

Kudos [?]: 205 [0], given: 0

CR - the richest one percent of Americans [#permalink]

### Show Tags

09 Feb 2005, 22:33
Between 1977 and 1989, the percentage of income paid to federal taxes by the richest one percent of Americans decreased from 40 percent to 25 percent. By the end of that same period, however, the richest one percent of Americans were paying a larger proportion of all federal tax revenues from 12.7 percent in 1977 to 16.2 percent in 1989.

Which of the following, if true, contributes most to an explanation of the discrepancy described above ?

(A) Between 1977 and 1989, the IRS increased the percentage of its staff members responsible for audits and tax collection.

(B) Between 1977 and 1989, the before-tax income of the richest one percent of Americans increased by over 75 percent when adjusted for inflation.

(C) Between 1977 and 1989, many of the richest one percent of Americans shifted their investments from untaxable to taxable assets.

(D) Between 1977 and 1989, the tax rate paid by middle-income Americans was reduced, but several tax loopholes were eliminated.

(E) Between 1977 and 1989, the amount of federal taxes paid by the richest one percent of American increased by $45 billion, while the amount paid by all Americans rose by$50 billion.
SVP
Joined: 03 Jan 2005
Posts: 2243
Followers: 16

Kudos [?]: 328 [0], given: 0

### Show Tags

09 Feb 2005, 22:43
Definitely B. The rich has become richer.
VP
Joined: 25 Nov 2004
Posts: 1493
Followers: 7

Kudos [?]: 98 [0], given: 0

### Show Tags

09 Feb 2005, 22:45
lower income => higher tax
Higher income => lower tax.

Director
Joined: 04 Jul 2004
Posts: 904
Followers: 4

Kudos [?]: 52 [0], given: 0

### Show Tags

10 Feb 2005, 17:40
Betweeb (B) and (C).. I will go for (B).

All other choices are out of scope.
Director
Joined: 29 Oct 2004
Posts: 863
Followers: 4

Kudos [?]: 205 [0], given: 0

### Show Tags

10 Feb 2005, 18:49
Please explain why (C) is wrong.
OA is (B)
Director
Joined: 04 Jul 2004
Posts: 904
Followers: 4

Kudos [?]: 52 [0], given: 0

### Show Tags

10 Feb 2005, 19:32
I think (C) brings in an assumption that rich ppl had untaxable asset.
SVP
Joined: 03 Jan 2005
Posts: 2243
Followers: 16

Kudos [?]: 328 [0], given: 0

### Show Tags

10 Feb 2005, 20:28
The stem says rich people are paying less fractions of their income, but the absolute value represents a larger proportion of total tax. For example, this rich guy used to pay 40% of 10 million, which is 4 million, and now he is paying only 30% of his income, but the value is 6 million. The only explanation is that his income is now 20 million. If C is true, he would be paying a higher fraction of his income as tax.
Director
Joined: 29 Oct 2004
Posts: 863
Followers: 4

Kudos [?]: 205 [0], given: 0

### Show Tags

10 Feb 2005, 22:34
This does not convince much.

Quote:
If C is true, he would be paying a higher fraction of his income as tax.

(C) Between 1977 and 1989, many of the richest one percent of Americans shifted their investments from untaxable to taxable assets.

Let look at some number here.

1977: 40% of $100 1989: 25% of ($100 + $10000000) (the taxable assets now, before it was not) SVP Joined: 03 Jan 2005 Posts: 2243 Followers: 16 Kudos [?]: 328 [0], given: 0 ### Show Tags 10 Feb 2005, 23:01 Your post cannot be true unless the taxable assets are considered income since we are talking about fraction of income. If assets are considered income then B is true, although I don't think assets are the same as income. Director Joined: 29 Oct 2004 Posts: 863 Followers: 4 Kudos [?]: 205 [0], given: 0 ### Show Tags 10 Feb 2005, 23:11 income vs assets Alright! Got it now. Thanks. Manager Joined: 01 Jan 2005 Posts: 167 Location: NJ Followers: 1 Kudos [?]: 4 [0], given: 0 ### Show Tags 11 Feb 2005, 05:51 I know I am late. Yet another B. I think this is a PR question...isn't it? Director Joined: 01 Feb 2003 Posts: 851 Location: Hyderabad Followers: 4 Kudos [?]: 102 [0], given: 0 CR - Tax - Kaplan online test [#permalink] ### Show Tags 27 Feb 2005, 01:34 Between 1977 and 1989, the percentage of income paid to federal taxes by the richest one percent of Americans decreased , from 40% to 25%. By the end of that same period, however, the richest 1% of Americans were paying a larger proportion of all federal tax revenues, from 12.7% in 1977 to 16.2% in 1989. Which of the following, if true, contributes to an explanation of the discrepancy described above? A) between 1977 and 1989, the Internal Revenue Servuce increased the percentage of its staff members responsible for audits and tax collection B)Between 1977 and 1989, the before-tax income of the richest 1% of Americans increased by over 75% when adjusted for inflation C) Between 1977 and 1989, many of the richest one percent of Americans shifted their investements from taxable to untaxable assets D)Between 1977 and 1980, the tax rate paid by middle-income Americans was reduced, but several tax loopholes were eliminated E) Between 1977 and 1989, the amount of federal taxes paid by the richest 1% of Americans increased by$45 billion, while the amount paid by all Americans rose by \$50 billion
CR - Tax - Kaplan online test   [#permalink] 27 Feb 2005, 01:34

Go to page    1   2   3    Next  [ 57 posts ]

Similar topics Replies Last post
Similar
Topics:
8 The percentage of households with an annual income of more 9 27 Mar 2014, 08:57
30 Between 1977 and 1989, the percentage of income paid to 17 29 Jan 2012, 01:54
5 Between 1977 and 1989, the percentage of income paid to 8 26 Sep 2011, 19:09
The percentage of households with an annual income of more 4 17 Feb 2009, 17:12
The percentage of households with an annual income of more 0 07 Jan 2009, 13:39
Display posts from previous: Sort by


text:
1. ## probability

John’s wallet contains two $20-bills, one$10-dollar bill, and three $5-dollar bills. On this particular summer day, John’s friend Eddy is visiting and Eddy’s wallet contains one$20, three $10s, and one$5. Both wallets look the same and are sitting together on the table. When little Jenny hears the ice cream truck coming she asks her dad John if she can have
some money for an ice cream. He tells her she can go grab a bill out of his wallet. She runs to the table, randomly grabs a bill out of one of the wallets, buys an ice cream for $2 and then returns the change to one of the wallets (not remembering which one she took the money from). A tree diagram would be useful here! (a) What is the probability that Eddy goes home with more money than he came with? (b) What is the probability Eddy still has his$20-bill when he leaves?
(c) If the change Jenny returns with is more than $5, what is the probability she took the money from the correct wallet? 2. Hello, zackgilbey! I started a tree diagram, then found that we can answer . . the first two questions with a little "common sense." John’s wallet contains two$20-bills, one $10-dollar bill, and three$5-dollar bills.
John’s friend Eddys wallet contains one $20, three$10s, and one $5. Both wallets look the same and are sitting together on the table. When little Jenny hears the ice cream truck coming she asks her dad John if she can have some money for an ice cream. He tells her she can go grab a bill out of his wallet. She runs to the table, randomly grabs a bill out of one of the wallets, buys an ice cream for$2, and then returns the change to one of the wallets.

(a) What is the probability that Eddy goes home with more money than he came with?

If Eddy has a profit, Jenny must have taken a bill from John's wallet.
. . This happens with probabiity $\tfrac{1}{2}.$

She returns with the change and puts it in Eddy's wallet.
. . This happens with probability $\tfrac{1}{2}.$

So Eddy makes a profit with probability: . $\frac{1}{2}\cdot\frac{1}{2} \:=\:\frac{1}{4}$

(b) What is the probability Eddy still has his $20-bill when he leaves? Eddy will still have his$20-bill if one of two cases occur:

. . [1] Jenny takes money from John's wallet: probabiity $\tfrac{1}{2}$

. . [2] Jenny takes money from Eddy's wallet (probability $\tfrac{1}{2}\$)
. . . . .and takes $5 or$10 (probability $\tfrac{4}{5}$)

Therefore: . $P(\text{Eddy has his \20 bill}) \:=\:\frac{1}{2}+\frac{1}{2}\!\cdot\!\frac{4}{5} \;=\;\frac{9}{10}$

I'm still working on a simple way to explain my answer to part (c).

3. thanks... ive created a tree diagram and a and b make sense now as for part c this is what i got.

If there is more than 5 dollars change that means it must be a $10 or$20 so I eliminated the chance of $5 bills. Jenny is still faced with choosing either John or Eddy's wallet. so 1/2 now if she chooses John's wallet correctly there is a 2/5 chance that it will be something other than a$5 (10 or 20 bill) Therefore would the answer be

(1/2) . (2/5)


text:
Mid Chapter Review
Chapter
Chapter 6
Section
Mid Chapter Review
Solutions 33 Videos

 \displaystyle x^2 + 4x = 12

0.31mins
Q1a

 \displaystyle x^2 + 8x + 9 = 0

0.51mins
Q1b

 \displaystyle x^2 -9x = -4

1.10mins
Q1c

 \displaystyle -3x^2 -2x + 3 = 0

1.26mins
Q1d

 \displaystyle 2x^2 - 5x + 10 = 15

1.29mins
Q1e

\frac{1}{2}x^2 + 10x - 2 = -10

1.12mins
Q1f

Determine the root(s).

 \displaystyle x^2 + 6x - 16 = 0

0.26mins
Q2a

Determine the root(s).

 \displaystyle 2x^2 + x - 3= 0

1.12mins
Q2b

Determine the root(s).

 \displaystyle x^2 + 3x - 10 = 0

0.21mins
Q2c

Determine the root(s).

 \displaystyle 6x^2 + 7x - 5 = 0

0.56mins
Q2d

Determine the root(s).

 \displaystyle -3x^2 -9x + 12 = 0

0.39mins
Q2e

Determine the root(s).

 \displaystyle \frac{1}{2}^2 + 6x + 16 = 0

0.33mins
Q2f

Solve using any strategy.

 \displaystyle x^2 + 12x + 45 = 0

0.25mins
Q3a

Solve using any strategy.

 \displaystyle 2x^2 + 7x + 5 = 9

0.40mins
Q3b

Solve using any strategy.

 \displaystyle x(6x -1) = 12

0.56mins
Q3c

Solve using any strategy.

 \displaystyle x(x + 3) - 20 = 5(x + 3)

0.47mins
Q3d

Kate drew this sketch of a small suspension bridge over a gorge near her home.

She determined that the bridge can be modelled by the relation y = 0.1x^2 - 1.2x + 2. How wide is the gorge, if 1 unit on her graph represents 1 m?

1.43mins
Q4

If a ball were thrown on Mars, its height, h, in metres, might be modelled by the relation h = -1.9t^2 + 18t + 1, where tis the time in seconds since the ball was thrown.

a.Determine when the ball would be 20 m or higher above Mars’ surface.

b. Determine when the ball would hit the surface.

5.17mins
Q5

Determine the value of c needed to create a perfect-square trinomial.

 \displaystyle x^2 + 8x + c

0.12mins
Q6a

Determine the value of c needed to create a perfect-square trinomial.

 \displaystyle x^2 - 10x + c

0.10mins
Q6b

Determine the value of c needed to create a perfect-square trinomial.

 \displaystyle x^2 + 5x + c

0.12mins
Q6c

Determine the value of c needed to create a perfect-square trinomial.

 \displaystyle x^2 - 7x + c

0.13mins
Q6d

Determine the value of c needed to create a perfect-square trinomial.

 \displaystyle -4x^2 + 24x + c

0.30mins
Q6e

Determine the value of c needed to create a perfect-square trinomial.

 \displaystyle 2x^2 -18x + c

0.40mins
Q6f

Write each relation in vertex form by completing the square.

 \displaystyle y = x^2 + 6x -3

0.28mins
Q7a

Write each relation in vertex form by completing the square.

 \displaystyle y = x^2 -4x + 5

0.24mins
Q7b

Write each relation in vertex form by completing the square.

 \displaystyle y = 2x^2 + 16x + 30

0.42mins
Q7c

Write each relation in vertex form by completing the square.

 \displaystyle y = -3x^2 -18x - 17

0.44mins
Q7d

Write each relation in vertex form by completing the square.

 \displaystyle y = 2x^2 + 10x + 8

1.09mins
Q7e

Write each relation in vertex form by completing the square.

 \displaystyle y = -3x^2 + 9x -2

1.06mins
Q7f

Consider the relation y = -4x^2 + 40x - 91.

a. Complete the square to write the equation in vertex form.

b. Determine the vertex and the equation of the axis of symmetry.

c. Graph the relation.

2.01mins
Q8

Martha bakes and sells her own organic dog treats for \$15/kg. For every \$1 price increase, she will lose sales. Her revenue, R, in dollars, can be modelled by y = -10x^2 + 100x + 3750, where x is the number of \\$1 increases. What selling price will maximize her revenue?

For his costume party, Byron hung a spider from a spring that was attached to the ceiling at one end. Fern hit the spider so that it began to bounce up and down. The height of the spider above the ground, b, in centimetres, during one bounce can be modelled by h = 10h^2 -40t+240, where t seconds is the time since the spider was hit. When was the spider closest to the ground during this bounce?


text:
### Generalized almost convergence of double sequences in modular function spaces

#### Abstract

This article deals with almost convergence of double sequences using a new generalization of fractional-order difference operator in modular spaces and application to the Korovkin-type approximation in the context of modular spaces for positive linear operators. We then obtain several inclusion relations and present some examples, include proper non-trivial extensions of the corresponding classical ones. Further, we extend our study to new modular forms of Korovkin-type approximation theorems. Finally, we give an example using bivariate Chlodowsky-Szász-Kantorovich-Charlier-type operators and outline possible further extensions and improvements, in order to illustrate the effectiveness of the proposed methods.

#### Article information

Source
Adv. Oper. Theory, Volume 4, Number 3 (2019), 556-573.

Dates
Accepted: 18 November 2018
First available in Project Euclid: 2 March 2019

https://projecteuclid.org/euclid.aot/1551495620

Digital Object Identifier
doi:10.15352/aot.1808-1412

Mathematical Reviews number (MathSciNet)
MR3919031

Zentralblatt MATH identifier
07056785

Subjects
Primary: 40A30: Convergence and divergence of series and sequences of functions
Secondary: 46E30 40G15 39A70

#### Citation

Kadak, Ŭgur. Generalized almost convergence of double sequences in modular function spaces. Adv. Oper. Theory 4 (2019), no. 3, 556--573. doi:10.15352/aot.1808-1412. https://projecteuclid.org/euclid.aot/1551495620

#### References

• P. N. Agrawal, B. Baxhaku, and R. Chauhan, The approximation of bivariate Chlodowsky–Szasz–Kantorovich-Charlier-type operators, J. Inequal. Appl. 2017, Paper No. 195, 23 pp.
• P. Baliarsingh, On a fractional difference operator, Alexandria Eng. J. 55 (2016), no. 2, 1811–1816.
• C. Bardaro and I. Mantellini, Approximation properties in abstract modular spaces for a class of general sampling-type operators, Appl. Anal. 85 (2006), no. 4, 383–413.
• C. Bardaro and I. Mantellini, A Korovkin theorem in multivariate modular function spaces, J. Funct. Spaces Appl. 7 (2009). no. 2, 105–120.
• C. Çakan and B. Altay, Statistical boundedness and statistical core of double sequences, J. Math. Anal. Appl. 317 (2006), no. 2, 690–697.
• S. Chapman, On non-integral orders of summability of series and integrals, Proc. London Math. Soc. (2) 9 (1911), 369–409.
• J. A. Fridy and C. Orhan, Lacunary statistical convergence, Pacific J. Math. 160 (1993), 43–51.
• U. Kadak and S. A. Mohiuddine, Generalized statistically almost convergence based on the difference operator which includes the $(p, q)$-gamma function and related approximation theorems, Results Math. 73 (2018), no. 1, Art. 9, 31 pp.
• S. Konca, E. Savas, and S. Ekin, Double weighted lacunary almost statistical convergence of order $\alpha$, Rom. J. Math. Comput. Sci. 6 (2016), no. 1, 39–46.
• G. G. Lorentz, A contribution to the theory of divergent series, Acta Math. 80 (1) 1948, 167–190.
• M. Mursaleen and O. H. H. Edely, Statistical convergence of double sequences, J. Math. Anal. Appl. 288 (2003), 223–231.
• J. Musielak, Orlicz spaces and modular spaces, Lecture Notes in Mathematics, 1034. Springer-Verlag, Berlin, 1983.
• J. Musielak and W. Orlicz, On modular spaces, Studia Math. 18 (1959), 49–65.


text:
# Computing $\lim\limits_{n\to\infty} \int_{0}^{\infty}\frac{\sin(x/n)}{(1+x/n)^{n}}\, dx$

$$\lim_{n\to\infty} \int_{0}^{\infty}\frac{\sin(x/n)}{(1+x/n)^{n}}\, dx$$

I’ve been able to show that the integral is bounded above by 1 (several ways).
One of the simplest is just letting $u=x/n$ and doing some bounding above. It must converge to something (if it is monotone increasing.. don’t think so), but all my efforts to use Lebesgue Dominated Convergence have failed. I can’t seem to dominate this function…

However, if I could dominate it the integrand converges pointwise to 0 and so
then the integral would be 0, which I think is incorrect.

I have found it sufficient to deal with
$$\lim_{n\to\infty}\int_{0}^{n}\frac{\sin(x/n)}{(1+x/n)^{n}}\, dx$$

I tried to turn it into a series and use the converse of the integral test, but that hasn’t went well.

I’ve used Egoroff’s theorem to try to use uniform convergence but that failed.

Some of the inequalities and ideas I’ve tried to use in a solution include:

$sin(x/n)\leq x/n$

after a $u$ sub I’ve tried to turn it into a riemann sum… failed

$(1+x/n)^{n}\geq 1+x$ and the binomial theorem

$(1+x/n)^{n}$ converges to $e^x$ and it is increasing in $n$ so
$e^{-x}\leq \frac{1}{(1+x/n)^{n}}$

I’ve tried to use that the integrand is measurable and subtract out different measurable sets from the integral to make it more convenient..

I’ve been playing with this on and off for a month or so and no luck. I appreciate any help here.

Update:
From mixedmath’s suggestion

splitting it into $[0,10]$ and $[10,\infty]$
it is clear that the integrand is dominated on $[0,10]$ (say by 1) and so
lebesgue sends that portion to 0.

On the larger interval I am still running into a problem making it bounded nicely. If I try a $u$ sub the bounds get messy. I would like to choose an $n$ so that

$2e^{-x} \leq (1+x/n)^n$ for all $x\in [10,\infty]$ .. maybe:

there exists an $N$ such that for all $n\geq N$

$e^{10}/2 < (1+10/n)^{n}$

but for $x>10$..

$e^{10}/2<(1+10/n)^{n}<(1+x/n)^{n}$

but that’s not quite right..

#### Solutions Collecting From Web of "Computing $\lim\limits_{n\to\infty} \int_{0}^{\infty}\frac{\sin(x/n)}{(1+x/n)^{n}}\, dx$"

Let
$$f_n(x) = \frac{\sin(x/n)}{(1+x/n)^n}.$$
Notice that $\lim_{n\to\infty} f_n(x) = 0$.
But
$$|f_n(x)| \leq \frac{1}{(1+x/n)^n} \leq \frac{1}{(1+x/2)^2}$$
for $n\ge 2.$
So, for $n\ge 2$, $f_n(x)$ is dominated by $1/(1+x/2)^2$, which is integrable,
$$\int_0^\infty dx \frac{1}{(1+x/2)^2} = 2.$$
Therefore, the dominated convergence theorem applies,
$$\lim_{n\to\infty} \int_0^\infty \frac{\sin(x/n)}{(1+x/n)^n} dx = 0.$$

In the comments, @RobertIsrael gives another option for a dominating function.

Just for an alternate solution that avoids the Dominated Convergence theorem you can do this.

First show:

$$\lim_{n \to \infty} \int_0^{n\pi} \frac{\sin(x/n)}{(1 + x/n)^n} dx = \lim_{n \to \infty} \int_0^{\infty} \frac{\sin(x/n)}{(1 + x/n)^n} dx.$$

You can do this by looking at the difference between their limit, and an obvious bound. Then use the variable substitution $x/n \mapsto x$ to get:

$$\int_0^{n\pi} \frac{\sin(x/n)}{(1 + x/n)^n} dx = n \int_0^{\pi} \frac{\sin(x)}{(1 + x)^n} dx.$$

Now this integral is set up nicely for integration by parts ($\sin$ is 0 at the end points) to get:

$$n \int_0^{\pi} \frac{\sin(x)}{(1 + x)^n} dx = \frac{n}{n-1} \int_0^{\pi} \frac{\cos(x)}{(1 + x)^{n-1}} dx.$$

Now you can use Bernoulli’s inequality, which says $(1 + x)^{n-1} \geq 1 + (n-1)x$ to get:

$$\int_0^{\pi} \frac{\cos(x)}{(1 + x)^{n-1}} \leq \int_0^{\pi} \frac{1}{1 + (n-1)x} dx$$.

which is easily seen to go to 0.