Matching Items (76)
Filtering by
- Resource Type: Text
Description
A $k$-list assignment for a graph $G=(V, E)$ is a function $L$ that assigns a $k$-set $L(v)$ of "available colors" to each vertex $v \in V$. A $d$-defective, $m$-fold, $L$-coloring is a function $\phi$ that assigns an $m$-subset $\phi(v) \subseteq L(v)$ to each vertex $v$ so that each color class $V_{i}=\{v \in V:$ $i \in \phi(v)\}$ induces a subgraph of $G$ with maximum degree at most $d$. An edge $xy$ is an $i$-flaw of $\phi$ if $i\in \phi(x) \cap \phi(y)$. An online list-coloring algorithm $\mathcal{A}$ works on a known graph $G$ and an unknown $k$-list assignment $L$ to produce a coloring $\phi$ as follows. At step $r$ the set of vertices $v$ with $r \in L(v)$ is revealed to $\mathcal{A}$. For each vertex $v$, $\mathcal{A}$ must decide irrevocably whether to add $r$ to $\phi(v)$. The online choice number $\pt_{m}^{d}(G)$ of $G$ is the least $k$ for which some such algorithm produces a $d$-defective, $m$-fold, $L$-coloring $\phi$ of $G$ for all $k$-list assignments $L$. Online list coloring was introduced independently by Uwe Schauz and Xuding Zhu. It was known that if $G$ is planar then $\pt_{1}^{0}(G) \leq 5$ and $\pt_{1}^{1}(G) \leq 4$ are sharp bounds; here it is proved that $\pt_{1}^{3}(G) \leq 3$ is sharp, but there is a planar graph $H$ with $\pt_{1}^{2}(H)\ge 4$. Zhu conjectured that for some integer $m$, every planar graph $G$ satisfies $\pt_{m}^{0}(G) \leq 5 m-1$, and even that this is true for $m=2$. This dissertation proves that $\pt_{2}^{1}(G) \leq 9$, so the conjecture is "nearly" true, and the proof extends to $\pt_{m}^{1}(G) \leq\left\lceil\frac{9}{2} m\right\rceil$. Using Alon's Combinatorial Nullstellensatz, this is strengthened by showing that $G$ contains a linear forest $(V, F)$ such that there is an online algorithm that witnesses $\mathrm{pt}_{2}^{1}(G) \leq 9$ while producing a coloring whose flaws are in $F$, and such that no edge is an $i$-flaw and a $j$-flaw for distinct colors $i$ and $j$.
Contributorshan, ming (Author) / Kierstead, Henry A. (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Sen, Arunabha (Committee member) / Spielberg, John (Committee member) / Fishel, Susanna (Committee member) / Arizona State University (Publisher)
Created2021
Description
Let $G=(V,E)$ be a graph. A \emph{list assignment} $L$ for $G$ is a function from
$V$ to subsets of the natural numbers. An $L$-\emph{coloring} is a function $f$
with domain $V$ such that $f(v)\in L(v)$ for all vertices $v\in V$ and $f(x)\ne f(y)$
whenever $xy\in E$. If $|L(v)|=t$ for all $v\in V$ then $L$ is a $t$-\emph{list
assignment}. The graph $G$ is $t$-choosable if for every $t$-list assignment $L$
there is an $L$-coloring. The least $t$ such that $G$ is $t$-choosable is called
the list chromatic number of $G$, and is denoted by $\ch(G)$. The complete multipartite
graph with $k$ parts, each of size $s$ is denoted by $K_{s*k}$. Erd\H{o}s et al.
suggested the problem of determining $\ensuremath{\ch(K_{s*k})}$, and showed that
$\ch(K_{2*k})=k$. Alon gave bounds of the form $\Theta(k\log s)$. Kierstead proved
the exact bound $\ch(K_{3*k})=\lceil\frac{4k-1}{3}\rceil$. Here it is proved that
$\ch(K_{4*k})=\lceil\frac{3k-1}{2}\rceil$.
An online version of the list coloring problem was introduced independently by Schauz
and Zhu. It can be formulated as a game between two players, Alice and Bob. Alice
designs lists of colors for all vertices, but does not tell Bob, and is allowed to
change her mind about unrevealed colors as the game progresses. On her $i$-th turn
Alice reveals all vertices with $i$ in their list. On his $i$-th turn Bob decides,
irrevocably, which (independent set) of these vertices to color with $i$. For a
function $l$ from $V$ to the natural numbers, Bob wins the $l$-\emph{game} if
eventually he colors every vertex $v$ before $v$ has had $l(v)+1$ colors of its
list revealed by Alice; otherwise Alice wins. The graph $G$ is $l$-\emph{online
choosable} or \emph{$l$-paintable} if Bob has a strategy to win the $l$-game. If
$l(v)=t$ for all $v\in V$ and $G$ is $l$-paintable, then $G$ is t-paintable.
The \emph{online list chromatic number }of $G$ is the least $t$ such that $G$
is $t$-paintable, and is denoted by $\ensuremath{\ch^{\mathrm{OL}}(G)}$. Evidently,
$\ch^{\mathrm{OL}}(G)\geq\ch(G)$. Zhu conjectured that the gap $\ch^{\mathrm{OL}}(G)-\ch(G)$
can be arbitrarily large. However there are only a few known examples with this gap
equal to one, and none with larger gap. This conjecture is explored in this thesis.
One of the obstacles is that there are not many graphs whose exact list coloring
number is known. This is one of the motivations for establishing new cases of Erd\H{o}s'
problem. Here new examples of graphs with gap one are found, and related technical
results are developed as tools for attacking Zhu's conjecture.
The square $G^{2}$ of a graph $G$ is formed by adding edges between all vertices
at distance $2$. It was conjectured that every graph $G$ satisfies $\chi(G^{2})=\ch(G^{2})$.
This was recently disproved for specially constructed graphs. Here it is shown that
a graph arising naturally in the theory of cellular networks is also a counterexample.
$V$ to subsets of the natural numbers. An $L$-\emph{coloring} is a function $f$
with domain $V$ such that $f(v)\in L(v)$ for all vertices $v\in V$ and $f(x)\ne f(y)$
whenever $xy\in E$. If $|L(v)|=t$ for all $v\in V$ then $L$ is a $t$-\emph{list
assignment}. The graph $G$ is $t$-choosable if for every $t$-list assignment $L$
there is an $L$-coloring. The least $t$ such that $G$ is $t$-choosable is called
the list chromatic number of $G$, and is denoted by $\ch(G)$. The complete multipartite
graph with $k$ parts, each of size $s$ is denoted by $K_{s*k}$. Erd\H{o}s et al.
suggested the problem of determining $\ensuremath{\ch(K_{s*k})}$, and showed that
$\ch(K_{2*k})=k$. Alon gave bounds of the form $\Theta(k\log s)$. Kierstead proved
the exact bound $\ch(K_{3*k})=\lceil\frac{4k-1}{3}\rceil$. Here it is proved that
$\ch(K_{4*k})=\lceil\frac{3k-1}{2}\rceil$.
An online version of the list coloring problem was introduced independently by Schauz
and Zhu. It can be formulated as a game between two players, Alice and Bob. Alice
designs lists of colors for all vertices, but does not tell Bob, and is allowed to
change her mind about unrevealed colors as the game progresses. On her $i$-th turn
Alice reveals all vertices with $i$ in their list. On his $i$-th turn Bob decides,
irrevocably, which (independent set) of these vertices to color with $i$. For a
function $l$ from $V$ to the natural numbers, Bob wins the $l$-\emph{game} if
eventually he colors every vertex $v$ before $v$ has had $l(v)+1$ colors of its
list revealed by Alice; otherwise Alice wins. The graph $G$ is $l$-\emph{online
choosable} or \emph{$l$-paintable} if Bob has a strategy to win the $l$-game. If
$l(v)=t$ for all $v\in V$ and $G$ is $l$-paintable, then $G$ is t-paintable.
The \emph{online list chromatic number }of $G$ is the least $t$ such that $G$
is $t$-paintable, and is denoted by $\ensuremath{\ch^{\mathrm{OL}}(G)}$. Evidently,
$\ch^{\mathrm{OL}}(G)\geq\ch(G)$. Zhu conjectured that the gap $\ch^{\mathrm{OL}}(G)-\ch(G)$
can be arbitrarily large. However there are only a few known examples with this gap
equal to one, and none with larger gap. This conjecture is explored in this thesis.
One of the obstacles is that there are not many graphs whose exact list coloring
number is known. This is one of the motivations for establishing new cases of Erd\H{o}s'
problem. Here new examples of graphs with gap one are found, and related technical
results are developed as tools for attacking Zhu's conjecture.
The square $G^{2}$ of a graph $G$ is formed by adding edges between all vertices
at distance $2$. It was conjectured that every graph $G$ satisfies $\chi(G^{2})=\ch(G^{2})$.
This was recently disproved for specially constructed graphs. Here it is shown that
a graph arising naturally in the theory of cellular networks is also a counterexample.
ContributorsWang, Ran (Author) / Kierstead, H.A. (Thesis advisor) / Colbourn, Charles (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2015
Description
Complex systems are pervasive in science and engineering. Some examples include complex engineered networks such as the internet, the power grid, and transportation networks. The complexity of such systems arises not just from their size, but also from their structure, operation (including control and management), evolution over time, and that people are involved in their design and operation. Our understanding of such systems is limited because their behaviour cannot be characterized using traditional techniques of modelling and analysis.
As a step in model development, statistically designed screening experiments may be used to identify the main effects and interactions most significant on a response of a system. However, traditional approaches for screening are ineffective for complex systems because of the size of the experimental design. Consequently, the factors considered are often restricted, but this automatically restricts the interactions that may be identified as well. Alternatively, the designs are restricted to only identify main effects, but this then fails to consider any possible interactions of the factors.
To address this problem, a specific combinatorial design termed a locating array is proposed as a screening design for complex systems. Locating arrays exhibit logarithmic growth in the number of factors because their focus is on identification rather than on measurement. This makes practical the consideration of an order of magnitude more factors in experimentation than traditional screening designs.
As a proof-of-concept, a locating array is applied to screen for main effects and low-order interactions on the response of average transport control protocol (TCP) throughput in a simulation model of a mobile ad hoc network (MANET). A MANET is a collection of mobile wireless nodes that self-organize without the aid of any centralized control or fixed infrastructure. The full-factorial design for the MANET considered is infeasible (with over 10^{43} design points) yet a locating array has only 421 design points.
In conjunction with the locating array, a ``heavy hitters'' algorithm is developed to identify the influential main effects and two-way interactions, correcting for the non-normal distribution of the average throughput, and uneven coverage of terms in the locating array. The significance of the identified main effects and interactions is validated independently using the statistical software JMP.
The statistical characteristics used to evaluate traditional screening designs are also applied to locating arrays.
These include the matrix of covariance, fraction of design space, and aliasing, among others. The results lend additional support to the use of locating arrays as screening designs.
The use of locating arrays as screening designs for complex engineered systems is promising as they yield useful models. This facilitates quantitative evaluation of architectures and protocols and contributes to our understanding of complex engineered networks.
As a step in model development, statistically designed screening experiments may be used to identify the main effects and interactions most significant on a response of a system. However, traditional approaches for screening are ineffective for complex systems because of the size of the experimental design. Consequently, the factors considered are often restricted, but this automatically restricts the interactions that may be identified as well. Alternatively, the designs are restricted to only identify main effects, but this then fails to consider any possible interactions of the factors.
To address this problem, a specific combinatorial design termed a locating array is proposed as a screening design for complex systems. Locating arrays exhibit logarithmic growth in the number of factors because their focus is on identification rather than on measurement. This makes practical the consideration of an order of magnitude more factors in experimentation than traditional screening designs.
As a proof-of-concept, a locating array is applied to screen for main effects and low-order interactions on the response of average transport control protocol (TCP) throughput in a simulation model of a mobile ad hoc network (MANET). A MANET is a collection of mobile wireless nodes that self-organize without the aid of any centralized control or fixed infrastructure. The full-factorial design for the MANET considered is infeasible (with over 10^{43} design points) yet a locating array has only 421 design points.
In conjunction with the locating array, a ``heavy hitters'' algorithm is developed to identify the influential main effects and two-way interactions, correcting for the non-normal distribution of the average throughput, and uneven coverage of terms in the locating array. The significance of the identified main effects and interactions is validated independently using the statistical software JMP.
The statistical characteristics used to evaluate traditional screening designs are also applied to locating arrays.
These include the matrix of covariance, fraction of design space, and aliasing, among others. The results lend additional support to the use of locating arrays as screening designs.
The use of locating arrays as screening designs for complex engineered systems is promising as they yield useful models. This facilitates quantitative evaluation of architectures and protocols and contributes to our understanding of complex engineered networks.
ContributorsAldaco-Gastelum, Abraham Netzahualcoyotl (Author) / Syrotiuk, Violet R. (Thesis advisor) / Colbourn, Charles J. (Committee member) / Sen, Arunabha (Committee member) / Montgomery, Douglas C. (Committee member) / Arizona State University (Publisher)
Created2015
Description
Text classification, in the artificial intelligence domain, is an activity in which text documents are automatically classified into predefined categories using machine learning techniques. An example of this is classifying uncategorized news articles into different predefined categories such as "Business", "Politics", "Education", "Technology" , etc. In this thesis, supervised machine learning approach is followed, in which a module is first trained with pre-classified training data and then class of test data is predicted. Good feature extraction is an important step in the machine learning approach and hence the main component of this text classifier is semantic triplet based features in addition to traditional features like standard keyword based features and statistical features based on shallow-parsing (such as density of POS tags and named entities). Triplet {Subject, Verb, Object} in a sentence is defined as a relation between subject and object, the relation being the predicate (verb). Triplet extraction process, is a 5 step process which takes input corpus as a web text document(s), each consisting of one or many paragraphs, from RSS feeds to lists of extremist website. Input corpus feeds into the "Pronoun Resolution" step, which uses an heuristic approach to identify the noun phrases referenced by the pronouns. The next step "SRL Parser" is a shallow semantic parser and converts the incoming pronoun resolved paragraphs into annotated predicate argument format. The output of SRL parser is processed by "Triplet Extractor" algorithm which forms the triplet in the form {Subject, Verb, Object}. Generalization and reduction of triplet features is the next step. Reduced feature representation reduces computing time, yields better discriminatory behavior and handles curse of dimensionality phenomena. For training and testing, a ten- fold cross validation approach is followed. In each round SVM classifier is trained with 90% of labeled (training) data and in the testing phase, classes of remaining 10% unlabeled (testing) data are predicted. Concluding, this paper proposes a model with semantic triplet based features for story classification. The effectiveness of the model is demonstrated against other traditional features used in the literature for text classification tasks.
ContributorsKarad, Ravi Chandravadan (Author) / Davulcu, Hasan (Thesis advisor) / Corman, Steven (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2013
Description
The overall contribution of the Minerva Initiative at ASU is to map social organizations in a multidimensional space that provides a measure of their radical or counter radical influence over the demographics of a nation. This tool serves as a simple content management system to store and track project resources like documents, images, videos and web links. It provides centralized and secure access to email conversations among project team members. Conversations are categorized into one of the seven pre-defined categories. Each category is associated with a certain set of keywords and we follow a frequency based approach for matching email conversations with the categories. The interface is hosted as a web application which can be accessed by the project team.
ContributorsNair, Apurva Aravindakshan (Author) / Davulcu, Hasan (Thesis advisor) / Sen, Arunabha (Committee member) / Dasgupta, Partha (Committee member) / Arizona State University (Publisher)
Created2012
Description
Social media platforms provide a rich environment for analyzing user behavior. Recently, deep learning-based methods have been a mainstream approach for social media analysis models involving complex patterns. However, these methods are susceptible to biases in the training data, such as participation inequality. Basically, a mere 1% of users generate the majority of the content on social networking sites, while the remaining users, though engaged to varying degrees, tend to be less active in content creation and largely silent. These silent users consume and listen to information that is propagated on the platform.However, their voice, attitude, and interests are not reflected in the online content, making the decision of the current methods predisposed towards the opinion of the active users. So models can mistake the loudest users for the majority. To make the silent majority heard is to reveal the true landscape of the platform. In this dissertation, to compensate for this bias in the data, which is related to user-level data scarcity, I introduce three pieces of research work. Two of these proposed solutions deal with the data on hand while the other tries to augment the current data. Specifically, the first proposed approach modifies the weight of users' activity/interaction in the input space, while the second approach involves re-weighting the loss based on the users' activity levels during the downstream task training. Lastly, the third approach uses large language models (LLMs) and learns the user's writing behavior to expand the current data. In other words, by utilizing LLMs as a sophisticated knowledge base, this method aims to augment the silent user's data.
ContributorsKarami, Mansooreh (Author) / Liu, Huan (Thesis advisor) / Sen, Arunabha (Committee member) / Davulcu, Hasan (Committee member) / Mancenido, Michelle V. (Committee member) / Arizona State University (Publisher)
Created2023