Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `+publisher:"University of Illinois – Urbana-Champaign" +contributor:("Gupta, Anupam")`

.
Showing records 1 – 2 of
2 total matches.

▼ Search Limiters

University of Illinois – Urbana-Champaign

1. Korula, Nitish J. Approximation Algorithms for Network Design and Orienteering.

Degree: PhD, 0112, 2010, University of Illinois – Urbana-Champaign

URL: http://hdl.handle.net/2142/16731

This thesis presents approximation algorithms for some NP-Hard combinatorial optimization problems on graphs and networks; in particular, we study problems related to Network Design. Under the widely-believed complexity-theoretic assumption that P is not equal to NP, there are no efficient (i.e., polynomial-time) algorithms that solve these problems exactly. Hence, if one desires efficient algorithms for such problems, it is necessary to consider approximate solutions: An approximation algorithm for an NP-Hard problem is a polynomial time algorithm which, for any instance of the problem, finds a solution whose value is guaranteed to be within a multiplicative factor of the value of an optimal solution to that instance. We attempt to design algorithms for which this factor, referred to as the approximation ratio of the algorithm, is as small as possible.
The field of Network Design comprises a large class of problems that deal with constructing networks of low cost and/or high capacity, routing data through existing networks, and many related issues. In this thesis, we focus chiefly on designing fault-tolerant networks. Two vertices u,v in a network are said to be k-edge-connected if deleting any set of k − 1 edges leaves u and v connected; similarly, they are k-vertex connected if deleting any set of k − 1 other vertices or edges leaves u and v connected. We focus on building networks that are highly connected, meaning that even if a small number of edges and nodes fail, the remaining nodes will still be able to communicate. A brief description of some of our results is given below.
We study the problem of building 2-vertex-connected networks that are large and have low cost. Given an n-node graph with costs on its edges and any integer k, we give an O(log n log k) approximation for the problem of finding a minimum-cost 2-vertex-connected subgraph containing at least k nodes. We also give an algorithm of similar approximation ratio for maximizing the number of nodes in a 2-vertex-connected subgraph subject to a budget constraint on the total cost of its edges. Our algorithms are based on a pruning process that, given a 2-vertex-connected graph, finds a 2-vertex-connected subgraph of any desired size and of density comparable to the input graph, where the density of a graph is the ratio of its cost to the number of vertices it contains. This pruning algorithm is simple and efficient, and is likely to find additional applications.
Recent breakthroughs on vertex-connectivity have made use of algorithms for element-connectivity problems. We develop an algorithm that, given a graph with some vertices marked as terminals, significantly simplifies the graph while preserving the pairwise element-connectivity of all terminals; in fact, the resulting graph is bipartite. We believe that our simplification/reduction algorithm will be a useful tool in many settings. We illustrate its applicability by giving algorithms to find many trees that each span a given terminal set, while being disjoint on edges and non-terminal…
*Advisors/Committee Members: Chekuri, Chandra S. (advisor), Chekuri, Chandra S. (Committee Chair), Erickson, Jeff G. (committee member), Har-Peled, Sariel (committee member), Gupta, Anupam (committee member).*

Subjects/Keywords: Algorithms; Approximation algorithms; Network design; Graph algorithms; Connectivity; Orienteering

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Korula, N. J. (2010). Approximation Algorithms for Network Design and Orienteering. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/16731

Chicago Manual of Style (16^{th} Edition):

Korula, Nitish J. “Approximation Algorithms for Network Design and Orienteering.” 2010. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed January 25, 2020. http://hdl.handle.net/2142/16731.

MLA Handbook (7^{th} Edition):

Korula, Nitish J. “Approximation Algorithms for Network Design and Orienteering.” 2010. Web. 25 Jan 2020.

Vancouver:

Korula NJ. Approximation Algorithms for Network Design and Orienteering. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2010. [cited 2020 Jan 25]. Available from: http://hdl.handle.net/2142/16731.

Council of Science Editors:

Korula NJ. Approximation Algorithms for Network Design and Orienteering. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2010. Available from: http://hdl.handle.net/2142/16731

University of Illinois – Urbana-Champaign

2. Madan, Vivek. On approximability and LP formulations for multicut and feedback set problems.

Degree: PhD, Computer Science, 2018, University of Illinois – Urbana-Champaign

URL: http://hdl.handle.net/2142/102390

Graph cut algorithms are an important tool for solving optimization problems in a variety of areas in computer science. Of particular importance is the min s-t cut problem and an efficient (polynomial time) algorithm for it. Unfortunately, efficient algorithms are not known for several other cut problems. Furthermore, the theory of NP-completeness rules out the existence of efficient algorithms for these problems if the P\neq NP conjecture is true. For this reason, much of the focus has shifted to the design of approximation algorithms. Over the past 30 years significant progress has been made in understanding the approximability of various graph cut problems. In this thesis we further advance our understanding by closing some of the gaps in the known approximability results. Our results comprise of new approximation algorithms as well as new hardness of approximation bounds. For both of these, new linear programming (LP) formulations based on a labeling viewpoint play a crucial role.
One of the problems we consider is a generalization of the min s-t cut problem, known as the multicut problem. In a multicut instance, we are given an undirected or directed weighted supply graph and a set of pairs of vertices which can be encoded as a demand graph. The goal is to remove a minimum weight set of edges from the supply graph such that all the demand pairs are disconnected. We study the effect of the structure of the demand graph on the approximability of multicut. We prove several algorithmic and hardness results which unify previous results and also yield new results. Our algorithmic result generalizes the constant factor approximations known for the undirected and directed multiway cut problems to a much larger class of demand graphs. Our hardness result proves the optimality of the hitting-set LP for directed graphs. In addition to the results on multicut, we also prove results for multiway cut and another special case of multicut, called linear-3-cut. Our results exhibit tight approximability bounds in some cases and improve upon the existing bound in other cases. As a consequence, we also obtain tight approximation results for related problems.
Another part of the thesis is focused on feedback set problems. In a subset feedback edge or vertex set instance, we are given an undirected edge or vertex weighted graph, and a set of terminals. The goal is to find a minimum weight set of edges or vertices which hit all of the cycles that contain some terminal vertex. There is a natural hitting-set LP which has an Ω(log k) integrality gap for k terminals. Constant factor approximation algorithms have been developed using combinatorial techniques. However, the factors are not tight, and the algorithms are sometimes complicated. Since most of the related problems admit optimal approximation algorithms using LP relaxations, lack of good LP relaxations was seen as a fundamental roadblock towards resolving the approximability of these problems. In this thesis we address this by developing new LP relaxations…
*Advisors/Committee Members: Chekuri, Chandra (advisor), Chekuri, Chandra (Committee Chair), Har-Peled, Sariel (committee member), Mehta, Ruta (committee member), Chandrasekaran, Karthekeyan (committee member), Gupta, Anupam (committee member).*

Subjects/Keywords: Approximation; Multicut; Feedback set; Linear programming relaxation; Hardness of approximation; Linear cut; Multiway cut; Subset feedback set; Flow-cut gap

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Madan, V. (2018). On approximability and LP formulations for multicut and feedback set problems. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/102390

Chicago Manual of Style (16^{th} Edition):

Madan, Vivek. “On approximability and LP formulations for multicut and feedback set problems.” 2018. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed January 25, 2020. http://hdl.handle.net/2142/102390.

MLA Handbook (7^{th} Edition):

Madan, Vivek. “On approximability and LP formulations for multicut and feedback set problems.” 2018. Web. 25 Jan 2020.

Vancouver:

Madan V. On approximability and LP formulations for multicut and feedback set problems. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2018. [cited 2020 Jan 25]. Available from: http://hdl.handle.net/2142/102390.

Council of Science Editors:

Madan V. On approximability and LP formulations for multicut and feedback set problems. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2018. Available from: http://hdl.handle.net/2142/102390