You searched for +publisher:"Georgia Tech" +contributor:("Thomas, Robin").
Showing records 1 – 29 of
29 total matches.
No search limiters apply to these results.
Georgia Tech
1.
Asadi Shahmirzadi, Arash.
Minor-minimal non-projective planar graphs with an internal 3-separation.
Degree: PhD, Mathematics, 2012, Georgia Tech
URL: http://hdl.handle.net/1853/45914 
► The property that a graph has an embedding in the projective plane is closed under taking minors. Thus by the well known Graph Minor theorem…
(more)
▼ The property that a graph has an embedding in the projective plane is closed under taking minors. Thus by the well known Graph Minor theorem of Robertson and Seymour, there exists a finite list of minor-minimal graphs, call it L, such that a given graph G is projective planar if and only if G does not contain any graph isomorphic to a member of L as a minor. Glover, Huneke and Wang found 35 graphs in L, and Archdeacon proved that those are all the members of L, but Archdeacon's proof never appeared in any refereed journal. In this thesis we develop a modern approach and technique for finding the list L, independent of previous work.
Our approach is based on conditioning on the connectivity of a member of L. Assume G is a member of L. If G is not 3-connected then the structure of G is well understood. In the case that G is 3-connected, the problem breaks down into two main cases, either G has an internal separation of order three or G is internally 4-connected. In this thesis we find the set of all 3-connected minor minimal non-projective planar graphs with an internal 3-separation. For proving our main result, we use a technique which can be considered as a variation and generalization of the method that Robertson, Seymour and
Thomas used for non-planar extension of planar graphs. Using this technique, besides our main result, we also classify the set of minor minimal obstructions for a-, ac-, abc-planarity for rooted graphs. (A rooted graph (G,a,b,c) is a-planar if there exists a split of the vertex a to a' and a' in G
such that the new graph G' obtained by the split has an embedding
in a disk such that the vertices a', b, a', c are on the
boundary of the disk in the order listed. We define b- and c-planarity analogously. We say that the rooted graph (G,a,b,c) is ab-planar
if it is a-planar or b-planar, and we define abc-planarity analogously.)
Advisors/Committee Members: Thomas, Robin (Committee Chair), Cook, William (Committee Member), Tetali, Prasad (Committee Member), Trotter, William (Committee Member), Yu, Xingxing (Committee Member).
Subjects/Keywords: C-planar; Non-projective planar; Minor-minimal; Algorithms; Graph theory; Graph theory; Geometry, Plane
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Asadi Shahmirzadi, A. (2012). Minor-minimal non-projective planar graphs with an internal 3-separation. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/45914
Chicago Manual of Style (16th Edition):
Asadi Shahmirzadi, Arash. “Minor-minimal non-projective planar graphs with an internal 3-separation.” 2012. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/45914.
MLA Handbook (7th Edition):
Asadi Shahmirzadi, Arash. “Minor-minimal non-projective planar graphs with an internal 3-separation.” 2012. Web. 27 Jan 2021.
Vancouver:
Asadi Shahmirzadi A. Minor-minimal non-projective planar graphs with an internal 3-separation. [Internet] [Doctoral dissertation]. Georgia Tech; 2012. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/45914.
Council of Science Editors:
Asadi Shahmirzadi A. Minor-minimal non-projective planar graphs with an internal 3-separation. [Doctoral Dissertation]. Georgia Tech; 2012. Available from: http://hdl.handle.net/1853/45914
Georgia Tech
2.
Backman, Spencer Christopher Foster.
Combinatorial divisor theory for graphs.
Degree: PhD, Mathematics, 2014, Georgia Tech
URL: http://hdl.handle.net/1853/51908
► Chip-firing is a deceptively simple game played on the vertices of a graph, which was independently discovered in probability theory, poset theory, graph theory, and…
(more)
▼ Chip-firing is a deceptively simple game played on the vertices of a graph, which was independently discovered in probability theory, poset theory, graph theory, and statistical physics. In recent years, chip-firing has been employed in the development of a theory of divisors on graphs analogous to the classical theory for Riemann surfaces. In particular, Baker and Norin were able to use this set up to prove a combinatorial Riemann-Roch formula, whose classical counterpart is one of the cornerstones of modern algebraic geometry. It is now understood that the relationship between divisor theory for graphs and algebraic curves goes beyond pure analogy, and the primary operation for making this connection precise is tropicalization, a certain type of degeneration which allows us to treat graphs as “combinatorial shadows” of curves. The development of this tropical relationship between graphs and algebraic curves has allowed for beautiful applications of chip-firing to both algebraic geometry and number theory. In this thesis we continue the combinatorial development of divisor theory for graphs. In Chapter 1 we give an overview of the history of chip-firing and its connections to algebraic geometry. In Chapter 2 we describe a reinterpretation of chip-firing in the language of partial graph orientations and apply this setup to give a new proof of the Riemann-Roch formula. We introduce and investigate transfinite chip-firing, and chip-firing with respect to open covers in Chapters 3 and 4 respectively. Chapter 5 represents joint work with Arash Asadi, where we investigate Riemann-Roch theory for directed graphs and arithmetical graphs, the latter of which are a special class of balanced vertex weighted graphs arising naturally in arithmetic geometry.
Advisors/Committee Members: Baker, Matthew (advisor), Thomas, Robin (committee member), Yu, Josephine (committee member), Pokutta, Sebastian (committee member), Sergey Norin (committee member).
Subjects/Keywords: Chip-firing; Graph; Tropical curve; Riemann-Roch; Orientation; Divisor theory; Combinatorial analysis; Graph theory; Geometry, Algebraic; Number theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Backman, S. C. F. (2014). Combinatorial divisor theory for graphs. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/51908
Chicago Manual of Style (16th Edition):
Backman, Spencer Christopher Foster. “Combinatorial divisor theory for graphs.” 2014. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/51908.
MLA Handbook (7th Edition):
Backman, Spencer Christopher Foster. “Combinatorial divisor theory for graphs.” 2014. Web. 27 Jan 2021.
Vancouver:
Backman SCF. Combinatorial divisor theory for graphs. [Internet] [Doctoral dissertation]. Georgia Tech; 2014. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/51908.
Council of Science Editors:
Backman SCF. Combinatorial divisor theory for graphs. [Doctoral Dissertation]. Georgia Tech; 2014. Available from: http://hdl.handle.net/1853/51908
Georgia Tech
3.
Whalen, Peter.
Pfaffian orientations, flat embeddings, and Steinberg's conjecture.
Degree: PhD, Mathematics, 2014, Georgia Tech
URL: http://hdl.handle.net/1853/52207
► The first result of this thesis is a partial result in the direction of Steinberg's Conjecture. Steinberg's Conjecture states that any planar graph without cycles…
(more)
▼ The first result of this thesis is a partial result in the direction of Steinberg's Conjecture. Steinberg's Conjecture states that any planar graph without cycles of length four or five is three colorable. Borodin, Glebov, Montassier, and Raspaud showed that planar graphs without cycles of length four, five, or seven are three colorable and Borodin and Glebov showed that planar graphs without five cycles or triangles at distance at most two apart are three colorable. We prove a statement that implies the first of these theorems and is incomparable with the second: that any planar graph with no cycles of length four through six or cycles of length seven with incident triangles distance exactly two apart are three colorable.
The third and fourth chapters of this thesis are concerned with the study of Pfaffian orientations. A theorem proved by William McCuaig and, independently, Neil Robertson, Paul Seymour, and
Robin Thomas provides a good characterization for whether or not a bipartite graph has a Pfaffian orientation as well as a polynomial time algorithm for that problem. We reprove this characterization and provide a new algorithm for this problem. In Chapter 3, we generalize a preliminary result needed to reprove this theorem. Specifically, we show that any internally 4-connected, non-planar bipartite graph contains a subdivision of K3,3 in which each path has odd length. In Chapter 4, we make use of this result to provide a much shorter proof using elementary methods of this characterization.
In the fourth and fifth chapters we investigate flat embeddings. A piecewise-linear embedding of a graph in 3-space is flat if every cycle of the graph bounds a disk disjoint from the rest of the graph. We provide a structural theorem for flat embeddings that indicates how to build them from small pieces in Chapter 5. In Chapter 6, we present a class of flat graphs that are highly non-planar in the sense that, for any fixed k, there are an infinite number of members of the class such that deleting k vertices leaves the graph non-planar.
Advisors/Committee Members: Thomas, Robin (advisor), Yu, Xingxing (committee member), Norin, Sergey (committee member), Trotter, William (committee member), Vazirani, Vijay (committee member).
Subjects/Keywords: Combinatorics; Coloring; Graph theory; Pfaffian orientations; Flat embeddings
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Whalen, P. (2014). Pfaffian orientations, flat embeddings, and Steinberg's conjecture. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/52207
Chicago Manual of Style (16th Edition):
Whalen, Peter. “Pfaffian orientations, flat embeddings, and Steinberg's conjecture.” 2014. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/52207.
MLA Handbook (7th Edition):
Whalen, Peter. “Pfaffian orientations, flat embeddings, and Steinberg's conjecture.” 2014. Web. 27 Jan 2021.
Vancouver:
Whalen P. Pfaffian orientations, flat embeddings, and Steinberg's conjecture. [Internet] [Doctoral dissertation]. Georgia Tech; 2014. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/52207.
Council of Science Editors:
Whalen P. Pfaffian orientations, flat embeddings, and Steinberg's conjecture. [Doctoral Dissertation]. Georgia Tech; 2014. Available from: http://hdl.handle.net/1853/52207
Georgia Tech
4.
Dang, Thanh Ngoc.
Minors of graphs of large path-width.
Degree: PhD, Mathematics, 2018, Georgia Tech
URL: http://hdl.handle.net/1853/59846
► Let P be a graph with a vertex v such that P-v is a forest and let Q be an outerplanar graph. In 1993 Paul…
(more)
▼ Let P be a graph with a vertex v such that P-v is a forest and let Q be an outerplanar graph. In 1993 Paul Seymour asked if every two-connected graph of sufficiently large path-width contains P or Q as a minor.mDefine g(H) as the minimum number for which there exists a positive integer p(H) such that every g(H)-connected H-minor-free graph has path-width at most p(H). Then g(H) = 0 if and only if H is a forest and there is no graph H with g(H) = 1, because path-width of a graph G is the maximum of the path-widths of its connected components. Let A be the graph that consists of a cycle (a
1,a
2,a
3,a
4,a
5,a
6,a
1) and extra edges a
1a3, a
3a5, a
5a1. Let C
3,2 be a graph of 2 disjoint triangles. In 2014 Marshall and Wood conjectured that a graph H does not have K
4, K
2,3, C
3,2 or A as a minor if and only if g(H) <= 2. In this thesis we answer Paul Seymour's question in the affirmative and prove Marshall and Wood's conjecture, as well as extend the result to three-connected and four-connected graphs of large path-width. We introduce ``cascades", our main tool, and prove that in any tree-decomposition with no duplicate bags of bounded width of a graph of big path-width there is an ``injective" cascade of large height. Then we prove that every 2-connected graph of big path-width and bounded tree-width admits a tree-decomposition of bounded width and a cascade with linkages that are minimal. We analyze those minimal linkages and prove that there are essentially only two types of linkage. Then we convert the two types of linkage into the two families of graphs P and Q. In this process we have to choose the ``right'' tree decomposition to deal with special cases like a long cycle. Similar techniques are used for three-connected and four-connected graphs with high path-width.
Advisors/Committee Members: Thomas, Robin (advisor), Pokutta, Sebastian (committee member), Tetali, Prasad (committee member), Trotter, William T. (committee member), Yu, Xingxing (committee member).
Subjects/Keywords: Graph theory; Graph; Minors; Minor; Pathwidth; Path-width; Large
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Dang, T. N. (2018). Minors of graphs of large path-width. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/59846
Chicago Manual of Style (16th Edition):
Dang, Thanh Ngoc. “Minors of graphs of large path-width.” 2018. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/59846.
MLA Handbook (7th Edition):
Dang, Thanh Ngoc. “Minors of graphs of large path-width.” 2018. Web. 27 Jan 2021.
Vancouver:
Dang TN. Minors of graphs of large path-width. [Internet] [Doctoral dissertation]. Georgia Tech; 2018. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/59846.
Council of Science Editors:
Dang TN. Minors of graphs of large path-width. [Doctoral Dissertation]. Georgia Tech; 2018. Available from: http://hdl.handle.net/1853/59846
Georgia Tech
5.
Xie, Shijie.
6-connected graphs are two-three linked.
Degree: PhD, Mathematics, 2019, Georgia Tech
URL: http://hdl.handle.net/1853/62273
► Let G be a graph and a0, a1, a2, b1, and b2 be distinct vertices of G. Motivated by their work on Four Color Theorem,…
(more)
▼ Let G be a graph and a
0, a
1, a
2, b
1, and b
2 be distinct vertices of G. Motivated by their work on Four Color Theorem, Hadwiger's conjecture for K
6, and J\o rgensen's conjecture, Robertson and Seymour asked when does G contain disjoint connected subgraphs G
1, G
2, such that {a
0, a
1, a
2}\subseteq V(G
1) and {b
1, b
2}\subseteq V(G
2). We prove that if G is 6-connected then such G
1,G
2 exist. Joint work with
Robin Thomas and Xingxing Yu.
Advisors/Committee Members: Yu, Xingxing (advisor), Thomas, Robin (committee member), Tetali, Prasad (committee member), Peng, Richard (committee member), Warnke, Lutz (committee member).
Subjects/Keywords: Graph theory; Disjoint paths in graphs; Two-three linked graphs; 6-connected graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Xie, S. (2019). 6-connected graphs are two-three linked. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/62273
Chicago Manual of Style (16th Edition):
Xie, Shijie. “6-connected graphs are two-three linked.” 2019. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/62273.
MLA Handbook (7th Edition):
Xie, Shijie. “6-connected graphs are two-three linked.” 2019. Web. 27 Jan 2021.
Vancouver:
Xie S. 6-connected graphs are two-three linked. [Internet] [Doctoral dissertation]. Georgia Tech; 2019. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/62273.
Council of Science Editors:
Xie S. 6-connected graphs are two-three linked. [Doctoral Dissertation]. Georgia Tech; 2019. Available from: http://hdl.handle.net/1853/62273
6.
Chenette, Nathan Lee.
Symmetric schemes for efficient range and error-tolerant search on encrypted data.
Degree: PhD, Mathematics, 2012, Georgia Tech
URL: http://hdl.handle.net/1853/48976
► Large-scale data management systems rely more and more on cloud storage, where the need for efficient search capabilities clashes with the need for data confidentiality.…
(more)
▼ Large-scale data management systems rely more and more on cloud storage, where the need for efficient search capabilities clashes with the need for data confidentiality. Encryption and efficient accessibility are naturally at odds, as for instance strong encryption necessitates that ciphertexts reveal nothing about underlying data. Searchable encryption is an active field in cryptography studying encryption schemes that provide varying levels of efficiency, functionality, and security, and efficient searchable encryption focuses on schemes enabling sub-linear (in the size of the database) search time. I present the first cryptographic study of efficient searchable symmetric encryption schemes supporting two types of search queries, range queries and error-tolerant queries. The natural solution to accommodate efficient range queries on ciphertexts is to use order-preserving encryption (OPE). I propose a security definition for OPE schemes, construct the first OPE scheme with provable security, and further analyze security by characterizing one-wayness of the scheme. Efficient error-tolerant queries are enabled by efficient fuzzy-searchable encryption (EFSE). For EFSE, I introduce relevant primitives, an optimal security definition and a (somewhat space-inefficient, but in a sense efficient as possible) scheme achieving it, and more efficient schemes that achieve a weaker, but practical, security notion. In all cases, I introduce new appropriate security definitions, construct novel schemes, and prove those schemes secure under standard assumptions. The goal of this line of research is to provide constructions and provable security analysis that should help practitioners decide whether OPE or FSE provides a suitable efficiency-security-functionality tradeoff for a given application.
Advisors/Committee Members: Boldyreva, Alexandra (advisor), Ahamad, Mustaque (committee member), Lipton, Richard (committee member), Peikert, Chris (committee member), Thomas, Robin (committee member).
Subjects/Keywords: Fuzzy searchable encryption; Symmetric encryption; Searchable encryption; Hypergeometric distribution; Database security; Order-preserving encryption; Data encryption (Computer science); Cloud computing; Data protection; Database searching
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Chenette, N. L. (2012). Symmetric schemes for efficient range and error-tolerant search on encrypted data. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/48976
Chicago Manual of Style (16th Edition):
Chenette, Nathan Lee. “Symmetric schemes for efficient range and error-tolerant search on encrypted data.” 2012. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/48976.
MLA Handbook (7th Edition):
Chenette, Nathan Lee. “Symmetric schemes for efficient range and error-tolerant search on encrypted data.” 2012. Web. 27 Jan 2021.
Vancouver:
Chenette NL. Symmetric schemes for efficient range and error-tolerant search on encrypted data. [Internet] [Doctoral dissertation]. Georgia Tech; 2012. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/48976.
Council of Science Editors:
Chenette NL. Symmetric schemes for efficient range and error-tolerant search on encrypted data. [Doctoral Dissertation]. Georgia Tech; 2012. Available from: http://hdl.handle.net/1853/48976
7.
Ye, Tianjun.
Forbidden subgraphs and 3-colorability.
Degree: PhD, Mathematics, 2012, Georgia Tech
URL: http://hdl.handle.net/1853/48986
► Classical vertex coloring problems ask for the minimum number of colors needed to color the vertices of a graph, such that adjacent vertices use different…
(more)
▼ Classical vertex coloring problems ask for the minimum number of colors needed to color the vertices of a graph, such that adjacent vertices use different colors. Vertex coloring does have quite a few practical applications in communication theory, industry engineering and computer science. Such examples can be found in the book of Hansen and Marcotte. Deciding whether a graph is 3-colorable or not is a well-known NP-complete problem, even for triangle-free graphs. Intuitively, large girth may help reduce the chromatic number. However, in 1959, Erdos used the probabilitic method to prove that for any two positive integers g and k, there exist graphs of girth at least g and chromatic number at least k. Thus, restricting girth alone does not help bound the chromatic number. However, if we forbid certain tree structure in addition to girth restriction, then it is possible to bound the chromatic number. Randerath determined several such tree structures, and conjectured that if a graph is fork-free and triangle-free, then it is 3-colorable, where a fork is a star K1,4 with two branches subdivided once. The main result of this thesis is that Randerath’s conjecture is true for graphs with odd girth at least 7. We also give a proof that Randerath’s conjecture holds for graphs with maximum degree 4.
Advisors/Committee Members: Yu, Xingxing (advisor), Chen, Guantao (committee member), Tetali, Prasad (committee member), Thomas, Robin (committee member), Trotter, William (committee member).
Subjects/Keywords: Forbidden subgraphs; 3-colorability; Graph theory; Graph coloring
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Ye, T. (2012). Forbidden subgraphs and 3-colorability. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/48986
Chicago Manual of Style (16th Edition):
Ye, Tianjun. “Forbidden subgraphs and 3-colorability.” 2012. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/48986.
MLA Handbook (7th Edition):
Ye, Tianjun. “Forbidden subgraphs and 3-colorability.” 2012. Web. 27 Jan 2021.
Vancouver:
Ye T. Forbidden subgraphs and 3-colorability. [Internet] [Doctoral dissertation]. Georgia Tech; 2012. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/48986.
Council of Science Editors:
Ye T. Forbidden subgraphs and 3-colorability. [Doctoral Dissertation]. Georgia Tech; 2012. Available from: http://hdl.handle.net/1853/48986
8.
Liu, Chun-Hung.
Graph structures and well-quasi-ordering.
Degree: PhD, Mathematics, 2014, Georgia Tech
URL: http://hdl.handle.net/1853/52262
► Robertson and Seymour proved that graphs are well-quasi-ordered by the minor relation. In other words, given infinitely many graphs, one graph contains another as a…
(more)
▼ Robertson and Seymour proved that graphs are well-quasi-ordered by the minor relation. In other words, given infinitely many graphs, one graph contains another as a minor. An application of this theorem is that every property that is closed under deleting vertices, edges, and contracting edges can be characterized by finitely many graphs, and hence can be decided in polynomial time.
In this thesis we are concerned with the topological minor relation. We say that a graph G contains another graph H as a topological minor if H can be obtained from a subgraph of G by repeatedly deleting a vertex of degree two and adding an edge incident with the neighbors of the deleted vertex. Unlike the relation of minor, the topological minor relation does not well-quasi-order graphs in general. However, Robertson conjectured in the late 1980's that for every positive integer k, the topological minor relation well-quasi-orders graphs that do not contain a topological minor isomorphic to the path of length k with each edge duplicated.
This thesis consists of two main results. The first one is a structure theorem for excluding a fixed graph as a topological minor, which is analogous to a cornerstone result of Robertson and Seymour, who gave such a structure for graphs that exclude a fixed minor. Results for topological minors were previously obtained by Grohe and Marx and by Dvorak, but we push one of the bounds in their theorems to the optimal value. This improvement is needed for the next theorem.
The second main result is a proof of Robertson's conjecture. As a corollary, properties on certain graphs closed under deleting vertices, edges, and "suppressing" vertices of degree two can be characterized by finitely many graphs, and hence can be decided in polynomial time.
Advisors/Committee Members: Thomas, Robin (advisor), Baker, Matthew (committee member), Tovey, Craig A. (committee member), Trotter, William (committee member), Yu, Xingxing (committee member).
Subjects/Keywords: Graph; Topological minor; Well-quasi-ordering
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Liu, C. (2014). Graph structures and well-quasi-ordering. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/52262
Chicago Manual of Style (16th Edition):
Liu, Chun-Hung. “Graph structures and well-quasi-ordering.” 2014. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/52262.
MLA Handbook (7th Edition):
Liu, Chun-Hung. “Graph structures and well-quasi-ordering.” 2014. Web. 27 Jan 2021.
Vancouver:
Liu C. Graph structures and well-quasi-ordering. [Internet] [Doctoral dissertation]. Georgia Tech; 2014. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/52262.
Council of Science Editors:
Liu C. Graph structures and well-quasi-ordering. [Doctoral Dissertation]. Georgia Tech; 2014. Available from: http://hdl.handle.net/1853/52262
9.
Goel, Gagan.
Algorithms for budgeted auctions and multi-agent covering problems.
Degree: PhD, Computing, 2009, Georgia Tech
URL: http://hdl.handle.net/1853/29679
► In this thesis, we do an algorithmic study of optimization problems in budgeted auctions, and some well known covering problems in the multi-agent setting. We…
(more)
▼ In this thesis, we do an algorithmic study of
optimization problems in budgeted auctions, and some well known
covering problems in the multi-agent setting. We give new results
for the design of approximation algorithms, online algorithms and
hardness of approximation for these problems. Along the way we give
new insights for many other related problems.
Budgeted Auction. We study the following allocation problem which
arises in budgeted auctions (such as advertisement auctions run by
Google, Microsoft, Yahoo! etc.) : Given a set of m indivisible
items and n agents; agent i is willing to pay b[subscript ij] for item
j and has an overall budget of B[subscript i] (i.e. the maximum total
amount he is willing to pay). The goal is to allocate items to the
agents so as to maximize the total revenue obtained.
We study the computation complexity of the above allocation problem,
and give improved results for the approximation and the hardness of
approximation. We also study the above allocation problem in an
online setting. Online version of the problem has motivation in the
sponsored search auctions which are run by search engines. Lastly,
we propose a new bidding language for the budgeted auctions:
decreasing bid curves with budget constraints. We make a case for
why this language is better both for the sellers and for the buyers.
Multi-agent Covering Problems. To motivate this class of problems,
consider the network design problem of constructing a spanning tree
of a graph, assuming there are many agents willing to construct
different parts of the tree. The cost of each agent for constructing
a particular set of edges could be a complex function. For instance,
some agents might provide discounts depending on how many edges they
construct. The algorithmic question that one would be interested in
is: Can we find a spanning tree of minimum cost in polynomial time
in these complex settings? Note that such an algorithm will have to
find a spanning tree, and partition its edges among the agents.
Above are the type of questions that we are trying to answer for
various combinatorial problems. We look at the case when the agents'
cost functions are submodular. These functions form a rich class and
capture the natural properties of economies of scale or the law of
diminishing returns.We study the following fundamental problems in
this setting- Vertex Cover, Spanning Tree, Perfect Matching,
Reverse Auctions. We look at both the single agent and the
multi-agent case, and study the approximability of each of these
problems.
Advisors/Committee Members: Vazirani, Vijay (Committee Chair), Kalai, Adam (Committee Member), Mihail, Milena (Committee Member), Tetali, Prasad (Committee Member), Thomas, Robin (Committee Member).
Subjects/Keywords: Game theory; Covering problems; Budgeted auctions; Approximation algorithms; Algorithms; Auctions; Mathematical optimization; Algorithms
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Goel, G. (2009). Algorithms for budgeted auctions and multi-agent covering problems. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/29679
Chicago Manual of Style (16th Edition):
Goel, Gagan. “Algorithms for budgeted auctions and multi-agent covering problems.” 2009. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/29679.
MLA Handbook (7th Edition):
Goel, Gagan. “Algorithms for budgeted auctions and multi-agent covering problems.” 2009. Web. 27 Jan 2021.
Vancouver:
Goel G. Algorithms for budgeted auctions and multi-agent covering problems. [Internet] [Doctoral dissertation]. Georgia Tech; 2009. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/29679.
Council of Science Editors:
Goel G. Algorithms for budgeted auctions and multi-agent covering problems. [Doctoral Dissertation]. Georgia Tech; 2009. Available from: http://hdl.handle.net/1853/29679
10.
Saket, Rishi.
Intractability results for problems in computational learning and approximation.
Degree: PhD, Computing, 2009, Georgia Tech
URL: http://hdl.handle.net/1853/29681
► In this thesis we prove intractability results for well studied problems in computational learning and approximation. Let ε , mu > 0 be arbitrarily small…
(more)
▼ In this thesis we prove intractability results for well studied problems in computational learning and approximation. Let ε , mu > 0 be arbitrarily small constants and t be an arbitrary constant positive integer. We show an almost optimal hardness factor of d[superscript{1-ε}] for computing an equivalent DNF expression with minimum terms for a boolean function on d variables, given its truth table. In the study of weak learnability, we prove an optimal 1/2 + ε inapproximability for the accuracy of learning an intersection of two halfspaces with an intersection of t halfspaces. Further, we study the learnability of small DNF formulas, and prove optimal 1/2 + ε inapproximability for the accuracy of learning (i) a two term DNF by a t term DNF, and (ii) an AND under adversarial mu-noise by a t-CNF. In addition, we show a 1 - 2[superscript{-d}] + ε inapproximability for accurately learning parities (over GF(2)), under adversarial mu-noise, by degree d polynomials, where d is a constant positive integer.
We also provide negative answers to the possibility of stronger semi-definite programming (SDP) relaxations yielding much better approximations for graph partitioning problems such as Maximum Cut and Sparsest Cut by constructing integrality gap examples for them. For Maximum Cut and Sparsest Cut we construct examples – with gaps alpha[superscript{-1}] - ε (alpha is the Goemans-Williamson constant) and Omega((logloglog n)[superscript{1/13}]) respectively – for the standard SDP relaxations augmented with O((logloglog n)[superscript{1/6}]) rounds of Sherali-Adams constraints. The construction for Sparsest Cut also implies that an n-point negative type metric may incur a distortion of Omega((logloglog n)[superscript{1/ 13}]) to embed into ell_1 even if the induced submetric on every subset of O((logloglog n)[superscript{1/6}]) points is isometric to ell_1. We also construct an integrality gap of Omega(loglog n) for the SDP relaxation for Uniform Sparsest Cut problem augmented with triangle inequalities, disproving a well known conjecture of Arora, Rao and Vazirani.
Advisors/Committee Members: Khot, Subhash (Committee Chair), Tetali, Prasad (Committee Member), Thomas, Robin (Committee Member), Vempala, Santosh (Committee Member), Vigoda, Eric (Committee Member).
Subjects/Keywords: Integrality gaps; Approximation; Hardness; Learning; Combinatorial optimization; Computational learning theory; Machine learning
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Saket, R. (2009). Intractability results for problems in computational learning and approximation. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/29681
Chicago Manual of Style (16th Edition):
Saket, Rishi. “Intractability results for problems in computational learning and approximation.” 2009. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/29681.
MLA Handbook (7th Edition):
Saket, Rishi. “Intractability results for problems in computational learning and approximation.” 2009. Web. 27 Jan 2021.
Vancouver:
Saket R. Intractability results for problems in computational learning and approximation. [Internet] [Doctoral dissertation]. Georgia Tech; 2009. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/29681.
Council of Science Editors:
Saket R. Intractability results for problems in computational learning and approximation. [Doctoral Dissertation]. Georgia Tech; 2009. Available from: http://hdl.handle.net/1853/29681
11.
He, Dawei.
Special TK5 in graphs containing K4-.
Degree: PhD, Mathematics, 2017, Georgia Tech
URL: http://hdl.handle.net/1853/58301
► Given a graph K, TK is used to denote a subdivision of K, which is a graph obtained from K by substituting some edges for…
(more)
▼ Given a graph K, TK is used to denote a subdivision of K, which is a graph
obtained from K by substituting some edges for paths. The well-known Kelmans-Seymour conjecture states that every nonplanar 5-connected graph contains TK5 . Ma and Yu proved the conjecture for graphs containing K4-. In this dissertation, we
strengthen their result in two ways. The results will be useful for completely resolving
the Kelmans-Seymour conjecture. Let G be a 5-connected nonplanar graph and let x1, x2, y1, y2 in V(G) be distinct, such that G[{x1, x2, y1, y2}] is isomorphic to K4- and y1y2 is not in E(G). We show that one of the following holds: G - y2 contains K4-, or G contains a TK5 in which y2 is not a branch vertex, or G has a special 5-separation, or for any distinct w1, w2, w3 in N(y2) - {x1, x2}, G - {y2v : v not in {x1, x2, w1, w2, w3}} contains TK5. We show that one of the following holds: G - x1 contains K4-, or G contains a TK5 in which x1 is not a branch vertex, or G contains a K4- in which x1 is of degree 2, or {x2, y1, y2} may be chosen so that for any distinct z0, z1 in N(x1) - {x2, y1, y2}, G - {x1v : v not in {z0, z1, x2, y1, y2}} contains TK5.
Advisors/Committee Members: Yu, Xingxing (advisor), Thomas, Robin (committee member), Trotter, William (committee member), Blekhermann, Greg (committee member), Li, Geoffrey Ye (committee member).
Subjects/Keywords: Kelmans-Seymour conjecture; Subdivision of K5; K4-; Branch vertex
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
He, D. (2017). Special TK5 in graphs containing K4-. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/58301
Chicago Manual of Style (16th Edition):
He, Dawei. “Special TK5 in graphs containing K4-.” 2017. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/58301.
MLA Handbook (7th Edition):
He, Dawei. “Special TK5 in graphs containing K4-.” 2017. Web. 27 Jan 2021.
Vancouver:
He D. Special TK5 in graphs containing K4-. [Internet] [Doctoral dissertation]. Georgia Tech; 2017. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/58301.
Council of Science Editors:
He D. Special TK5 in graphs containing K4-. [Doctoral Dissertation]. Georgia Tech; 2017. Available from: http://hdl.handle.net/1853/58301
12.
Mai, Tung.
Distributive lattices, stable matchings, and robust solutions.
Degree: PhD, Computer Science, 2018, Georgia Tech
URL: http://hdl.handle.net/1853/60238
► The stable matching problem, first presented by mathematical economists Gale and Shapley, has been studied extensively since its introduction. As a result, a remarkably rich…
(more)
▼ The stable matching problem, first presented by mathematical economists Gale and Shapley, has been studied extensively since its introduction. As a result, a remarkably rich literature on the problem has accumulated in both theory and practice. In this thesis we further extend our understanding on several algorithmic and structural aspects of stable matching. We summarize the main contributions of the thesis as follows: generalizing stable matching to maximum weight stable matching; finding stable matchings that are robust to shifts; generalizing Birkhoff's Theorem, and providing an application to robust stable matching.
Advisors/Committee Members: Vazirani, Vijay (advisor), Garg, Jugal (committee member), Mihail, Milena (committee member), Singh, Mohit (committee member), Thomas, Robin (committee member).
Subjects/Keywords: Distributive lattice; Stable matching
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Mai, T. (2018). Distributive lattices, stable matchings, and robust solutions. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/60238
Chicago Manual of Style (16th Edition):
Mai, Tung. “Distributive lattices, stable matchings, and robust solutions.” 2018. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/60238.
MLA Handbook (7th Edition):
Mai, Tung. “Distributive lattices, stable matchings, and robust solutions.” 2018. Web. 27 Jan 2021.
Vancouver:
Mai T. Distributive lattices, stable matchings, and robust solutions. [Internet] [Doctoral dissertation]. Georgia Tech; 2018. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/60238.
Council of Science Editors:
Mai T. Distributive lattices, stable matchings, and robust solutions. [Doctoral Dissertation]. Georgia Tech; 2018. Available from: http://hdl.handle.net/1853/60238
13.
Wang, Yan.
Subdivisions of complete graphs.
Degree: PhD, Mathematics, 2017, Georgia Tech
URL: http://hdl.handle.net/1853/58633
► A subdivision of a graph G, also known as a topological G and denoted by TG, is a graph obtained from G by replacing certain…
(more)
▼ A subdivision of a graph G, also known as a topological G and denoted by TG, is a graph obtained from G by replacing certain edges of G with internally vertex-disjoint paths. This dissertation studies a problem in structural graph theory regarding subdivisions of a complete graph in graphs. In this dissertation, we focus on TK
5, or subdivisions of K
5. A well known theorem of Kuratowski in 1932 states that a graph is planar if, and only if, it does not contain a subdivision of K
5 or K
3,3. Wagner proved in 1937 that if a graph other than K
5 does not contain any subdivision of K
3,3 then it is planar or it admits a cut of size at most 2. Kelmans and, independently, Seymour conjectured in the 1970s that if a graph does not contain any subdivision of K
5 then it is planar or it admits a cut of size at most 4. In this dissertation, we give a proof of the Kelmans-Seymour conjecture.
Advisors/Committee Members: Yu, Xingxing (advisor), Peng, Richard (committee member), Tetali, Prasad (committee member), Thomas, Robin (committee member), Warnke, Lutz (committee member).
Subjects/Keywords: K5-subdivision; Independent paths; Separation; Connectivity; Discharging; Contraction
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Wang, Y. (2017). Subdivisions of complete graphs. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/58633
Chicago Manual of Style (16th Edition):
Wang, Yan. “Subdivisions of complete graphs.” 2017. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/58633.
MLA Handbook (7th Edition):
Wang, Yan. “Subdivisions of complete graphs.” 2017. Web. 27 Jan 2021.
Vancouver:
Wang Y. Subdivisions of complete graphs. [Internet] [Doctoral dissertation]. Georgia Tech; 2017. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/58633.
Council of Science Editors:
Wang Y. Subdivisions of complete graphs. [Doctoral Dissertation]. Georgia Tech; 2017. Available from: http://hdl.handle.net/1853/58633
14.
Ma, Jie.
Judicious partitions of graphs and hypergraphs.
Degree: PhD, Mathematics, 2011, Georgia Tech
URL: http://hdl.handle.net/1853/41064
► Classical partitioning problems, like the Max-Cut problem, ask for partitions that optimize one quantity, which are important to such fields as VLSI design, combinatorial optimization,…
(more)
▼ Classical partitioning problems, like the Max-Cut problem, ask for partitions that optimize one quantity, which are important to such fields as VLSI design, combinatorial optimization, and computer science. Judicious partitioning problems on graphs or hypergraphs ask for partitions that optimize several quantities simultaneously. In this dissertation, we work on judicious partitions of graphs and hypergraphs, and solve or asymptotically solve several open problems of Bollobas and Scott on judicious partitions, using the probabilistic method and extremal techniques.
Advisors/Committee Members: Yu, Xingxing (Committee Chair), Shapira, Asaf (Committee Member), Tetali, Prasad (Committee Member), Thomas, Robin (Committee Member), Vigoda, Eric (Committee Member).
Subjects/Keywords: Judicious partition; Azuma-Hoeffding inequality; Hypergraphs; Graph theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Ma, J. (2011). Judicious partitions of graphs and hypergraphs. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/41064
Chicago Manual of Style (16th Edition):
Ma, Jie. “Judicious partitions of graphs and hypergraphs.” 2011. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/41064.
MLA Handbook (7th Edition):
Ma, Jie. “Judicious partitions of graphs and hypergraphs.” 2011. Web. 27 Jan 2021.
Vancouver:
Ma J. Judicious partitions of graphs and hypergraphs. [Internet] [Doctoral dissertation]. Georgia Tech; 2011. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/41064.
Council of Science Editors:
Ma J. Judicious partitions of graphs and hypergraphs. [Doctoral Dissertation]. Georgia Tech; 2011. Available from: http://hdl.handle.net/1853/41064
15.
Hoyer, Alexander.
On the independent spanning tree conjectures and related problems.
Degree: PhD, Mathematics, 2019, Georgia Tech
URL: http://hdl.handle.net/1853/61777
► We say that trees with common root are (edge-)independent if, for any vertex in their intersection, the paths to the root induced by each tree…
(more)
▼ We say that trees with common root are (edge-)independent if, for any vertex in their intersection, the paths to the root induced by each tree are internally (edge-)disjoint. The relationship between graph (edge-)connectivity and the existence of (edge-)independent spanning trees is explored. The (Edge-)Independent Spanning Tree Conjecture states that every k-(edge-)connected graph has k-(edge-)independent spanning trees with arbitrary root. We prove the case k = 4 of the Edge-Independent Spanning Tree Conjecture using a graph decomposition similar to an ear decomposition, and give polynomial-time algorithms to construct the decomposition and the trees. We provide alternate geometric proofs for the cases k = 3 of both the Independent Spanning Tree Conjecture and Edge-Independent Spanning Tree Conjecture by
embedding the vertices or edges in a 2-simplex, and conjecture higher-dimension generalizations. We provide a partial result towards a generalization of the Independent Spanning Tree Conjecture, in which local connectivity between the root and a vertex set S implies the existence of trees whose independence properties hold only in S. Finally, we prove and generalize a theorem of Györi and Lovász on partitioning a k-connected graph, and give polynomial-time algorithms for the cases k = 2, 3, 4 using the graph decompositions used to prove the corresponding cases of the Independent Spanning Tree Conjecture.
Advisors/Committee Members: Thomas, Robin (advisor), Tetali, Prasad (committee member), Warnke, Lutz (committee member), Yu, Xingxing (committee member), Vempala, Santosh (committee member).
Subjects/Keywords: Graph theory; Structural graph theory; Independent spanning tree conjecture; Edge-independent spanning tree conjecture; Connectivity; Edge-connectivity; Independent spanning trees; Edge-independent spanning trees; Ear decomposition; Chain decomposition; Graph decomposition; Györi-Lovász theorem
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Hoyer, A. (2019). On the independent spanning tree conjectures and related problems. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/61777
Chicago Manual of Style (16th Edition):
Hoyer, Alexander. “On the independent spanning tree conjectures and related problems.” 2019. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/61777.
MLA Handbook (7th Edition):
Hoyer, Alexander. “On the independent spanning tree conjectures and related problems.” 2019. Web. 27 Jan 2021.
Vancouver:
Hoyer A. On the independent spanning tree conjectures and related problems. [Internet] [Doctoral dissertation]. Georgia Tech; 2019. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/61777.
Council of Science Editors:
Hoyer A. On the independent spanning tree conjectures and related problems. [Doctoral Dissertation]. Georgia Tech; 2019. Available from: http://hdl.handle.net/1853/61777
16.
Postle, Luke Jamison.
5-list-coloring graphs on surfaces.
Degree: PhD, Mathematics, 2012, Georgia Tech
URL: http://hdl.handle.net/1853/45807
► Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. This thesis…
(more)
▼ Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. This thesis develops new techniques to prove general theorems for 5-list-coloring graphs embedded in a fixed surface. Indeed, a general paradigm is established which improves a number of previous results while resolving several open conjectures. In addition, the proofs are almost entirely self-contained.
In what follows, let S be a fixed surface, G be a graph embedded in S and L a list assignment such that, for every vertex v of G, L(v) has size at least five. First, the thesis provides an independent proof of a theorem of DeVos, Kawarabayashi and Mohar that says if G has large edge-width, then G is 5-list-colorable. Moreover, the bound on the edge-width is improved from exponential to logarithmic in the Euler genus of S, which is best possible up to a multiplicative constant. Second, the thesis proves that there exist only finitely many 6-list-critical graphs embeddable in S, solving a conjecture of Thomassen from 1994. Indeed, it is shown that the number of vertices in a 6-list-critical graph is at most linear in genus, which is best possible up to a multiplicative constant. As a corollary, there exists a linear-time algorithm for deciding 5-list-colorability of graphs embeddable in S.
Furthermore, we prove that the number of L-colorings of an L-colorable graph embedded in S is exponential in the number of vertices of G, with a constant depending only on the Euler genus g of S. This resolves yet another conjecture of Thomassen from 2007. The thesis also proves that if X is a subset of the vertices of G that are pairwise distance Omega(log g) apart and the edge-width of G is Omega(log g), then any L-coloring of X extends to an L-coloring of G. For planar graphs, this was conjectured by Albertson and recently proved by Dvorak, Lidicky, Mohar, and Postle. For regular coloring, this was proved by Albertson and Hutchinson. Other related generalizations are examined.
Advisors/Committee Members: Thomas, Robin (Committee Chair), Cook, William (Committee Member), Dvorak, Zdenek (Committee Member), Trotter, William T. (Committee Member), Yu, Xingxing (Committee Member).
Subjects/Keywords: Graph coloring; List-coloring; Choosability; Graph theory; Graph coloring
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Postle, L. J. (2012). 5-list-coloring graphs on surfaces. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/45807
Chicago Manual of Style (16th Edition):
Postle, Luke Jamison. “5-list-coloring graphs on surfaces.” 2012. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/45807.
MLA Handbook (7th Edition):
Postle, Luke Jamison. “5-list-coloring graphs on surfaces.” 2012. Web. 27 Jan 2021.
Vancouver:
Postle LJ. 5-list-coloring graphs on surfaces. [Internet] [Doctoral dissertation]. Georgia Tech; 2012. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/45807.
Council of Science Editors:
Postle LJ. 5-list-coloring graphs on surfaces. [Doctoral Dissertation]. Georgia Tech; 2012. Available from: http://hdl.handle.net/1853/45807
17.
Streib, Noah Sametz.
Planar and hamiltonian cover graphs.
Degree: PhD, Mathematics, 2011, Georgia Tech
URL: http://hdl.handle.net/1853/43744
► This dissertation has two principal components: the dimension of posets with planar cover graphs, and the cartesian product of posets whose cover graphs have hamiltonian…
(more)
▼ This dissertation has two principal components: the dimension of posets with planar cover graphs, and the cartesian product of posets whose cover graphs have hamiltonian cycles that parse into symmetric chains. Posets of height two can have arbitrarily large dimension. In 1981, Kelly provided an infinite sequence of planar posets that shows that the dimension of planar posets can also be arbitrarily large. However, the height of the posets in this sequence increases with the dimension. In 2009, Felsner, Li, and Trotter conjectured that for each integer h at least 2, there exists a least positive integer c(h) so that if P is a poset with a planar cover graph (the class of posets with planar cover graphs includes the class of planar posets) and the height of P is h, then the dimension of P is at most c(h). In the first principal component of this dissertation we prove this conjecture. We also give the best known lower bound for c(h), noting that this lower bound is far from the upper bound. In the second principal component, we consider posets with the Hamiltonian Cycle – Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a hamiltonian cycle which parses into w symmetric chains. This definition is motivated by a proof of Sperner's theorem that uses symmetric chains, and was intended as a possible method of attack on the Middle Two Levels Conjecture. We show that the subset lattices have the HC-SCP property by showing that the class of posets with the strong HC-SCP property, a slight strengthening of the HC-SCP property, is closed under cartesian product with a two-element chain. Furthermore, we show that the cartesian product of any two posets from this strong class has the (weak) HC-SCP property.
Advisors/Committee Members: Trotter, William T. (Committee Chair), Duffus, Dwight (Committee Member), Sokol, Joel (Committee Member), Tetali, Prasad (Committee Member), Thomas, Robin (Committee Member).
Subjects/Keywords: Symmetric chains; Hamiltonian cycles; Cover graphs; Height; Planarity; Dimension; Posets; Partially ordered sets; Hamiltonian graph theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Streib, N. S. (2011). Planar and hamiltonian cover graphs. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/43744
Chicago Manual of Style (16th Edition):
Streib, Noah Sametz. “Planar and hamiltonian cover graphs.” 2011. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/43744.
MLA Handbook (7th Edition):
Streib, Noah Sametz. “Planar and hamiltonian cover graphs.” 2011. Web. 27 Jan 2021.
Vancouver:
Streib NS. Planar and hamiltonian cover graphs. [Internet] [Doctoral dissertation]. Georgia Tech; 2011. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/43744.
Council of Science Editors:
Streib NS. Planar and hamiltonian cover graphs. [Doctoral Dissertation]. Georgia Tech; 2011. Available from: http://hdl.handle.net/1853/43744
18.
Biro, Csaba.
Problems and results in partially ordered sets, graphs and geometry.
Degree: PhD, Mathematics, 2008, Georgia Tech
URL: http://hdl.handle.net/1853/24719
► The thesis consist of three independent parts. In the first part, we investigate the height sequence of an element of a partially ordered set. Let…
(more)
▼ The thesis consist of three independent parts. In the first part, we investigate the height sequence of an element of a partially ordered set. Let x be an element of the partially ordered set P. Then h
i(x) is the number of linear extensions of P in which x is in the ith lowest position. The sequence {h
i(x)} is called the height sequence of x in P. Stanley proved in 1981 that the height sequence is log-concave, but no combinatorial proof has been found, and Stanley's proof does not reveal anything about the deeper structure of the height sequence. In this part of the thesis, we provide a combinatorial proof of a special case of Stanley's theorem. The proof of the inequality uses the Ahlswede – Daykin Four Functions Theorem.
In the second part, we study two classes of segment orders introduced by Shahrokhi. Both classes are natural generalizations of interval containment orders and interval orders. We prove several properties of the classes, and inspired by the observation, that the classes seem to be very similar, we attempt to find out if they actually contain the same partially ordered sets. We prove that the question is equivalent to a stretchability question involving certain sets of pseudoline arrangements. We also prove several facts about continuous universal functions that would transfer segment orders of the first kind into segments orders of the second kind.
In the third part, we consider the lattice whose elements are the subsets of {1,2,ldots,n}. Trotter and Felsner asked whether this subset lattice always contains a monotone Hamiltonian path. We make progress toward answering this question by constructing a path for all n that satisfies the monotone properties and covers every set of size at most 3. This portion of thesis represents joint work with David M.~Howard.
Advisors/Committee Members: Trotter, William T. (Committee Chair), Duke, Richard A. (Committee Member), Randall, Dana (Committee Member), Thomas, Robin (Committee Member), Yu, Xingxing (Committee Member).
Subjects/Keywords: Geometric containment order; Correlation; Boolean lattice; Partially ordered sets; Combinatorial geometry; Lattice theory; Monotonic functions; Set theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Biro, C. (2008). Problems and results in partially ordered sets, graphs and geometry. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/24719
Chicago Manual of Style (16th Edition):
Biro, Csaba. “Problems and results in partially ordered sets, graphs and geometry.” 2008. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/24719.
MLA Handbook (7th Edition):
Biro, Csaba. “Problems and results in partially ordered sets, graphs and geometry.” 2008. Web. 27 Jan 2021.
Vancouver:
Biro C. Problems and results in partially ordered sets, graphs and geometry. [Internet] [Doctoral dissertation]. Georgia Tech; 2008. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/24719.
Council of Science Editors:
Biro C. Problems and results in partially ordered sets, graphs and geometry. [Doctoral Dissertation]. Georgia Tech; 2008. Available from: http://hdl.handle.net/1853/24719
19.
He, Qie.
Topics in discrete optimization: models, complexity and algorithms.
Degree: PhD, Industrial and Systems Engineering, 2013, Georgia Tech
URL: http://hdl.handle.net/1853/50237
► In this dissertation we examine several discrete optimization problems through the perspectives of modeling, complexity and algorithms. We first provide a probabilistic comparison of split…
(more)
▼ In this dissertation we examine several discrete optimization problems through the perspectives of modeling, complexity and algorithms. We first provide a probabilistic comparison of split and type 1 triangle cuts for mixed-integer programs with two rows and two integer variables in terms of cut coefficients and volume cutoff. Under a specific probabilistic model of the problem parameters, we show that for the above measure, the probability that a split cut is better than a type 1 triangle cut is higher than the probability that a type 1 triangle cut is better than a split cut. The analysis also suggests some guidelines on when type 1 triangle cuts are likely to be more effective than split cuts and vice versa. We next study a minimum concave cost network flow problem over a grid network. We give a polytime algorithm to solve this problem when the number of echelons is fixed. We show that the problem is NP-hard when the number of echelons is an input parameter. We also extend our result to grid networks with backward and upward arcs. Our result unifies the complexity results for several models in production planning and green recycling including the lot-sizing model, and gives the first polytime algorithm for some problems whose complexities were not known before. Finally, we examine how much complexity randomness will bring to a simple combinatorial optimization problem. We study a problem called the sell or hold problem (SHP). SHP is to sell k out of n indivisible assets over two stages, with known first-stage prices and random second-stage prices, to maximize the total expected revenue. Although the deterministic version of SHP is trivial to solve, we show that SHP is NP-hard when the second-stage prices are realized as a finite set of scenarios. We show that SHP is polynomially solvable when the number of scenarios in the second stage is constant. A max{1/2,k/n}-approximation algorithm is presented for the scenario-based SHP.
Advisors/Committee Members: Ahmed, Shabbir (advisor), Nemhauser, George L. (advisor), Cook, William J. (committee member), Dey, Santanu S. (committee member), Thomas, Robin (committee member).
Subjects/Keywords: Integer programming; Combinatorial optimization; Stochastic programming; Network flow; Production planning; Computational complexity; Mathematical optimization; Integer programming
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
He, Q. (2013). Topics in discrete optimization: models, complexity and algorithms. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/50237
Chicago Manual of Style (16th Edition):
He, Qie. “Topics in discrete optimization: models, complexity and algorithms.” 2013. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/50237.
MLA Handbook (7th Edition):
He, Qie. “Topics in discrete optimization: models, complexity and algorithms.” 2013. Web. 27 Jan 2021.
Vancouver:
He Q. Topics in discrete optimization: models, complexity and algorithms. [Internet] [Doctoral dissertation]. Georgia Tech; 2013. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/50237.
Council of Science Editors:
He Q. Topics in discrete optimization: models, complexity and algorithms. [Doctoral Dissertation]. Georgia Tech; 2013. Available from: http://hdl.handle.net/1853/50237
Georgia Tech
20.
Ponnuswami, Ashok Kumar.
Intractability Results for some Computational Problems.
Degree: PhD, Computing, 2008, Georgia Tech
URL: http://hdl.handle.net/1853/24638
► In this thesis, we show results for some well-studied problems from learning theory and combinatorial optimization. Learning Parities under the Uniform Distribution: We study the…
(more)
▼ In this thesis, we show results for some well-studied problems from learning theory and combinatorial optimization.
Learning Parities under the Uniform Distribution: We study the learnability of parities in the agnostic learning framework of Haussler and Kearns et al. We show that under the uniform distribution, agnostically learning parities reduces to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of Blum et al, this gives the first nontrivial algorithm for agnostic learning of parities. We use similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, we show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables and learning of k-juntas reduces to learning noisy parities of k variables.
Agnostic Learning of Halfspaces: We give an essentially optimal hardness result for agnostic learning of halfspaces over rationals. We show that for any constant ε finding a halfspace that agrees with an unknown function on 1/2+ε fraction of examples is NP-hard even when there exists a halfspace that agrees with the unknown function on 1-ε fraction of examples. This significantly improves on a number of previous hardness results for this problem. We extend the result to ε = 2[superscript-Ω(sqrt{log n})] assuming NP is not contained in DTIME(2[superscript(log n)O(1)]). Majorities of Halfspaces: We show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem. This also implies a hardness result for learning halfspaces with a high rate of adversarial noise even if the learning algorithm can output any efficiently computable hypothesis. Max-Clique, Chromatic Number and Min-3Lin-Deletion: We prove an improved hardness of approximation result for two problems, namely, the problem of finding the size of the largest clique in a graph (also referred to as the Max-Clique problem) and the problem of finding the chromatic number of a graph. We show that for any constant γ > 0, there is no polynomial time algorithm that approximates these problems within factor n/2[superscript(log n)3/4+γ] in an n vertex graph, assuming NP is not contained in BPTIME(2[superscript(log n)O(1)]). This improves the hardness factor of n/2[superscript (log n)1-γ'] for some small (unspecified) constant γ' > 0 shown by Khot. Our main idea is to show an improved hardness result for the Min-3Lin-Deletion problem.
An instance of Min-3Lin-Deletion is a system of linear equations modulo 2, where each equation is over three variables. The objective is to find the minimum number of equations that need to be deleted so that the remaining system of equations has a satisfying assignment. We show a hardness factor of 2[superscript sqrt{log n}] for this problem, improving upon the hardness factor of (log n)[superscriptβ] shown by…
Advisors/Committee Members: Khot, Subhash (Committee Chair), Randall, Dana (Committee Member), Thomas, Robin (Committee Member), Vempala, Santosh (Committee Member), Venkateswaran, H. (Committee Member).
Subjects/Keywords: Hardness of approximation; Max-Clique; Agnostic learning; Parities; Halfspaces; Thresholds; Circuit lower bounds; Combinatorial optimization; Computational learning theory; Machine learning
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Ponnuswami, A. K. (2008). Intractability Results for some Computational Problems. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/24638
Chicago Manual of Style (16th Edition):
Ponnuswami, Ashok Kumar. “Intractability Results for some Computational Problems.” 2008. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/24638.
MLA Handbook (7th Edition):
Ponnuswami, Ashok Kumar. “Intractability Results for some Computational Problems.” 2008. Web. 27 Jan 2021.
Vancouver:
Ponnuswami AK. Intractability Results for some Computational Problems. [Internet] [Doctoral dissertation]. Georgia Tech; 2008. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/24638.
Council of Science Editors:
Ponnuswami AK. Intractability Results for some Computational Problems. [Doctoral Dissertation]. Georgia Tech; 2008. Available from: http://hdl.handle.net/1853/24638
Georgia Tech
21.
Chakrabarty, Deeparnab.
Algorithmic aspects of connectivity, allocation and design problems.
Degree: PhD, Computing, 2008, Georgia Tech
URL: http://hdl.handle.net/1853/24659
► Most combinatorial optimization problems are NP -hard, which imply that under well- believed complexity assumptions, there exist no polynomial time algorithms to solve them. To…
(more)
▼ Most combinatorial optimization problems are
NP -hard, which imply that under well- believed complexity assumptions, there exist no polynomial time
algorithms to solve them. To cope with the NP-hardness, approximation algorithms which return solutions close to
the optimal, have become a rich field of study. One successful method for designing approx-
imation algorithms has been to model the optimization problem as an integer program and
then using its polynomial time solvable linear programming relaxation for the design and
analysis of such algorithms. Such a technique is called the LP-based technique.
In this thesis, we study the algorithmic aspects of three classes of combinatorial optimization problems
using LP-based techniques as our main tool.
Connectivity Problems:
We study the Steiner tree problem and devise new linear pro-
gramming relaxations for the problem. We show an equivalence of our relaxation with the
well studied bidirected cut relaxation for the Steiner tree problem. Furthermore, for a class
of graphs called quasi-bipartite graphs, we improve the best known upper bound on the
integrality gap from 3/2 to 4/3. Algorithmically, we obtain fast and simple approximation
algorithms for the Steiner tree problem on quasi-bipartite graphs.
Allocation Problems:
We study the budgeted al location problem of allocating a set of
indivisible items to a set of agents who bid on it but possess a hard budget constraint more
than which they are unwilling to pay. This problem is a special case of submodular welfare
maximization. We use a natural LP relaxation for the problem and improve the best known
approximation factor for the problem from ~ 0.632 to 3/4. We also improve the inapprox-
imability factor of the problem to 15/16 and use our techniques to show inapproximability
results for many other allocation problems.
We also study online allocation problems where the set of items are unknown and appear one at a time.
Under some necessary assumptions we provide online algorithms for
many problems which attain the (almost) optimal competitive ratio. Both these works have
applications in the area of budgeted auctions, the most famous of which are the sponsored
search auctions hosted by search engines on the Internet.
Design Problems:
We formally define and study design problems which asks how the
weights of an input instance can be designed, so that the minimum (or maximum) of
a certain function of the input can be maximized (respectively, minimized). We show
if the function can be approximated to any factor α, then the optimum design can be
approximated to the same factor.
We also show that (max-min) design problems are dual to packing problems. We use
the framework developed by our study of design problems to obtain results about fraction-
ally packing Steiner trees in a "black-box" fashion. Finally, we study integral packing of
spanning trees and provide an alternate proof of a theorem of Nash-Williams and Tutte
about…
Advisors/Committee Members: Vazirani, Vijay (Committee Chair), Cook, William (Committee Member), Kalai, Adam (Committee Member), Tetali, Prasad (Committee Member), Thomas, Robin (Committee Member).
Subjects/Keywords: Combinatorial optimization; Linear programming relaxations; Approximation algorithms; Combinatorial optimization; Approximation theory; Algorithms
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Chakrabarty, D. (2008). Algorithmic aspects of connectivity, allocation and design problems. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/24659
Chicago Manual of Style (16th Edition):
Chakrabarty, Deeparnab. “Algorithmic aspects of connectivity, allocation and design problems.” 2008. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/24659.
MLA Handbook (7th Edition):
Chakrabarty, Deeparnab. “Algorithmic aspects of connectivity, allocation and design problems.” 2008. Web. 27 Jan 2021.
Vancouver:
Chakrabarty D. Algorithmic aspects of connectivity, allocation and design problems. [Internet] [Doctoral dissertation]. Georgia Tech; 2008. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/24659.
Council of Science Editors:
Chakrabarty D. Algorithmic aspects of connectivity, allocation and design problems. [Doctoral Dissertation]. Georgia Tech; 2008. Available from: http://hdl.handle.net/1853/24659
Georgia Tech
22.
Bilinski, Mark.
Approximating the circumference of 3-connected claw-free graphs.
Degree: PhD, Mathematics, 2008, Georgia Tech
URL: http://hdl.handle.net/1853/26516
► Jackson and Wormald show that every 3-connected K_1,d-free graph, on n vertices, contains a cycle of length at least 1/2 n^g(d) where g(d) = (log_2…
(more)
▼ Jackson and Wormald show that every 3-connected
K_1,d-free graph, on n vertices, contains a cycle of length at least 1/2 n^g(d) where g(d) = (log_2 6 + 2 log_2 (2d+1))^-1. For d = 3, g(d) ~ 0.122.
Improving this bound, we prove that if G is a 3-connected claw-free graph on at least 6 vertices, then there exists a cycle C in G such that |E(C)| is at least c n^g+5, where
g = log_3 2 and c > 1/7 is a constant.
To do this, we instead prove a stronger theorem that requires the cycle to contain two specified edges. We then use Tutte decomposition to partition the graph and then use the inductive
hypothesis of our theorem to find paths or cycles in the different parts of the decomposition.
Advisors/Committee Members: Yu, Xingxing (Committee Chair), Duke, Richard (Committee Member), Tetali, Prasad (Committee Member), Thomas, Robin (Committee Member), Vigoda, Eric (Committee Member).
Subjects/Keywords: Claw-free; 3-connected; Long cycles; Graph theory; Decomposition (Mathematics)
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Bilinski, M. (2008). Approximating the circumference of 3-connected claw-free graphs. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/26516
Chicago Manual of Style (16th Edition):
Bilinski, Mark. “Approximating the circumference of 3-connected claw-free graphs.” 2008. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/26516.
MLA Handbook (7th Edition):
Bilinski, Mark. “Approximating the circumference of 3-connected claw-free graphs.” 2008. Web. 27 Jan 2021.
Vancouver:
Bilinski M. Approximating the circumference of 3-connected claw-free graphs. [Internet] [Doctoral dissertation]. Georgia Tech; 2008. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/26516.
Council of Science Editors:
Bilinski M. Approximating the circumference of 3-connected claw-free graphs. [Doctoral Dissertation]. Georgia Tech; 2008. Available from: http://hdl.handle.net/1853/26516
Georgia Tech
23.
Jiang, Wen.
Maximum Codes with the Identifiable Parent Property.
Degree: PhD, Mathematics, 2006, Georgia Tech
URL: http://hdl.handle.net/1853/14072
► We study codes that have identifiable parent property. Such codes are called IPP codes. Research on IPP codes is motivated by design of schemes that…
(more)
▼ We study codes that have identifiable parent property. Such codes are called IPP codes. Research on IPP codes is motivated by design of
schemes that protect against piracy of digital products.
Construction and decoding of maximum IPP codes have been studied in rich literature. General bounds on F(n,q), the maximum size of IPP
codes of length n over an alphabet with q elements, have been obtained through the use of techniques from graph theory and combinatorial
design. Improved bounds on F(3,q) and F(4,q) are obtained. Probabilistic techniques are also used to prove the existence of certain IPP codes.
We prove a precise formula for F(3,q), construct maximum IPP codes with size F(3,q), and give an efficient decoding algorithm for such codes. The main techniques used in this thesis are from graph theory and nonlinear optimization. Our approach may be used to improve bounds on F(2k+1, q). For
example, we characterize the associated graphs of
maximum IPP codes of length 5, and obtain bounds on F(5,q).
Advisors/Committee Members: Yu, Xingxing (Committee Chair), Dieci, Luca (Committee Member), Li, Ye (Committee Member), Thomas, Robin (Committee Member), Trotter, William (Committee Member).
Subjects/Keywords: Graph theory; IPP codes; Graph theory; Cryptography; Ciphers
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Jiang, W. (2006). Maximum Codes with the Identifiable Parent Property. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/14072
Chicago Manual of Style (16th Edition):
Jiang, Wen. “Maximum Codes with the Identifiable Parent Property.” 2006. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/14072.
MLA Handbook (7th Edition):
Jiang, Wen. “Maximum Codes with the Identifiable Parent Property.” 2006. Web. 27 Jan 2021.
Vancouver:
Jiang W. Maximum Codes with the Identifiable Parent Property. [Internet] [Doctoral dissertation]. Georgia Tech; 2006. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/14072.
Council of Science Editors:
Jiang W. Maximum Codes with the Identifiable Parent Property. [Doctoral Dissertation]. Georgia Tech; 2006. Available from: http://hdl.handle.net/1853/14072
Georgia Tech
24.
Goycoolea, Marcos G.
Cutting Planes for Large Mixed Integer Programming Models.
Degree: PhD, Industrial and Systems Engineering, 2006, Georgia Tech
URL: http://hdl.handle.net/1853/13956
► In this thesis I focus on cutting planes for large Mixed Integer Programming (MIP) problems. More specifically, I focus on two independent cutting planes studies.…
(more)
▼ In this thesis I focus on cutting planes for large Mixed Integer Programming (MIP) problems. More specifically, I focus on two independent cutting planes studies. The first of these deals with cutting planes for the Traveling Salesman Problem (TSP), and the second with cutting planes for general MIPs.
In the first study I introduce a new class of cutting planes which I call the Generalized Domino Parity (GDP) inequalities. My main achievements with regard to these are: (1) I show that these are valid for the TSP and for the graphical TSP. (2) I show that they generalize most well-known TSP inequalities (including combs, domino-parity constraints, clique-trees, bipartitions, paths and stars). (3) I show that a sub-class of these (which contains all clique-tree inequalities w/ a fixed number of handles) can be separated in polynomial time, on planar graphs.
My second study can be subdivided in two parts. In the first of these I study the Mixed Integer Knapsack Problem (MIKP) and develop a branch-and-bound based algorithm for solving it. The novelty of the approach is that it exploits the notion of "dominance" in order to effectively prune solutions in the branch-and-bound tree. In the second part, I develop a Mixed Integer Rounding (MIR) cut separation heuristic, and embed the MIKP solver in a column generation algorithm in order to assess the performance of said heuristic. The goal of this study is to understand why no other class of inequalities derived from single-row systems has been able to outperform the MIR. Computational results are presented.
Advisors/Committee Members: Cook, William (Committee Chair), Gu, Zonghao (Committee Member), Johnson, Ellis (Committee Member), Nemhauser, George (Committee Member), Thomas, Robin (Committee Member).
Subjects/Keywords: Traveling salesman problem; Cutting planes; Mixed integer rounding; Mixed integer programming
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Goycoolea, M. G. (2006). Cutting Planes for Large Mixed Integer Programming Models. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/13956
Chicago Manual of Style (16th Edition):
Goycoolea, Marcos G. “Cutting Planes for Large Mixed Integer Programming Models.” 2006. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/13956.
MLA Handbook (7th Edition):
Goycoolea, Marcos G. “Cutting Planes for Large Mixed Integer Programming Models.” 2006. Web. 27 Jan 2021.
Vancouver:
Goycoolea MG. Cutting Planes for Large Mixed Integer Programming Models. [Internet] [Doctoral dissertation]. Georgia Tech; 2006. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/13956.
Council of Science Editors:
Goycoolea MG. Cutting Planes for Large Mixed Integer Programming Models. [Doctoral Dissertation]. Georgia Tech; 2006. Available from: http://hdl.handle.net/1853/13956
Georgia Tech
26.
Inkmann, Torsten.
Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem.
Degree: PhD, Mathematics, 2007, Georgia Tech
URL: http://hdl.handle.net/1853/22583
► The tree-width and branch-width of a graph are two well-studied examples of parameters that measure how well a given graph can be decomposed into a…
(more)
▼ The tree-width and branch-width of a graph are two well-studied examples of parameters that measure how well a given graph can be decomposed into a tree structure. In this thesis we give several results and applications concerning these concepts, in particular if the graph is embedded on a surface.
In the first part of this thesis we develop a geometric description of tangles in graphs embedded on a fixed surface (tangles are the obstructions for low branch-width), generalizing a result of Robertson and Seymour. We use this result to establish a relationship between the branch-width of an embedded graph and the carving-width of an associated graph, generalizing a result for the plane of Seymour and
Thomas. We also discuss how these results relate to the polynomial-time algorithm to determine the branch-width of planar graphs of Seymour and
Thomas, and explain why their method does not generalize to surfaces other than the sphere.
We also prove a result concerning the class C_2k of minor-minimal graphs of branch-width 2k in the plane, for an integer k at least 2.
We show that applying a certain construction to a class of graphs in the projective plane yields a subclass of C_2k, but also show that not all members of C_2k arise in this way if k is at least 3.
The last part of the thesis is concerned with applications of graphs of bounded tree-width to the Traveling Salesman Problem (TSP). We first show how one can solve the separation problem for comb inequalities (with an arbitrary number of teeth) in linear time if the tree-width is bounded. In the second part, we modify an algorithm of Letchford et al. using tree-decompositions to obtain a practical method for separating a different class of TSP inequalities, called simple DP constraints, and study their effectiveness for solving TSP instances.
Advisors/Committee Members: Thomas, Robin (Committee Chair), Cook, William J. (Committee Co-Chair), Dvorak, Zdenek (Committee Member), Parker, Robert G. (Committee Member), Yu, Xingxing (Committee Member).
Subjects/Keywords: Tree-decompositions; TSP; Branch-width; Graphs on surfaces; Graph theory; Branch-decompositions; Decomposition method; Graph theory; Traveling-salesman problem; Programming (Mathematics); Combinatorial optimization
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Inkmann, T. (2007). Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/22583
Chicago Manual of Style (16th Edition):
Inkmann, Torsten. “Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem.” 2007. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/22583.
MLA Handbook (7th Edition):
Inkmann, Torsten. “Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem.” 2007. Web. 27 Jan 2021.
Vancouver:
Inkmann T. Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem. [Internet] [Doctoral dissertation]. Georgia Tech; 2007. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/22583.
Council of Science Editors:
Inkmann T. Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem. [Doctoral Dissertation]. Georgia Tech; 2007. Available from: http://hdl.handle.net/1853/22583
Georgia Tech
27.
Karande, Chinmay.
Algorithms and mechanism design for multi-agent systems.
Degree: PhD, Computing, 2010, Georgia Tech
URL: http://hdl.handle.net/1853/37229
► A scenario where multiple entities interact with a common environment to achieve individual and common goals either co-operatively or competitively can be classified as a…
(more)
▼ A scenario where multiple entities interact with a common environment to achieve individual and common goals either co-operatively or competitively can be classified as a Multi-Agent System. In this thesis, we concentrate on the situations where the agents exhibit selfish, competitive and strategic behaviour, giving rise to interesting game theoretic and optimization problems. From a computational point of view, the presence of multiple agents introduces strategic and temporal issues, apart from enhancing the difficulty of optimization.
We study the following natural mathematical models of such multi-agent problems faced in practice: a) combinatorial optimization problems with multi-agent submodular cost functions, b) combinatorial auctions with partially public valuations and c) online vertex-weighted bipartite matching and single bid budgeted allocations. We provide approximation algorithms, online algorithms and hardness of approximation results for these problems.
Advisors/Committee Members: Vazirani, Vijay (Committee Chair), Balcan, Maria-Florina (Committee Member), Cook, William (Committee Member), Thomas, Robin (Committee Member), Vigoda, Eric (Committee Member).
Subjects/Keywords: Multi-agent systems; Online auction; Algorithms; Mechanism design; Submodular functions; Matroids
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Karande, C. (2010). Algorithms and mechanism design for multi-agent systems. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/37229
Chicago Manual of Style (16th Edition):
Karande, Chinmay. “Algorithms and mechanism design for multi-agent systems.” 2010. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/37229.
MLA Handbook (7th Edition):
Karande, Chinmay. “Algorithms and mechanism design for multi-agent systems.” 2010. Web. 27 Jan 2021.
Vancouver:
Karande C. Algorithms and mechanism design for multi-agent systems. [Internet] [Doctoral dissertation]. Georgia Tech; 2010. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/37229.
Council of Science Editors:
Karande C. Algorithms and mechanism design for multi-agent systems. [Doctoral Dissertation]. Georgia Tech; 2010. Available from: http://hdl.handle.net/1853/37229
Georgia Tech
28.
Devanur, Nikhil Rangarajan.
Efficient Algorithms for Market Equilibria.
Degree: PhD, Computing, 2007, Georgia Tech
URL: http://hdl.handle.net/1853/16282
► The mathematical modelling of a market, and the proof of existence of equilibria have been of central importance in mathematical economics. Since the existence proof…
(more)
▼ The mathematical modelling of a market, and the proof of existence of
equilibria have been of central importance in mathematical economics.
Since the existence proof is non-constructive in general,
a natural question is if computation of equilibria can be done efficiently.
Moreover, the emergence of Internet and e-commerce has given rise to new
markets that have completely changed the traditional notions.
Add to this the pervasiveness of computing resources,
and an algorithmic theory of market equilibrium becomes highly desirable.
The goal of this thesis is to provide polynomial time algorithms for
various market models.
Two basic market models are the Fisher model: one in which there is a
demarcation between buyers and sellers, buyers are interested in the
goods that the sellers possess, and sellers are only interested in the
money that the buyers have; and the Arrow-Debreu model: everyone has
an endowment of goods, and wants to exchange them for other goods.
We give the first polynomial time algorithm for exactly computing an
equilibrium in the Fisher model with linear utilities. We also show that
the basic ideas in this algorithm can be extended to give a strongly
polynomial time approximation scheme in the Arrow-Debreu model.
We also give several existential, algorithmic and structural
results for new market models:
- the *spending constraint* utilities (defined by Vazirani) that captures
the "diminishing returns" property while generalizing the algorithm for
the linear case.
- the capacity allocation market (defined by Kelly), motivated
by the study of fairness and stability of the Transmission Control
Protocol (TCP) for the Internet, and more generally the class of
Eisenberg-Gale (EG) markets (defined by Jain and Vazirani).
In addition, we consider the adwords market
on search engines and show that some of these models are a natural fit
in this setting. Finally, this line of research has given insights into
the fundamental techniques in algorithm design. The primal-dual schema
has been a great success in combinatorial optimization and approximation
algorithms. Our algorithms use this paradigm in the enhanced setting of
Karush-Kuhn-Tucker (KKT) conditions and convex programs.
Advisors/Committee Members: Vazirani, Vijay V. (Committee Chair), Khot, Subhash (Committee Member), Randall, Dana (Committee Member), Thomas, Robin (Committee Member), Vempala, Santosh (Committee Member).
Subjects/Keywords: Combinatorial; Network flow; Utilities; Arrow-Debreu; Fisher
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Devanur, N. R. (2007). Efficient Algorithms for Market Equilibria. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/16282
Chicago Manual of Style (16th Edition):
Devanur, Nikhil Rangarajan. “Efficient Algorithms for Market Equilibria.” 2007. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/16282.
MLA Handbook (7th Edition):
Devanur, Nikhil Rangarajan. “Efficient Algorithms for Market Equilibria.” 2007. Web. 27 Jan 2021.
Vancouver:
Devanur NR. Efficient Algorithms for Market Equilibria. [Internet] [Doctoral dissertation]. Georgia Tech; 2007. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/16282.
Council of Science Editors:
Devanur NR. Efficient Algorithms for Market Equilibria. [Doctoral Dissertation]. Georgia Tech; 2007. Available from: http://hdl.handle.net/1853/16282
Georgia Tech
29.
Norine, Serguei.
Matching structure and Pfaffian orientations of graphs.
Degree: PhD, Mathematics, 2005, Georgia Tech
URL: http://hdl.handle.net/1853/7232
► The first result of this thesis is a generation theorem for bricks. A brick is a 3-connected graph such that the graph obtained from it…
(more)
▼ The first result of this thesis is a generation theorem for
bricks. A brick is a 3-connected graph such that the graph
obtained from it by deleting any two distinct vertices has a
perfect matching. The importance of bricks stems from the fact
that they are building blocks of a decomposition procedure of
Kotzig, and Lovasz and Plummer. We prove that every brick except
for the Petersen graph can be generated from K_4 or the prism by
repeatedly applying certain operations in such a way that all the
intermediate graphs are bricks. We use this theorem to prove an
exact upper bound on the number of edges in a minimal brick with
given number of vertices and to prove that every minimal brick has
at least three vertices of degree three.
The second half of the thesis is devoted to an investigation of
graphs that admit Pfaffian orientations. We prove that a graph
admits a Pfaffian orientation if and only if it can be drawn in
the plane in such a way that every perfect matching crosses
itself even number of times. Using similar techniques, we give a
new proof of a theorem of Kleitman on the parity of crossings and
develop a new approach to Turan's problem of estimating crossing
number of complete bipartite graphs.
We further extend our methods to study k-Pfaffian graphs and
generalize a theorem by Gallucio, Loebl and Tessler. Finally, we
relate Pfaffian orientations and signs of edge-colorings and prove
a conjecture of Goddyn that every k-edge-colorable k-regular
Pfaffian graph is k-list-edge-colorable. This generalizes a
theorem of Ellingham and Goddyn for planar graphs.
Advisors/Committee Members: Thomas, Robin (Committee Chair), Cook, William (Committee Member), Duke, Richard (Committee Member), Trotter, William T. (Committee Member), Yu, Xingxing (Committee Member).
Subjects/Keywords: Pfaffian orientations; Graph theory; Matching theory; Pfaffian systems; Matching theory; Graph theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Norine, S. (2005). Matching structure and Pfaffian orientations of graphs. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/7232
Chicago Manual of Style (16th Edition):
Norine, Serguei. “Matching structure and Pfaffian orientations of graphs.” 2005. Doctoral Dissertation, Georgia Tech. Accessed January 27, 2021.
http://hdl.handle.net/1853/7232.
MLA Handbook (7th Edition):
Norine, Serguei. “Matching structure and Pfaffian orientations of graphs.” 2005. Web. 27 Jan 2021.
Vancouver:
Norine S. Matching structure and Pfaffian orientations of graphs. [Internet] [Doctoral dissertation]. Georgia Tech; 2005. [cited 2021 Jan 27].
Available from: http://hdl.handle.net/1853/7232.
Council of Science Editors:
Norine S. Matching structure and Pfaffian orientations of graphs. [Doctoral Dissertation]. Georgia Tech; 2005. Available from: http://hdl.handle.net/1853/7232
. 
Open Access Theses and Dissertations
