Distributed Virtual Environments (DVEs), such as online games, military simulations, collaborative design, etc., are very popular nowadays. To support large-scale DVEs, a multi-server architecture is usually employed,...
详细信息
Distributed Virtual Environments (DVEs), such as online games, military simulations, collaborative design, etc., are very popular nowadays. To support large-scale DVEs, a multi-server architecture is usually employed, and the virtual world is partitioned into multiple zones for load distribution. The client assignment problem arises when assigning the participating clients to the servers. Current approaches usually assign clients to servers according to the locations of clients in the virtual world, i.e., clients interacting in the same zone of the virtual world will be assigned to the same server. This approach may degrade the interactivity of DVEs if the network delay from a client to its assigned server is large. In this paper, we formulate the client assignment problem, and propose two algorithms to assign clients to servers in a more efficient way. The proposed algorithms are based on the heuristics developed for the well-known Terminal Assignment problem. Simulation results with the BRITE Internet Topology Generator show that our algorithms are effective in enhancing the interactivity of DVEs.
We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. The extent of fairness of an allocation is measured by its Nash social welfare, which is the geometric mean o...
详细信息
We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. The extent of fairness of an allocation is measured by its Nash social welfare, which is the geometric mean of the valuations of the agents for their bundles. While the problem of maximizing Nash social welfare is known to be APX-hard in general, we study the effectiveness of simple, greedy algorithms in solving this problem in two interesting special ***, we show that a simple, greedy algorithm provides a 1.061-approximation guarantee when agents have identical valuations, even though the problem of maximizing Nash social welfare remains NP-hard for this setting. Second, we show that when agents have binary valuations over the goods, an exact solution (i.e., a Nash optimal allocation) can be found in polynomial time via a greedy algorithm. Our results in the binary setting extend to provide novel, exact algorithms for optimizing Nash social welfare under concave valuations. Notably, for the above mentioned scenarios, our techniques provide a simple alternative to several of the existing, more sophisticated techniques for this problem such as constructing equilibria of Fisher markets or using real stable polynomials.
Various versions of the shortest common superstring (SCS) problem play important roles in data compression and DNA sequencing. For example, in laboratories DNA sequencing is routinely done by sequencing large numbers ...
详细信息
Various versions of the shortest common superstring (SCS) problem play important roles in data compression and DNA sequencing. For example, in laboratories DNA sequencing is routinely done by sequencing large numbers of relatively short fragments, and then heuristically finding a short common superstring. We assume that the input strings are independently generated, and we adopt a mixing model for the underlying probabilistic model of strings generation.
We consider the MAX-2-SAT problem on d-degenerate formulas. This class of 2-CNFs is a generalization of 2-CNFs of bounded tree width. We first show that the class of d-degenerate formulas is very broad, since random f...
详细信息
We consider the MAX-2-SAT problem on d-degenerate formulas. This class of 2-CNFs is a generalization of 2-CNFs of bounded tree width. We first show that the class of d-degenerate formulas is very broad, since random formulas can be shown to be d-degenerate for an appropriate d. Then we test several heuristic algorithms on random d-degenerate formulas and compare results against similar tests on regular random 2-CNFs. Finally, we model the performance of one of these algorithms, the greedy one, on both random and random d-degenerate formulas by systems of differential equations.
Chebyshev greedy Algorithm is a generalization of the well known Orthogonal Matching Pursuit defined in a Hilbert space to the case of Banach spaces. We apply this algorithm for constructing sparse approximate solutio...
详细信息
ISBN:
(纸本)9781479982981
Chebyshev greedy Algorithm is a generalization of the well known Orthogonal Matching Pursuit defined in a Hilbert space to the case of Banach spaces. We apply this algorithm for constructing sparse approximate solutions (with respect to a given dictionary) to convex optimization problems. Along with algorithms that use exact evaluations, algorithms with approximate evaluations are discussed. Convergence and rate of convergence results are obtained.
A wide class of problems in coding theory are dealt with using a greedy algorithm due to Stein (1974) and Lovasz (1975). Some examples, including constructing covering codes, codes for conflict resolution, separating ...
详细信息
A wide class of problems in coding theory are dealt with using a greedy algorithm due to Stein (1974) and Lovasz (1975). Some examples, including constructing covering codes, codes for conflict resolution, separating systems, source encoding with distortion, etc., are given a unified treatment.
Many real life applications are subject to changes which can be modeled as dynamic graphs. In this paper, we are interested especially in the dynamic graph coloring. We focus on coloring using online algorithms and we...
详细信息
Many real life applications are subject to changes which can be modeled as dynamic graphs. In this paper, we are interested especially in the dynamic graph coloring. We focus on coloring using online algorithms and we propose new greedy approaches to solve it efficiently.
greedy algorithms constitute an apparently simple algorithm design technique, but its learning goals are not simple to achieve. We present a didactic method aimed at promoting active learning of greedy algorithms. The...
详细信息
greedy algorithms constitute an apparently simple algorithm design technique, but its learning goals are not simple to achieve. We present a didactic method aimed at promoting active learning of greedy algorithms. The method is focused on the concept of selection function, and is based on explicit learning goals. It mainly consists of an experimental method and the interactive system, GreedEx, that supports it. We also present our experience of five years using the didactic method and the evaluations we conducted to refine it, which are of two kinds: usability evaluations of GreedEx and analysis of students' reports. Usability evaluations revealed a number of opportunities of improvement for GreedEx, and the analysis of students' reports showed a number of misconceptions. We made use of these findings in several ways, mainly: improving GreedEx, elaborating lecture notes that address students' misconceptions, and adapting the class and lab sessions and materials. As a consequence of these actions, our didactic method currently satisfies its initial goals. The article has two main contributions. First, the didactic method itself can be valuable for computer science educators in their teaching of algorithms. Secondly, the refinement process we have carried out, which was a multifaceted, medium-term action research, can be of interest to researchers of technology-supported computing education, since it illustrates how the didactic method was integrated into our educational practice.
This paper introduces Empirically Adjusted greedy Heuristics (EAGH), a procedure for designing greedy algorithms for a given combinatorial optimization problem and illustrates the way in which EAGH works with an appli...
详细信息
This paper introduces Empirically Adjusted greedy Heuristics (EAGH), a procedure for designing greedy algorithms for a given combinatorial optimization problem and illustrates the way in which EAGH works with an application to minimize the makespan in the permutation flow-shop problem. The basic idea behind EAGH is that a greedy heuristic can be seen as a member of an infinite set of heuristics, this set being defined by a function that depends on several parameters. Each set of values of the parameters corresponds to a specific greedy heuristic. Then, the best element of the set, for a training set of instances of the problem, is found by applying a non-linear optimization algorithm to a function that measures the quality of the obtained solutions to the instances of the training set, and which depends on the parameters that characterize each specific algorithm. EAGH allows improving known heuristics or finding good new ones. Journal of the Operational Research Society (2011) 62, 1704-1710. doi:10.1057/jors.2010.131 Published online 25 August 2010
In this paper, we present the greedy reconfiguration algorithm (GRA) and the fast greedy reconfiguration algorithm (FGRA)-two reconfiguration algorithms that minimize the energy not supplied (ENS) of medium-voltage (M...
详细信息
In this paper, we present the greedy reconfiguration algorithm (GRA) and the fast greedy reconfiguration algorithm (FGRA)-two reconfiguration algorithms that minimize the energy not supplied (ENS) of medium-voltage (MV)-distribution network (DNs). The algorithms are derived from a graph-theoretic model for the MV-DNs and an iterative formulation for the ENS. Given a DN composed of n loads, GRA yields an initial radial topology with minimal ENS after executing n - 1 iterations of a multistage decision process. Next, GRA executes a verification algorithm to evaluate all of those candidate topologies randomly discarded during the decision process. After the second stage, GRA announces the optimal topology as well as the minimum ENS of the system. The second algorithm proposed is called FGRA and is obtained when heuristic graph compression is performed throughout the execution of GRA. The aforementioned graph compression reduces the dimension of the problem, thereby producing substantial savings in computing time at the expense of possibly achieving a suboptimal solution.
暂无评论