This paper presents a new method and a constraint-based objective function to solve two problemsrelated to the design of optical telecommunication networks, namely the Synchronous Optical Net-work Ring Assignment Problem (SRAP) and the Intra-ring Synchronous Optical Network DesignProblem (IDP). These network topology problems can be represented as a graph partitioning withcapacity constraints as shown in previous works. We present here a new objective function and anew local search algorithm to solve these problems. Experiments conducted in C
Previously, we saw that with local search it is necessary to define a neighborhood to choose the next solution. The authors of @cite_5 use the same for all of their metaheuristics. It tries to assign an item @math from a partition, @math , to another partition, @math . The authors also consider the neighborhood obtained by swapping two items, @math and @math , from two different partitions, @math and @math . But instead of trying all the pairs of items, it will only try to swap the two items if the resulting solution of the assignment of @math to the partition @math is unfeasible.
@cite_5
1969385974
In this paper we study the problem of allocating divisible items to agents without payments. We assume no prior knowledge about the agents. The utility of an agent is additive. The social welfare of a mechanism is defined as the overall utility of all agents. This model is first defined by Guo and Conitzer [7]. Here we are interested in strategy-proof mechanisms that have a good competitive ratio, that is, those that are able to achieve social welfare close to the maximal social welfare in all cases. First, for the setting of n agents and m items, we prove that there is no (1 m+e)-competitive strategy-proof mechanism, for any e>0. And, no mechanism can achieve a competitive ratio better than @math , when @math . Next we study the setting of two agents and m items, which is also the focus of [7]. We prove that the competitive ratio of any swap-dictatorial mechanism is no greater than @math . Then we give a characterization result: for the case of 2 items, if the mechanism is strategy-proof, symmetric and second order continuously differentiable, then it is always swap-dictatorial. In the end we consider a setting where an agent's valuation of each item is bounded by C m, where C is an arbitrary constant. We show a mechanism that is (1 2+e(C))-competitive, where e(C)>0. In the three-dimensional (3D) strip packing problem, we are given a set of 3D rectangular items and a 3D box @math . The goal is to pack all the items in @math such that the height of the packing is minimized. We consider the most basic version of the problem, where the items must be packed with their edges parallel to the edges of @math and cannot be rotated. Building upon Caprara's work for the two-dimensional (2D) bin packing problem, we obtain an algorithm that, given any @math , achieves an approximation of @math , where @math is the well-known number that occurs naturally in the context of bin packing. Our key idea is to establish a connection between bin packing solutions for an arbitrary instance @math and the strip packing solutions for the corresponding instance obtained from @math by applying the harmonic transformation to certain dimensions. Based on this connection, we also give a simple alternate proof of the @math approximation for 2D ... We consider a large class of random geometric graphs constructed from samples @math of independent, identically distributed observations of an underlying probability measure @math on a bounded domain @math . The popular modularity' clustering method specifies a partition @math of the set @math as the solution of an optimization problem. In this paper, under conditions on @math and @math , we derive scaling limits of the modularity clustering on random geometric graphs. Among other results, we show a geometric form of consistency: When the number of clusters is a priori bounded above, the discrete optimal partitions @math converge in a certain sense to a continuum partition @math of the underlying domain @math , characterized as the solution of a type of Kelvin's shape optimization problem. The multiple knapsack problem (MKP) is a natural and well-known generalization of the single knapsack problem and is defined as follows. We are given a set of @math items and @math bins (knapsacks) such that each item @math has a profit @math and a size @math , and each bin @math has a capacity @math . The goal is to find a subset of items of maximum profit such that they have a feasible packing in the bins. MKP is a special case of the generalized assignment problem (GAP) where the profit and the size of an item can vary based on the specific bin that it is assigned to. GAP is APX-hard and a 2-approximation, for it is implicit in the work of Shmoys and Tardos [Math. Program. A, 62 (1993), pp. 461-474], and thus far, this was also the best known approximation for MKP @. The main result of this paper is a polynomial time approximation scheme (PTAS) for MKP @. Apart from its inherent theoretical interest as a common generalization of the well-studied knapsack and bin packing problems, it appears to be the strongest special case of GAP that is not APX-hard. We substantiate this by showing that slight generalizations of MKP are APX-hard. Thus our results help demarcate the boundary at which instances of GAP become APX-hard. An interesting aspect of our approach is a PTAS-preserving reduction from an arbitrary instance of MKP to an instance with @math distinct sizes and profits. We consider a crowdsourcing model in which @math workers are asked to rate the quality of @math items previously generated by other workers. An unknown set of @math workers generate reliable ratings, while the remaining workers may behave arbitrarily and possibly adversarially. The manager of the experiment can also manually evaluate the quality of a small number of items, and wishes to curate together almost all of the high-quality items with at most an @math fraction of low-quality items. Perhaps surprisingly, we show that this is possible with an amount of work required of the manager, and each worker, that does not scale with @math : the dataset can be curated with @math ratings per worker, and @math ratings by the manager, where @math is the fraction of high-quality items. Our results extend to the more general setting of peer prediction, including peer grading in online classrooms. A stochastic combinatorial semi-bandit is an online learning problem where at each step a learning agent chooses a subset of ground items subject to constraints, and then observes stochastic weights of these items and receives their sum as a payoff. In this paper, we close the problem of computationally and sample efficient learning in stochastic combinatorial semi-bandits. In particular, we analyze a UCB-like algorithm for solving the problem, which is known to be computationally efficient; and prove @math and @math upper bounds on its @math -step regret, where @math is the number of ground items, @math is the maximum number of chosen items, and @math is the gap between the expected returns of the optimal and best suboptimal solutions. The gap-dependent bound is tight up to a constant factor and the gap-free bound is tight up to a polylogarithmic factor. This paper gives a dichotomy theorem for the complexity of computing the partition function of an instance of a weighted Boolean constraint satisfaction problem. The problem is parameterized by a finite set @math of nonnegative functions that may be used to assign weights to the configurations (feasible solutions) of a problem instance. Classical constraint satisfaction problems correspond to the special case of 0,1-valued functions. We show that computing the partition function, i.e., the sum of the weights of all configurations, is @math -complete unless either (1) every function in @math is of “product type,” or (2) every function in @math is “pure affine.” In the remaining cases, computing the partition function is in P. A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices, @math the minimum degree, and @math the maximum degree. We show that every graph has a domatic partition with @math dominating sets and, moreover, that such a domatic partition can be found in polynomial-time. This implies a @math -approximation algorithm for domatic number, since the domatic number is always at most @math . We also show this to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every @math , a @math -approximation implies that @math . This makes domatic number the first natural maximization problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better. We also show that every graph has a domatic partition with @math dominating sets, where the "o(1)" term goes to zero as @math increases. This can be turned into an efficient algorithm that produces a domatic partition of @math sets. This paper explores the preference-based top- @math rank aggregation problem. Suppose that a collection of items is repeatedly compared in pairs, and one wishes to recover a consistent ordering that emphasizes the top- @math ranked items, based on partially revealed preferences. We focus on the Bradley-Terry-Luce (BTL) model that postulates a set of latent preference scores underlying all items, where the odds of paired comparisons depend only on the relative scores of the items involved. We characterize the minimax limits on identifiability of top- @math ranked items, in the presence of random and non-adaptive sampling. Our results highlight a separation measure that quantifies the gap of preference scores between the @math and @math ranked items. The minimum sample complexity required for reliable top- @math ranking scales inversely with the separation measure irrespective of other preference distribution metrics. To approach this minimax limit, we propose a nearly linear-time ranking scheme, called , that returns the indices of the top- @math items in accordance to a careful score estimate. In a nutshell, Spectral MLE starts with an initial score estimate with minimal squared loss (obtained via a spectral method), and then successively refines each component with the assistance of coordinate-wise MLEs. Encouragingly, Spectral MLE allows perfect top- @math item identification under minimal sample complexity. The practical applicability of Spectral MLE is further corroborated by numerical experiments. In this paper we study noisy sorting without re-sampling. In this problem there is an unknown order @math for all pairs @math , where @math is a constant and @math for all @math and @math . It is assumed that the errors are independent. Given the status of the queries the goal is to find the maximum likelihood order. In other words, the goal is find a permutation @math that minimizes the number of pairs @math where @math . The problem so defined is the feedback arc set problem on distributions of inputs, each of which is a tournament obtained as a noisy perturbations of a linear order. Note that when @math and @math is large, it is impossible to recover the original order @math . It is known that the weighted feedback are set problem on tournaments is NP-hard in general. Here we present an algorithm of running time @math and sampling complexity @math that with high probability solves the noisy sorting without re-sampling problem. We also show that if @math is an optimal solution of the problem then it is close'' to the original order. More formally, with high probability it holds that @math and @math . Our results are of interest in applications to ranking, such as ranking in sports, or ranking of search items based on comparisons by experts. In the (d,n) group testing problem n items have to be identified as either good or defective and the number of defective items is known to be d. A test on an arbitrary group (subset) of items reveals either that all items in the group are good or that at least one of the items is defective, but not how many or which items are defective. We present a new algorithm which in the worst case needs less than @math tests more than the information lower bound @math for n d≥2. For n d≥38, the difference decreases to less than @math tests. For d≥10, this is a considerable improvement over the d−1 additional tests given for the best previously known algorithm by Hwang. We conjecture that the behaviour for large n and d of the difference is optimal for @math . This implies that the @math tests per defective given in the bound above are the best possible. We describe a new approximation algorithm for Max Cut. Our algorithm runs in @math time, where @math is the number of vertices, and achieves an approximation ratio of @math . In instances in which an optimal solution cuts a @math fraction of edges, our algorithm finds a solution that cuts a @math fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a @math fraction of edges, our spectral partitioning algorithm finds a set @math of vertices and a bipartition @math of @math such that at least a @math fraction of the edges incident on @math have one endpoint in @math and one endpoint in @math . (This can be seen as an analogue of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, var... This paper studies problems of inferring order given noisy information. In these problems there is an unknown order (permutation) @math on @math elements denoted by @math . We assume that information is generated in a way correlated with @math . The goal is to find a maximum likelihood @math given the information observed. We will consider two different types of observations: noisy comparisons and noisy orders. The data in Noisy orders are permutations given from an exponential distribution correlated with (this is also called the Mallow's model). The data in Noisy Comparisons is a signal given for each pair of elements which is correlated with their true ordering. In this paper we present polynomial time algorithms for solving both problems with high probability. As part of our proof we show that for both models the maximum likelihood solution @math is close to the original permutation @math . Our results are of interest in applications to ranking, such as ranking in sports, or ranking of search items based on comparisons by experts. Let @math be an induced subgraph of the hypercube @math for some @math . We show that if @math is a power of @math then, for sufficiciently large @math , the vertex set of @math can be partitioned into induced copies of @math . This answers a question of Offner. In fact, we prove a stronger statement: if @math is a subset of @math for some @math and if @math is a power of @math , then, for sufficiently large @math , @math can be partitioned into isometric copies of @math . Suppose the complex matrix M is partitioned into a @math array of blocks; let @math . The generalized Schur complement of A in M is defined to be @math , where @math is the Moore–Penrose inverse of A. The relationship of the ranks of M, A, and @math is determined. A new proof, under certain conditions, of Sylvester’s determinantal formula is given. A quotient formula like one previously proved for the Schur complement is obtained. Finally, several known inequalities for positive semidefinite Hermitian matrices are generalized. Several algorithms with an approximation guarantee of @math are known for the Set Cover problem, where @math is the number of elements. We study a generalization of the Set Cover problem, called the Partition Set Cover problem. Here, the elements are partitioned into @math , and we are required to cover at least @math elements from each color class @math , using the minimum number of sets. We give a randomized LP-rounding algorithm that is an @math approximation for the Partition Set Cover problem. Here @math denotes the approximation guarantee for a related Set Cover instance obtained by rounding the standard LP. As a corollary, we obtain improved approximation guarantees for various set systems for which @math is known to be sublogarithmic in @math . We also extend the LP rounding algorithm to obtain @math approximations for similar generalizations of the Facility Location type problems. Finally, we show that many of these results are essentially tight, by showing that it is NP-hard to obtain an @math -approximation for any of these problems. We study a random graph model named the "block model" in statistics and the "planted partition model" in theoretical computer science. In its simplest form, this is a random graph with two equal-sized clusters, with a between-class edge probability of @math and a within-class edge probability of @math . A striking conjecture of Decelle, Krzkala, Moore and Zdeborov 'a based on deep, non-rigorous ideas from statistical physics, gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if @math and @math , @math and @math then conjectured that it is possible to efficiently cluster in a way correlated with the true partition if @math and impossible if @math for some sufficiently large @math . In a previous work, we proved that indeed it is information theoretically impossible to to cluster if @math . A different independent proof of the same result was recently obtained by Laurent Massoulie. We study the classic Bin Packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio between updates. Formally, each item @math has a @math , and we want to use @math bins and incur a movement cost @math , either in the worst case, or in an amortized sense, for @math as small as possible. We call @math the of the algorithm. This is motivated by cloud storage applications, where fully-dynamic Bin Packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure. Let @math be a partially ordered set. If the Boolean lattice @math can be partitioned into copies of @math for some positive integer @math , then @math must satisfy the following two trivial conditions: (1) the size of @math is a power of @math , (2) @math has a unique maximal and minimal element. Resolving a conjecture of Lonc, it was shown by Gruslys, Leader and Tomon that these conditions are sufficient as well. In this paper, we show that if @math only satisfies condition (2), we can still almost partition @math into copies of @math . We prove that if @math has a unique maximal and minimal element, then there exists a constant @math such that all but at most @math elements of @math can be covered by disjoint copies of @math . We address the following problem: Given a complete @math -partite geometric graph @math whose vertex set is a set of @math points in @math , compute a spanner of @math that has a “small” stretch factor and “few” edges. We present two algorithms for this problem. The first algorithm computes a @math -spanner of @math with @math edges in @math time. The second algorithm computes a @math -spanner of @math with @math edges in @math time. The latter result is optimal: We show that for any @math , spanners with @math edges and stretch factor less than 3 do not exist for all complete @math -partite geometric graphs.