Advanced search options

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

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

.
Showing records 1 – 3 of
3 total matches.

▼ Search Limiters

University of Illinois – Urbana-Champaign

1. Gordon, Spencer L. The complexity of continuous local search.

Degree: MS, Computer Science, 2017, University of Illinois – Urbana-Champaign

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

The complexity class CLS was introduced by Daskalakis and Papadimitriou in [9] with the goal of capturing the complexity of some well-known problems in PPAD ∩ PLS that have resisted, in some cases for decades, attempts to put them in polynomial time. No complete problem was known for CLS, and in [9], the problems CONTRACTION, i.e., the problem of finding an approximate fixpoint of a contraction map, and P-LCP, i.e., the problem of solving a P-matrix Linear Complementarity Problem, were identified as prime candidates.
First, we present the first complete problem for CLS, METAMETRICCONTRACTION, which is closely related to the problem CONTRACTION.
Second, we introduce ENDOFPOTENTIALLINE, which captures aspects of PPAD and PLS directly via a monotonic directed path, and show that ENDOFPOTENTIALLINE is in CLS via a two-way reduction to ENDOFMETEREDLINE. The latter was defined in [18] to keep track of how far a vertex is on the PPAD path via a restricted potential function, and was shown to be in CLS.
Third, we reduce P-LCP to ENDOFPOTENTIALLINE, thus making ENDOFPOTENTIALLINE and ENDOFMETEREDLINE at least as likely to be hard for CLS as P-LCP. This result leverages the monotonic structure of Lemke paths for P-LCP problems, making ENDOFPOTENTIALLINE a likely candidate to capture the exact complexity of P-LCP; we note that the structure of Lemke-Howson paths for finding a Nash equilibrium in a two-player game directly motivated the definition of the complexity class PPAD, which ended up capturing this problem’s complexity exactly.
Finally, we reduce the 2-dimensional version of CONTRACTION to ENDOFPOTENTIALLINE, providing further evidence that ENDOFPOTENTIALLINE is CLS-hard.
*Advisors/Committee Members: Mehta, Ruta (advisor).*

Subjects/Keywords: Theoretical computer science; Algorithmic game theory; Computational complexity; Linear complementarity problem; Contraction map

Record Details Similar Records

❌

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

APA (6^{th} Edition):

Gordon, S. L. (2017). The complexity of continuous local search. (Thesis). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/97391

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

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

Gordon, Spencer L. “The complexity of continuous local search.” 2017. Thesis, University of Illinois – Urbana-Champaign. Accessed January 20, 2020. http://hdl.handle.net/2142/97391.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Gordon, Spencer L. “The complexity of continuous local search.” 2017. Web. 20 Jan 2020.

Vancouver:

Gordon SL. The complexity of continuous local search. [Internet] [Thesis]. University of Illinois – Urbana-Champaign; 2017. [cited 2020 Jan 20]. Available from: http://hdl.handle.net/2142/97391.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Gordon SL. The complexity of continuous local search. [Thesis]. University of Illinois – Urbana-Champaign; 2017. Available from: http://hdl.handle.net/2142/97391

Not specified: Masters Thesis or Doctoral Dissertation

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 20, 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. 20 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 20]. 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

3. Jin, Haiming. Incentive mechanism design for mobile crowd sensing systems.

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

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

The recent proliferation of increasingly capable and affordable mobile devices with a plethora of on-board and portable sensors that pervade every corner of the world has given rise to the fast development and wide deployment of mobile crowd sensing (MCS) systems. Nowadays, applications of MCS systems have covered almost every aspect of people's everyday living and working, such as ambient environment monitoring, healthcare, floor plan reconstruction, smart transportation, indoor localization, and many others.
Despite their tremendous benefits, MCS systems pose great new research challenges, of which, this thesis targets one important facet, that is, to effectively incentivize (crowd) workers to achieve maximum participation in MCS systems. Participating in crowd sensing tasks is usually a costly procedure for individual workers. On one hand, it consumes workers' resources, such as computing power, battery, and so forth. On the other hand, a considerable portion of sensing tasks require the submission of workers' sensitive and private information, which causes privacy leakage for participants. Clearly, the power of crowd sensing could not be fully unleashed, unless workers are properly incentivized to participate via satisfactory rewards that effectively compensate their participation costs.
Targeting the above challenge, in this thesis, I present a series of novel incentive mechanisms, which can be utilized to effectively incentivize worker participation in MCS systems. The proposed mechanisms not only incorporate workers' quality of information in order to selectively recruit relatively more reliable workers for sensing, but also preserve workers' privacy so as to prevent workers from being disincentivized by excessive privacy leakage. I demonstrate through rigorous theoretical analyses and extensive simulations that the proposed incentive mechanisms bear many desirable properties theoretically, and have great potential to be practically applied.
*Advisors/Committee Members: Nahrstedt, Klara (advisor), Nahrstedt, Klara (Committee Chair), Srikant, Rayadurgam (committee member), Gunter, Carl A. (committee member), Mehta, Ruta (committee member), Li, Baochun (committee member).*

Subjects/Keywords: Incentive mechanism; Mobile crowd sensing; Quality of information; Privacy preservation

Record Details Similar Records

❌

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

APA (6^{th} Edition):

Jin, H. (2017). Incentive mechanism design for mobile crowd sensing systems. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/97338

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

Jin, Haiming. “Incentive mechanism design for mobile crowd sensing systems.” 2017. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed January 20, 2020. http://hdl.handle.net/2142/97338.

MLA Handbook (7^{th} Edition):

Jin, Haiming. “Incentive mechanism design for mobile crowd sensing systems.” 2017. Web. 20 Jan 2020.

Vancouver:

Jin H. Incentive mechanism design for mobile crowd sensing systems. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2017. [cited 2020 Jan 20]. Available from: http://hdl.handle.net/2142/97338.

Council of Science Editors:

Jin H. Incentive mechanism design for mobile crowd sensing systems. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2017. Available from: http://hdl.handle.net/2142/97338