Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

Intuitionistic fuzzy soft modules

Molodtsov (1999) initiated the concept of soft sets in [1]. Maji et al. (2003) defined some operations on soft sets in [22]. Akta? and Ça?man (2007) generalized soft sets by defining the concept of soft groups in [16]. After them, Sun et al. (2008) gave soft modules in [21]. In this paper, the concept of an intuitionistic fuzzy soft module is introduced and some operations on intuitionistic fuzzy soft sets are given. Finally, some of its basic properties are studied.     

The Power of Priority Algorithms for Facility Location and Set Cover

We apply and extend the priority algorithm framework introduced by Borodin, Nielsen, and Rackoff to define greedy-like algorithms for the (uncapacitated) facility location problems and set cover problems. These problems have been the focus of extensive research from the point of view of approximation algorithms and for both problems greedy-like algorithms have been proposed and analyzed. The priority algorithm definitions are general enough to capture a broad class of algorithms that can be characterized as greedy-like while still possible to derive non-trivial lower bounds on the approximability of the problems by algorithms in such a class. Our results are orthogonal to complexity considerations, and hence apply to algorithms that are not necessarily polynomial time.     

Specifications for decidable hybrid games

We introduce STORMED hybrid games (SHG), a generalization of STORMED hybrid systems, Vladimerou et al. (2008) [33], which have natural specifications that allow rich continuous dynamics and various decidable properties. We solve the control problem for SHG using a reduction to bisimulation on finite game graphs. This generalizes to a greater family of games, which includes o-minimal hybrid games, Bouyer et al. (2006) [6]. We also solve the optimal-cost reachability problem for Weighted SHG and prove decidability of WCTL for Weighted STORMED hybrid systems.     

Succinct representation of dynamic trees

We study the problem of maintaining a dynamic ordered tree succinctly under updates of the following form: insertion or deletion of a leaf, insertion of a node on an edge (edge subdivision) or deletion of a node with only one child (the child becomes a child of its former grandparent). We allow satellite data of a fixed size to be associated to the nodes of the tree.We support update operations in constant amortized time and support access to satellite data and basic navigation operations in worst-case constant time; the basic navigation operations include parent, first/last-child, previous/next-child. These operations are moving from a node to its parent, leftmost/rightmost child, and its previous and next child respectively.We demonstrate that to efficiently support more extended operations, such as determining the i-th child of a node, rank of a child among its siblings, or size of the subtree rooted at a node, one requires a restrictive pattern for update strategy, for which we propose the finger-update model. In this model, updates are performed at the location of a finger that is only allowed to crawl on the tree between a child and a parent or between consecutive siblings. Under this model, we describe how the named extended operations are performed in worst-case constant time.Previous work on dynamic succinct trees (Munro et al., 2001 [17]; Raman and Rao, 2003 [19]) is mainly restricted to binary trees and achieves poly-logarithmic (Munro et al., 2001 [17]) or “poly-log-log” (Raman and Rao, 2003 [19]) update time under a more restricted model, where updates are performed in traversals starting at the root and ending at the root and queries can be answered when the traversal is completed. A previous result on ordinal trees achieves only sublinear amortized update time and “poly-log-log” query time (Gupta et al., 2007 [11]). More recently, the update time has been improved to O(logn/loglogn) while queries can be performed in O(logn/loglogn) time (Sadakane and Navarro, 2010 [20]).     

A note on maximizing the spread of influence in social networks

We consider the spread maximization problem that was defined by Domingos and Richardson (2001, 2002) [7] and [22]. In this problem, we are given a social network represented as a graph and are required to find the set of the most “influential” individuals that by introducing them with a new technology, we maximize the expected number of individuals in the network, later in time, that adopt the new technology. This problem has applications in viral marketing, where a company may wish to spread the rumor of a new product via the most influential individuals in popular social networks such as Myspace and Blogsphere.The spread maximization problem was recently studied in several models of social networks (Kempe et al. (2003, 2005) [14] and [15], Mossel and Roch (2007) [20]). In this short paper we study this problem in the context of the well studied probabilistic voter model. We provide very simple and efficient algorithms for solving this problem. An interesting special case of our result is that the most natural heuristic solution, which picks the nodes in the network with the highest degree, is indeed the optimal solution.     

On the small cycle transversal of planar graphs

We consider the problem of finding a k-edge transversal set that intersects all (simple) cycles of length at most s in a planar graph, where s≥3 is a constant. This problem, referred to as Small Cycle Transversal, is known to be NP-complete. We present a polynomial-time algorithm that computes a kernel of size 36s³k for Small Cycle Transversal. In order to achieve this kernel, we extend the region decomposition technique of Alber et al. (2004) [1] by considering a unique region decomposition that is defined by shortest paths. Our kernel size is a significant improvement in terms of s over the kernel size obtained under the meta-kernelization framework by Bodlaender et al. (2009) [7].     

On the stability of solution mapping for parametric generalized vector quasiequilibrium problems

In this paper, we study the solution stability for a class of parametric generalized vector quasiequilibrium problems. By virtue of the parametric gap function, we obtain a sufficient and necessary condition for the Hausdorff lower semicontinuity of the solution mapping to the parametric generalized vector quasiequilibrium problem. The results presented in this paper generalize and improve some main results of Chen et al. (2010) [34], and Zhong and Huang (2011) [35].     

Soft sets and soft rings

Molodtsov (1999) introduced the concept of soft sets in [1]. Then, Maji et al. (2003) defined some operations on soft sets in [2]. Akta? and Ça?man (2007) defined the notion of soft groups in [3]. Finally, soft semirings are defined by Feng et al. (2008) in [5]. In this paper, we have introduced initial concepts of soft rings.     

Convergence theorems by a new iteration process for a finite family of nonself asymptotically nonexpansive mappings with errors in Banach spaces

In this paper, we study a new iteration process for a finite family of nonself asymptotically nonexpansive mappings with errors in Banach spaces. We prove some weak and strong convergence theorems for this new iteration process. The results of this paper improve and extend the corresponding results of Chidume et al. (2003) [10], Osilike and Aniagbosor (2000) [3], Schu (1991) [4], Takahashi and Kim (1998) [9], Tian et al. (2007) [18], Wang (2006) [11], Yang (2007) [17] and others.     

Sharpening Occam's razor

We provide a new representation-independent formulation of Occam's razor theorem, based on Kolmogorov complexity. This new formulation allows us to: (i) obtain better sample complexity than both length-based [Blumer et al., Inform. Process. Lett. 24 (1987) 377-380] and VC-based [Blumer et al., J. ACM 35 (1989) 929-965] versions of Occam's razor theorem, in many applications; and (ii) achieve a sharper reverse of Occam's razor theorem than that of Board and Pitt [STOC, 1999, pp. 54-63]. Specifically, we weaken the assumptions made by Board and Pitt [STOC, 1999, pp. 54-63] and extend the reverse to superpolynomial running times.     

BubbleSearch: A simple heuristic for improving priority-based greedy algorithms

We introduce BubbleSearch, a general approach for extending priority-based greedy heuristics. Following the framework recently developed by Borodin et al., we consider priority algorithms, which sequentially assign values to elements in some fixed or adaptively determined order. BubbleSearch extends priority algorithms by selectively considering additional orders near an initial good ordering. While many notions of nearness are possible, we explore algorithms based on the Kendall-tau distance (also known as the BubbleSort distance) between permutations. Our contribution is to elucidate the BubbleSearch paradigm and experimentally demonstrate its effectiveness.     

Graph Spanners in the Streaming Model: An Experimental Study

This article reports the results of an extensive experimental analysis of efficient algorithms for computing graph spanners in the data streaming model, where an (α,β)-spanner of a graph G is a subgraph S⊆G such that for each pair of vertices the distance in S is at most α times the distance in G plus β. To the best of our knowledge, this is the first computational study of graph spanner algorithms in a streaming setting. We compare experimentally the randomized algorithms proposed by Baswana () and by Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, pp. 716–727, 9–13 July 2007) for general stretch factors with the deterministic algorithm presented by Ausiello et al. (In: Proceedings of the 15th Annual European Symposium on Algorithms (ESA 2007), Engineering and Applications Track, Eilat, Israel, 8–10 October 2007. LNCS, vol. 4698, pp. 605–617, 2007), designed for building small stretch spanners. All the algorithms we implemented work in a data streaming model where the input graph is given as a stream of edges in arbitrary order, and all of them need a single pass over the data. Differently from the algorithm in Ausiello et al., the algorithms in Baswana () and Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, pp. 716–727, 9–13 July 2007) need to know in advance the number of vertices in the graph. The results of our experimental investigation on several input families confirm that all these algorithms are very efficient in practice, finding spanners with stretch and size much smaller than the theoretical bounds and comparable to those obtainable by off-line algorithms. Moreover, our experimental findings confirm that small values of the stretch factor are the case of interest in practice, and that the algorithm by Ausiello et al. tends to produce spanners of better quality than the algorithms by Baswana and Elkin, while still using a comparable amount of time and space resources. Work partially supported by the Italian Ministry of University and Research under Project MAINSTREAM “Algorithms for Massive Information Structures and Data Streams”. A preliminary version of this paper was presented at the 15th Annual European Symposium on Algorithms (ESA 2007) 5.     

CMBE v05—Implementation of a toy-model for chaos analysis of relativistic nuclear collisions at the present BNL energies

In this paper we present a new version of Chaos Many-Body Engine (CMBE) Grossu et al. (2014) [1]. Inspired by the Mean Free Path concept, we implemented a new parameter, namely the “Mean Free Time”, which is defined as the mean time between one particle’s creation and its stimulated decay. This new parameter should be understood as an effect of the nuclear environment and, as opposed to the particle lifetime, it has the advantage of not being affected by the relativistic dilation. In [2] we presented a toy-model for chaos analysis of relativistic nuclear collisions at 4.5 A GeV/c (the SKM 200 collaboration). In this work, we extended our model to 200 A GeV (the maximum BNL energy).     

Cooperative strategies of wireless access technologies: A game-theoretic analysis

The wireless Internet has to overcome the problem of spectrum scarcity as the number of mobile equipments could increase even by an order of magnitude in the next decade; the cooperation of mobile devices is foreseeable as a feasible solution to the problems. There exists a large body of literature on opportunistic ad hoc networking including Pelusi et al. (2006) [25], Chen et al. (2006) [26], Hui et al. (2005) [27]; however, the impact of the location of the devices on their access method selection is not yet appropriately dealt with. In this paper, we address this issue based on game-theoretic analyses. The key contribution of our work is threefold. First, we model the access method selection of mobile devices by extending the classical forwarding game with position, mobility, and availability of the devices. Second, we apply the model in game-theoretic analyses to better understand the optimal cooperation strategies in the presence of heterogeneous wireless technologies. We further extend our framework to include uncertainty. Finally, we present the applicability of the model in a cognitive radio scenario where complex structures of parameters are included.     

Some optimization problems on weak-bisplit graphs

A new decomposition scheme for bipartite graphs namely canonical decomposition was introduced by Fouquet et al. [Internat. J. Found. Comput. Sci. 10 (1999) 513-533]. The so-called weak-bisplit graphs are totally decomposable following this decomposition. We present here some optimization problems for general bipartite graphs which have efficient solutions when dealing with weak-bisplit graphs.     

A Stronger Model of Dynamic Programming Algorithms

We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Complexity, pp. 308–322, 2005), which is in turn a generalization of the priority algorithms model of Borodin, Nielson and Rackoff. One of the distinguishing features of these models is that they not only capture large classes of algorithms generally considered to be greedy, backtracking or dynamic programming algorithms, but they also allow characterizations of their limitations. Hence they give meaning to the statement that a given problem can or cannot be solved by dynamic programming. After defining the model, we prove three main results: (i) that certain types of natural restrictions of our seemingly more powerful model can be simulated by the BT model; (ii) that in general our model is stronger than the BT model—a fact which is witnessed by the classical shortest paths problem; (iii) that our model has very real limitations, namely that bipartite matching cannot be efficiently computed in it, hence suggesting that there are problems that can be solved efficiently by network flow algorithms and by simple linear programming that cannot be solved by natural dynamic programming approaches.