Maximizing a submodular set function subject to a matroid constraint (2009)
1 Introduction This paper is motivated by the following optimization problem. We are givena ground set N of n elements and a non-decreasing submodular set function f: 2N! R+. The function f is...
Monitoring Schedules for Randomly Deployed Sensor Networks (2009)
Gruia Calinescu, Robert B. Ellis
Abstract Given n sensors and m targets, a monitoring schedule is a partition of the sensor set such that each part of the partition can monitor all targets. Monitoring schedules are used to maximize...
Compressing Rectilinear Pictures and Minimizing Access Control Lists (2008)
Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
Analytical Bounds on Broadcast with Hitch-hiking in Wireless Ad-HocNetworks (2008)
Abstract Recently, there have been papers indicating that the maximal ratio combiner device can result inenergy savings in wireless ad hoc networks by using Hitch-hiking. We study the Min-Energy...
Maximizing a Monotone Submodular Function subject to a Matroid Constraint (2008)
Gruia Calinescu, Chandra Chekuri, Martin Pal, Jan Vondrak
Let f: 2 X → R+ be a monotone submodular set function, and let (X, I) be a matroid. We consider the problem maxS∈I f(S). It is known that the greedy algorithm yields a 1/2 approximation [14] for...
On the k-Structure Ratio in Planar and Outerplanar Graphs (2008)
Gruia Calinescu, Cristina G. Fernandes
A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight...
SONET (Synchronous Optical NETworks) add-drop (2007)
multiplexers (ADMs) are the dominant cost factor in the
Splitable Traffic Partition in WDM/SONET Rings to Minimize SONET ADMs (2007)
SONET ADMs are the dominant cost factor in the WDM/SONET rings. Recently several articles [2, 3, 6, 10, 14] proposed a number of heuristics for trac partition so as to use as few SONET ADMs as...
Gruia Calinescu, Amit Chakrabarti, Howard Karloff, Yuval Rabani
Abstract. We study the problem of finding a most profitable subset of n given tasks, each with a given start and finish time as well as profit and resource requirement, that at no time exceeds the...
Gruia Calinescu, Howard Karlo, Yuval Rabani
Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the...
Selecting Forwarding Neighbors in (2007)
Wireless Ad Hoc, Gruia Calinescu, Peng-jun Wan, Alexander Z. Zelikovsky
Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as flooding, is to let every node retransmit the message to all its 1-hop...
Maximizing a Submodular Set Function subject to a Matroid Constraint (2007)
Gruia Calinescu, Ra Chekuri, Martin Pál, Jan Vondrák
Abstract. Let f: 2 N → R + be a non-decreasing submodular set function, and let (N, I) be a matroid. We consider the problem maxS∈I f(S). It is known that the greedy algorithm yields a...
David L. Applegate, Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
David L. Applegate, Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
Maximizing a Submodular Set Function subject to a Matroid Constraint (2007)
Gruia Calinescu, Ra Chekuri, Jan Vondrák
Abstract. Let f:2 N →R + be a non-decreasing submodular set function, and let (N,I) be a matroid. We consider the problem maxS∈I f(S). It is known that the greedy algorithm yields a...
Compressing rectilinear pictures and minimizing access control lists (2007)
Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
Maximizing a Submodular Set Function subject to a Matroid Constraint (2007)
Gruia Calinescu, Ra Chekuri, Martin Pál, Jan Vondrák
Abstract. Let f: 2 N → R + be a non-decreasing submodular set function, and let (N, I) be a matroid. We consider the problem maxS∈I f(S). It is known that the greedy algorithm yields a...
Gruia Calinescu, Sanjiv Kapoor, Er Zelikovsky, Antti Hyvärinen
In ad-hoc wireless networks, certain network connectivity constraints are of interest because of their practical importance. An example of such a constraint would be strong connectivity. The aim is...
Power Efficient Range Assignment in Ad-hoc Wireless (2003)
Althaus,Ernst, Calinescu,Gruia, Mandoiu,Ion, Prasad,Sushil, Tchervenski,Nickolay, Zelikovsly,Alexander
Power Efficient Range Assignment in Ad-hoc Wireless (2003)
Althaus, Ernst, Calinescu, Gruia, Mandoiu, Ion, Prasad, Sushil, Tchervenski, Nickolay, Zelikovsly, Alexander
Localized Delaunay Triangulation with Application in Ad Hoc Wireless Networks (2003)
Xiang-yang Li, Gruia Calinescu, Peng-jun Wan, Yu Wang, Student Member
Abstract—Several localized routing protocols guarantee the delivery of the packets when the underlying network topology is a planar graph. Typically, relative neighborhood graph (RNG) or Gabriel...
Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks (2003)
Gruia Calinescu, Sanjiv Kapoor, Er Olshevsky
Abstract. Used for topology control in ad-hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity) The input...
Localized Delaunay Triangulation with Application in Ad Hoc Wireless Networks (2003)
Xiang-yang Li, Gruia Calinescu, Peng-jun Wan, Yu Wang
Several localized routing protocols guarantee the delivery of the packets when the underlying network topology is a planar graph. Typically, relative neighborhood graph (RNG) or Gabriel graph (GG) is...
Range Assignment for High Connectivity in Wireless Ad Hoc Networks (2003)
Depending on whether bidirectional links or unidirectional links are used for communications, the network topology under a given range assignment is either an undirected graph referred to as the...
Computing 2-Hop Neighborhoods in Ad Hoc Wireless Networks (2003)
We present efficient distributed algorithms for computing 2-hop neighborhoods in Ad Hoc Wireless Networks. The knowledge of the 2-hop neighborhood is assumed in many protocols and algorithms for...
Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks (2003)
Gruia Calinescu, Sanjiv Kapoor, Alexander Olshevsky, Alexander Zelikovsky
Used for topology control in ad-hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity) The input consists of...
Distributed Construction of a Planar Spanner and Routing for Ad Hoc Wireless Networks (2002)
Xiang-yang Li, Gruia Calinescu, Peng-jun Wan
Several localized routing protocols [1] guarantee the delivery of the packets when the underlying network topology is the Delaunay triangulation of all wireless nodes. However, it is expensive to...
Improved Approximation Algorithms for Resource Allocation (2002)
Gruia Calinescu, Amit Chakrabarti, Howard Karloff, Yuval Rabani
We study the problem of nding a most pro table subset of n given tasks, each with a given start and nish time as well as pro t and resource requirement, that at no time exceeds the quantity B of...
Approximation algorithms for the 0-extension problem (2001)
Gruia Calinescu, Howard Karloff, Yuval Rabani
Abstract. In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to...
Approximation algorithms for the 0-extension problem (2001)
Gruia Calinescu, Howard Karloff, Yuval Rabani
In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as...
Approximation Algorithms for the 0-Extension Problem (2000)
Gruia Calinescu, Howard Karloff, Yuval Rabani
In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as...
Approximation algorithms for graph-theoretic problems : planar subgraphs and multiway cut (1998)
PhD
Approximation algorithms for graph-theoretic problems : planar subgraphs and multiway cut (1998)
Ph.D.
Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width (1998)
Gruia Calinescu, Cristina G. Fern, Es Bruce Reed
The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices (s i, t i) of G, find a minimum set of edges of G whose removal disconnects each s i from the...
Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width (1998)
Gruia Calinescu, Cristina G. Fernandes, Bruce Reed
The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices (s i ; t i ) of G, find a minimum set of edges of G whose removal disconnects each s i from the...
Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width (1998)
Gruia Calinescu, Cristina G. Fernandes, Bruce Reed
. The Multicut problem is defined as follows: given a graph G and a collection of pairs of distinct vertices (s i ; t i ) of G, find a smallest set of edges of G whose removal disconnects each s i...
Gruia Calinescu, Howard Karloff, Yuval Rabani
Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1998)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the first algorithm with a nontrivial approximation ratio for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-Hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This...
Multicuts in Unweighted Graphs and Digraphs with Bounded Degree and Bounded Tree-Width (1998)
Gruia Calinescu, Cristina G. Fernandes, Bruce Reed
this paper. Also, we show that Directed Edge Multicut is NP-hard in digraphs with treewidth one and maximum in and out degree three. Other hardness results indicate why we cannot eliminate any of the...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1997)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-Hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1997)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the rst nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-Hard problem of nding a heaviest planar subgraph in an edge-weighted graph G. This problem has...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1997)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the first nontrivial approximation algorithm for maximum weight planar subgraph, the NPhard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has...
Alphabet Independent And Dictionary Scaled Matching (1996)
The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of...
Alphabet Independent And Dictionary Scaled Matching (1996)
Amihood Amir Gruia, Amihood Amir, Gruia Calinescu
The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of...
A Better Approximation Algorithm for Finding Planar Subgraphs (1996)
Gruia Calinescu, Cristina G. Fernandes, Ulrich Finkler, Howard Karloff
The MAXIMUM PLANAR SUBGRAPH problem---given a graph G, find a largest planar subgraph of G---has applications in circuit layout, facility layout, and graph drawing. No previous polynomialtime...
A Better Approximation Algorithm for Finding Planar Subgraphs (1996)
Gruia Calinescu, Cristina G. Fernandes, Ulrich Finkler, Howard Karloff
The MAXIMUM PLANAR SUBGRAPH problem---given a graph G, find a largest planar subgraph of G---has applications in circuit layout, facility layout, and graph drawing. No previous polynomial-time...
Finding Large Planar Subgraphs and Large Subgraphs of a Given Genus (1996)
Gruia Calinescu, Cristina G. Fernandes
. We consider the MAXIMUM PLANAR SUBGRAPH problem - given a graph G, find a largest planar subgraph of G. This problem has applications in circuit layout, facility layout, and graph drawing. We...
A Better Approximation Algorithm for Finding Planar Subgraphs (1996)
Gruia Calinescu, Cristina G. Fernandes, Ulrich Finkler, Howard Karloff
The MAXIMUM PLANAR SUBGRAPH problem---given a graph G, find a largest planar subgraph of G---has applications in circuit layout, facility layout, and graph drawing. No previous polynomialtime...
ARTICLE NO. AL970920 A Better Approximation Algorithm for Finding Planar Subgraphs (1996)
Gruia Calinescu, Cristina G. Fern, Ulrich Finkler, Howard Karloff
The MAXIMUM PLANAR SUBGRAPH problem�given a graph G, find a largest planar subgraph of G�has applications in circuit layout, facility layout, and graph drawing. No previous polynomial-time...
FA{S,T}ER Scaled Matching (1993)
Amir, Amihood, Calinescu, Gruia
The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of...
Fa{s,t}er Scaled Matching (1993)
The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of...
FA{S,T}ER Scaled Matching (1993)
Amir, Amihood, Calinescu, Gruia
The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of...