The Experts below are selected from a list of 121026 Experts worldwide ranked by ideXlab platform

Martin Skutella - One of the best experts on this subject based on the ideXlab platform.

  • Approximation Algorithms for the discrete time cost tradeoff problem
    Mathematics of Operations Research, 1998
    Co-Authors: Martin Skutella
    Abstract:

    Due to its obvious practical relevance, the Time-Cost Tradeoff Problem has attracted the attention of many researchers over the last forty years. While the Linear Time-Cost Tradeoff Problem can be solved in polynomial time, its discrete variant is known to be NP-hard. We present the first Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem. Specifically, given a fixed budget we consider the problem of finding a shortest schedule for a project. We give an Approximation algorithm with performance ratio 3/2 for the class of projects where all feasible durations of activities are either 0, 1, or 2. We extend our result by giving Approximation Algorithms with performance guarantee Olog l, where l is the ratio of the maximum duration of any activity to the minimum nonzero duration of any activity. Finally, we discuss bicriteria Approximation Algorithms which compute schedules for a given deadline or budget such that both project duration and cost are within a constant factor of the duration and cost of an optimum schedule for the given deadline or budget.

  • Approximation Algorithms for the discrete time cost tradeoff problem
    Symposium on Discrete Algorithms, 1997
    Co-Authors: Martin Skutella
    Abstract:

    Due to its obvious practical relevance, the Time-Cost Tradeoff Problem has attracted the attention of many researchers over the last forty years. While the Linear Time-Cost Tradeoff Problem can be solved in polynomial time, its discrete variant is known to be NP-hard. We present the first Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem. Specifically, given a fixed budget we consider the problem of finding a shortest schedule for a project. We give an Approximation algorithm with performance ratio 3 / 2 for the class of projects where all feasible durations of activities are either 0, 1, or 2. We extend our result by giving Approximation Algorithms with performance guarantee O( log l ) , where l is the ratio of the maximum duration of any activity to the minimum nonzero duration of any activity. Finally, we discuss bicriteria Approximation Algorithms which compute schedules for a given deadline or budget such that both project duration and cost are within a constant factor of the duration and cost of an optimum schedule for the given deadline or budget. 1. Introduction. An instance P of the Time-Cost Tradeoff Problem is a project given by a finite set of activities J P A J together with a partial order ( J, ‡ ) on the set of activities. In order to carry out a project, the activities have to be executed in accordance with the precedence constraints given by the partial order: if j‡ k, activity k may not be started before activity j is completed. The activities are indivisible tasks, hence their

Amitabh Sinha - One of the best experts on this subject based on the ideXlab platform.

R Ravi - One of the best experts on this subject based on the ideXlab platform.

  • Approximation Algorithms for low distortion embeddings into low dimensional spaces
    Symposium on Discrete Algorithms, 2005
    Co-Authors: Mihai Bǎdoiu, Anupam Gupta, R Ravi, Kedar Dhamdhere, Yuri Rabinovich, Harald Racke, Anastasios Sidiropoulos
    Abstract:

    We present several Approximation Algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O(√n)-Approximation algorithm for the problem of finding a line embedding of a metric induced by a given unweighted graph, that minimizes the (standard) multiplicative distortion. We give an improved O(n1/3) Approximation for the case of metrics generated by unweighted trees. This is the first result of this type.

  • hedging uncertainty Approximation Algorithms for stochastic optimization problems
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2004
    Co-Authors: R Ravi, Amitabh Sinha
    Abstract:

    We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight Approximation Algorithms for them. Our problems range from the graph-theoretic (shortest path, vertex cover, facility location) to set-theoretic (set cover, bin packing), and contain representatives with different Approximation ratios.The Approximation ratio of the stochastic variant of a typical problem is found to be of the same order of magnitude as its deterministic counterpart. Furthermore, we show that common techniques for designing Approximation Algorithms such as LP rounding, the primal-dual method, and the greedy algorithm, can be adapted to obtain these results.

  • hedging uncertainty Approximation Algorithms for stochastic optimization problems
    Integer Programming and Combinatorial Optimization, 2004
    Co-Authors: R Ravi, Amitabh Sinha
    Abstract:

    We study the design of Approximation Algorithms for stochastic combinatorial optimization problems. We formulate the problems in the framework of two-stage stochastic optimization, and provide nearly tight Approximations. Our problems range from the simple (shortest path, vertex cover, bin packing) to complex (facility location, set cover), and contain representatives with different Approximation ratios.

  • hedging uncertainty Approximation Algorithms for stochastic optimization problems
    Lecture Notes in Computer Science, 2004
    Co-Authors: R Ravi, Amitabh Sinha
    Abstract:

    We study the design of Approximation Algorithms for stochastic combinatorial optimization problems. We formulate the problems in the framework of two-stage stochastic optimization, and provide nearly tight Approximations. Our problems range from the simple (shortest path, vertex cover, bin packing) to complex (facility location, set cover), and contain representatives with different Approximation ratios. The Approximation ratio of the stochastic variant of a typical problem is of the same order of magnitude as its deterministic counterpart. Furthermore, common techniques for designing Approximation Algorithms such as LP rounding, the primal-dual method, and the greedy algorithm, can be carefully adapted to obtain these results.

  • Approximation Algorithms for the covering steiner problem
    Random Structures and Algorithms, 2002
    Co-Authors: Goran Konjevod, R Ravi, Aravind Srinivasan
    Abstract:

    The covering Steiner problem is a generalization of both the k-MST and the group Steiner problems: given an edge-weighted graph, with subsets of vertices called the groups, and a nonnegative integer value (called the requirement) for each group, the problem is to find a minimum-weight tree spanning at least the required number of vertices of every group. When all requirements are equal to 1, this becomes the group Steiner problem, while if there is only one group which contains all vertices of the graph the problem reduces to k-MST with k equal to the requirement of this unique group. We discuss two different (but equivalent) linear relaxations of the problem for the case when the given graph is a tree and construct polylogarithmic Approximation Algorithms based on randomized LP rounding of these relaxations. By using a probabilistic Approximation of general metrics by tree metrics due to Bartal, our Algorithms also solve the covering Steiner problem on general graphs with a further polylogarithmic worsening in the Approximation ratio.

Uri Zwick - One of the best experts on this subject based on the ideXlab platform.

  • a unified framework for obtaining improved Approximation Algorithms for maximum graph bisection problems
    Random Structures and Algorithms, 2002
    Co-Authors: Eran Halperin, Uri Zwick
    Abstract:

    We obtain improved semidefinite programming based Approximation Algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX n/2-BISECTION--partition the vertices of the graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX n/2-VERTEX-COVER--find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX n/2-DENSE-SUBGRAPH--find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAX n/2-UNCUT partition the vertices into two sets of equal size such that the total weight of edges that do not cross the cut is maximized. We also consider the directed versions of these problems, such as MAX n/2-DIRECTED-BISECTION and MAX n/2-DIRECTED-UNCUT. These results can be used to obtain improved Approximation Algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size k and n - k, where k is not necessarily n/2. Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others. All these results may be viewed as extensions of the MAX CUT algorithm of Goemans and Williamson, and the MAX 2-SAT and MAX DI-CUT Algorithms of Feige and Goemans.

  • a unified framework for obtaining improved Approximation Algorithms for maximum graph bisection problems
    Integer Programming and Combinatorial Optimization, 2001
    Co-Authors: Eran Halperin, Uri Zwick
    Abstract:

    We obtain improved semidefinite programming based Approximation Algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX n/2 -BISECTION - partition the vertices of a graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX n/2 -VERTEX-COVER - find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX n/2 -DENSE-SUBGRAPH - find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAX n/2 -UnCUT - partition the vertices into two sets of equal size such that the total weight of edges that do not cross the cut is maximized. We also consider the directed versions of these problems, MAX n/2 -DIRECTED-BISECTION and MAX n/2 -DIRECTED-UnCUT. These results can be used to obtain improved Approximation Algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size k and n - k, where k is not necessarily n/2 . Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others.

  • combinatorial Approximation Algorithms for the maximum directed cut problem
    Symposium on Discrete Algorithms, 2001
    Co-Authors: Eran Halperin, Uri Zwick
    Abstract:

    We describe several combinatorial Algorithms for the maximum directed cut problem. Among our results is a simple linear time 9/20-Approximation algorithm for the problem, and a somewhat slower ½-Approximation algorithm that uses a bipartite matching routine. No better combinatorial Approximation Algorithms are known even for the easier maximum cut problem for undirected graphs. Our Algorithms do not use linear programming, nor semidefinite programming. They are based on the observation that the maximum directed cut problem is equivalent to the problem of finding a maximum independent set in the line graph of the input graph, and that the linear programming relaxation of the problem is equivalent to the problem of finding a maximum fractional independent set of that line graph. The maximum fractional independent set problem can be easily reduced to a bipartite matching problem. As a consequence of this relation, we also get that the maximum directed cut problem for bipartite digraphs can be solved in polynomial time.

Moses Charikar - One of the best experts on this subject based on the ideXlab platform.

  • greedy Approximation Algorithms for finding dense components in a graph
    Lecture Notes in Computer Science, 2000
    Co-Authors: Moses Charikar
    Abstract:

    We study the problem of finding highly connected subgraphs of undirected and directed graphs. For undirected graphs, the notion of density of a subgraph we use is the average degree of the subgraph. For directed graphs, a corresponding notion of density was introduced recently by Kannan and Vinay. This is designed to quantify highly connectedness of substructures in a sparse directed graph such as the web graph. We study the optimization problems of finding subgraphs maximizing these notions of density for undirected and directed graphs. This paper gives simple greedy Approximation Algorithms for these optimization problems. We also answer an open question about the complexity of the optimization problem for directed graphs.

  • Approximation Algorithms for directed steiner problems
    Journal of Algorithms, 1999
    Co-Authors: Moses Charikar, Chandra Chekuri, Toyat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha
    Abstract:

    We give the first nontrivial Approximation Algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in network design and multicast routing. For both problems, the best ratios known before our work were the trivial O(k)-Approximations. For the directed Steiner tree problem, we design a family of Algorithms that achieves an Approximation ratio of i(i?1)k1/i in time O(nik2i) for any fixed i1, where k is the number of terminals. Thus, an O(k?) Approximation ratio can be achieved in polynomial time for any fixed ?0. Setting i=logk, we obtain an O(log2k) Approximation ratio in quasi-polynomial time. For the directed generalized Steiner network problem we give an algorithm that achieves an Approximation ratio of O(k2/3log1/3k), where k is the number of pairs of vertices that are to be connected. Related problems including the group Steiner tree problem, the set TSP problem, and several others in both directed and undirected graphs can be reduced in an Approximation preserving fashion to the directed Steiner tree problem. Thus, we obtain the first nontrivial Approximations to those as well. All these problems are known to be as hard as the Set cover problem to approximate.

  • Approximation Algorithms for directed steiner problems
    Symposium on Discrete Algorithms, 1998
    Co-Authors: Moses Charikar, Chandra Chekuri, Toyat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha
    Abstract:

    We obtain the first non-trivial Approximation Algorithms for the Steiner Tree problem and the Generalized Steiner Tree problem in general directed graphs. Essentially no Approximation Algorithms were known for these problems. For the Directed Steiner Tree problem, we design a family of Algorithms which achieve an Approximation ratio of O(k^\epsilon) in time O(kn^{1/\epsilon}) for any fixed (\epsilon < 0), where k is the number of terminals to be connected. For the Directed Generalized Steiner Tree Problem, we give an algorithm which achieves an Approximation ratio of O(k^{2/3}\log^{1/3} k), where k is the number of pairs to be connected. Related problems including the Group Steiner tree problem, the Node Weighted Steiner tree problem and several others can be reduced in an Approximation preserving fashion to the problems we solve, giving the first non-trivial Approximations to those as well.