Search

Your search keyword '"Călinescu, Gruia"' showing total 92 results
Start Over Author "Călinescu, Gruia"
92 results on '"Călinescu, Gruia"'

1. Online Flexible Busy Time Scheduling on Heterogeneous Machines

Author

Calinescu, Gruia, Davies, Sami, Khuller, Samir, and Zhang, Shirley

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We study the online busy time scheduling model on heterogeneous machines. In our setting, unit-length jobs arrive online with a deadline that is known to the algorithm at the job's arrival time. An algorithm has access to machines, each with different associated capacities and costs. The goal is to schedule jobs on machines before their deadline, so that the total cost incurred by the scheduling algorithm is minimized. Relatively little is known about online busy time scheduling when machines are heterogeneous (i.e., have different costs and capacities), despite this being the most practical model for clients using cloud computing services. We make significant progress in understanding this model by designing an 8-competitive algorithm for the problem on unit-length jobs, and providing a lower bound on the competitive ratio of 2. We further prove that our lower bound is tight in the natural setting when jobs have agreeable deadlines.

Published
2024

2. An Improved Algorithm for Finding Maximum Outerplanar Subgraphs

Author

Calinescu, Gruia, Kaul, Hemanshu, and Kudarzi, Bahareh

Subjects
Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics
Abstract

We study the NP-complete Maximum Outerplanar Subgraph problem. The previous best known approximation ratio for this problem is 2/3. We propose a new approximation algorithm which improves the ratio to 7/10.

Published
2023

6. Improved Approximation Algorithms for Minimum Power Covering Problems

Author

Calinescu, Gruia, Kortsarz, Guy, Nutov, Zeev, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Epstein, Leah, editor, and Erlebach, Thomas, editor

Published
2018
Full Text
View/download PDF

7. Faster Compression of Patterns to Rectangle Rule Lists

Author

Da Silva, Ian Albuquerque Raymundo, Calinescu, Gruia, De Graaf, Nathan, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Tang, Shaojie, editor, Du, Ding-Zhu, editor, Woodruff, David, editor, and Butenko, Sergiy, editor

Published
2018
Full Text
View/download PDF

8. 1.85 Approximation for Min-Power Strong Connectivity

Author

Calinescu, Gruia

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Given a directed simple graph G=(V,E) and a nonnegative-valued cost function the power of a vertex u in a directed spanning subgraph H is given by the maximum cost of an arcs of H exiting u. The power of H is the sum of the power of its vertices. Power Assignment seeks to minimize the power of H while H satisfies some connectivity constraint. In this paper, we assume E is bidirected (for every directed edge e in E, the opposite edge exists and has the same cost), while H is required to be strongly connected. This is the original power assignment problem introduced by Chen and Huang in 1989, who proved that bidirected minimum spanning tree has approximation ratio at most 2 (this is tight). In Approx 2010, we introduced a Greedy approximation algorithm and claimed a ratio of 1.992. Here we improve the analysis to 1.85. The proof also shows that a natural linear programming relaxation, introduced by us in 2012, has the same 1.85 integrality gap., Comment: Same algorithm, with the analysis improved and simplified

Published
2012

13. Adversary Games in Secure/Reliable Network Routing

Author

Calinescu, Gruia, Kapoor, Sanjiv, Quinn, Michael, Shin, Junghwan, Akan, Ozgur, Series editor, Bellavista, Paolo, Series editor, Cao, Jiannong, Series editor, Dressler, Falko, Series editor, Ferrari, Domenico, Series editor, Gerla, Mario, Series editor, Kobayashi, Hisashi, Series editor, Palazzo, Sergio, Series editor, Sahni, Sartaj, Series editor, Shen, Xuemin (Sherman), Series editor, Stan, Mircea, Series editor, Xiaohua, Jia, Series editor, Zomaya, Albert, Series editor, Coulson, Geoffrey, Series editor, Jain, Rahul, editor, and Kannan, Rajgopal, editor

Published
2012
Full Text
View/download PDF

14. Relay Placement for Two-Connectivity

Author

Calinescu, Gruia, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bestak, Robert, editor, Kencl, Lukas, editor, Li, Li Erran, editor, Widmer, Joerg, editor, and Yin, Hao, editor

Published
2012
Full Text
View/download PDF

15. Register Loading via Linear Programming

Author

Calinescu, Gruia, Li, Minming, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Dehne, Frank, editor, Iacono, John, editor, and Sack, Jörg-Rüdiger, editor

Published
2011
Full Text
View/download PDF

17. Min-Power Strong Connectivity

Author

Calinescu, Gruia, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Serna, Maria, editor, Shaltiel, Ronen, editor, Jansen, Klaus, editor, and Rolim, José, editor

Published
2010
Full Text
View/download PDF

18. Maximum Series-Parallel Subgraph

Author

Călinescu, Gruia, Fernandes, Cristina G., Kaul, Hemanshu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Paul, Christophe, editor, and Habib, Michel, editor

Published
2010
Full Text
View/download PDF

21. Relay Nodes in Wireless Sensor Networks

Author

Călinescu, Gruia, Tongngam, Sutep, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Li, Yingshu, editor, Huynh, Dung T., editor, Das, Sajal K., editor, and Du, Ding-Zhu, editor

Published
2008
Full Text
View/download PDF

22. Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)

Author

Calinescu, Gruia, Chekuri, Chandra, Pál, Martin, Vondrák, Jan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Rangan, C. Pandu, editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fischetti, Matteo, editor, and Williamson, David P., editor

Published
2007
Full Text
View/download PDF

23. Fast Edge Colorings with Fixed Number of Colors to Minimize Imbalance

Author

Calinescu, Gruia, Pelsmajer, Michael J., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Arun-Kumar, S., editor, and Garg, Naveen, editor

Published
2006
Full Text
View/download PDF

24. Reconfigurations in Graphs and Grids

Author

Calinescu, Gruia, Dumitrescu, Adrian, Pach, János, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Correa, José R., editor, Hevia, Alejandro, editor, and Kiwi, Marcos, editor

Published
2006
Full Text
View/download PDF

26. The Polymatroid Steiner Problems

Author

Calinescu, Gruia, Zelikovsky, Alexander, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fleischer, Rudolf, editor, and Trippen, Gerhard, editor

Published
2005
Full Text
View/download PDF

27. Bounding the Payment of Approximate Truthful Mechanisms

Author

Calinescu, Gruia, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fleischer, Rudolf, editor, and Trippen, Gerhard, editor

Published
2005
Full Text
View/download PDF

41. 10188

Author

Eckhoff, Jurgen, Skau, Ivar, and Calinescu, Gruia

Published
1994
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results