Spelling suggestions: "subject:"archard"" "subject:"achard""
1 
Inapproximability of the Minimum Biclique Edge Partition ProblemHIRATA, Tomio, OTSUKI, Hideaki 01 February 2010 (has links)
No description available.

2 
An evolutionary algorithm for the constrained forest problemQueern, John John 01 January 2013 (has links)
Given an undirected edgeweighted graph G and a positive integer m, the Constrained Forest Problem (CFP) seeks a lowestcost (or minimumweight) forest F which spans G while satisfying the requirement that each tree in F contain at least m vertices. This problem has been shown to be NPhard for values of m greater than three, giving rise to a number of approximation strategies for finding reasonable mforest solutions. This research presents a new genetic algorithm (GA) which can consistently find equalorbetter solutions to the problem when compared to nongenetic alternatives. This GA is unique in that it uses chromosomes which are actual candidate solutions (mforests) and performs genetic operations (random creation, selection, recombination, and mutation) on these candidate solutions. Experiments were run using 180 different GA configurations on 50 benchmark graphs to determine which operators and techniques would be most successful in solving the mforest problem. The "heaviest edge first" or HEF algorithm run against the minimum spanning tree (MST) of a graph was used as a performance metric. Previously, the HEF(MST) algorithm had been shown to produce the best results on mforest problems. When the GA was able to find better results than HEF(MST) on the same problem instance, this was considered a GA success. Since the GA's initial population included heuristic candidate solutions such as HEF(MST), the GA never did worse than the best of these. GA solution quality did vary, however, often finding several different betterthanHEF(MST) solutions, illustrating the stochastic nature of the process. Based on data collected from the 9000 initial problem instances, several factors were shown to significantly improve the quality of the GA solution. Problem instances which did not include mutation had a much lower success rate than those which did. Adding calculated heuristic solutions such as HEF(MST) to the initial population allowed the GA to converge more quickly and improved its likelihood of finding betterthanHEF(MST) solutions. Building an initial population using randomlygenerated candidate solutions whose edges were restricted to the problem graph's MST proved equally successful. GA configuration options were analyzed using all 9000 test cases and again using only those 403 cases in which the GA was able to find the very best solution for each graph. These analyses were consistent, and resulted in the identification of a single "best" GA configuration which combined the best overall initial population strategy, random seeding algorithms, mutation and crossover strategy. The selected configuration was then further tested using various values of m to ensure that the resulting GA could in fact find betterthanHEF(MST) solutions for the majority of problem instances.

3 
MeasureDriven Algorithm Design and Analysis: A New Approach for Solving NPhard ProblemsLiu, Yang 2009 August 1900 (has links)
NPhard problems have numerous applications in various fields such as networks,
computer systems, circuit design, etc. However, no efficient algorithms have
been found for NPhard problems. It has been commonly believed that no efficient algorithms
for NPhard problems exist, i.e., that P6=NP. Recently, it has been observed
that there are parameters much smaller than input sizes in many instances of NPhard
problems in the real world. In the last twenty years, researchers have been interested
in developing efficient algorithms, i.e., fixedparameter tractable algorithms, for those
instances with small parameters. Fixedparameter tractable algorithms can practically
find exact solutions to problem instances with small parameters, though those
problems are considered intractable in traditional computational theory.
In this dissertation, we propose a new approach of algorithm design and analysis:
discovering better measures for problems. In particular we use two measures instead of
the traditional single measure?input size to design algorithms and analyze their time
complexity. For several classical NPhard problems, we present improved algorithms
designed and analyzed with this new approach,
First we show that the new approach is extremely powerful for designing fixedparameter
tractable algorithms by presenting improved fixedparameter tractable algorithms
for the 3Dmatching and 3Dpacking problems, the multiway cut problem, the feedback vertex set problems on both directed and undirected
graph and the maxleaf problems on both directed and undirected graphs. Most of
our algorithms are practical for problem instances with small parameters.
Moreover, we show that this new approach is also good for designing exact algorithms
(with no parameters) for NPhard problems by presenting an improved exact
algorithm for the wellknown satisfiability problem.
Our results demonstrate the power of this new approach to algorithm design and
analysis for NPhard problems. In the end, we discuss possible future directions on
this new approach and other approaches to algorithm design and analysis.

4 
On Approximation Algorithms for Coloring kColorable GraphsHIRATA, Tomio, ONO, Takao, XIE, Xuzhen 01 May 2003 (has links)
No description available.

5 
Some Problems in OneOperator SchedulingBaki, Mohammed Fazle January 1999 (has links)
A flexible workforce or a versatile machine is employed to perform various types of operations. Often these resources are associated with setups. Whenever a worker or machine switches from processing one type of operation to another a setup time may be required although several operations of a same type can be processed in succession after a single setup. The presence of setups gives rise to the problem of choosing batch sizes that are neither too large nor too small. In the last one and a half decade, many researchers have addressed the problem of scheduling with batching. A majority of articles assumes that there is only one type of scarce resource, which is typically machine. Often there can be two scarce resources such as a worker and a machine or a machine and a tool. We propose a resource constrained scheduling model with a single operator and two or more machines. Whenever the operator changes machine, a setup time is required that may be sequence dependent or sequence independent. We consider the two cases of an open shop and a flow shop. In the open shop case, the order in which a job visits the machines is unrestricted. In the flow shop case, every job must visit the machines in the same order. We consider various scheduling objectives. For variable number of machines, many cases are intractable. We discuss some dominance properties that narrow down the search for an optimal schedule. We present a dynamic programming approach which solves a large number of cases. The running time of the dynamic program is polynomial for a fixed number of machines. For the case of two machines, we show that the dominance properties have a nice interpretation. We develop some algorithms and justify their use by establishing running times, comparing the running times with those of the existing algorithms, and testing the performance of the algorithms.

6 
Robust Sensor Selection Strong DetectabilityNathaniel T. Woodford (5930930) 16 January 2019 (has links)
An unknown input observer provides perfect asymptotic tracking of the state of a system affected by unknown inputs. Such an observer exists (possibly requiring a delay in estimation) if and only if the system satisfies a property known as strong detectability. In this thesis, we consider the problem of selecting (at designtime) a minimum cost subset of sensors from a given set to make a given system strongly detectable. We show this problem is NPhard even when the system is stable. Furthermore, we show it is not possible to approximate the minimum cost within a factor of log(n) in polynomialtime (unless P=NP). However, we prove if a given system (with a selected set of sensors) is already strongly detectable, finding the smallest set of additional sensors to install to obtain a zerodelay observer can be done in polynomial time. Next we consider the problem of attacking a set of deployed sensors to remove the property of strong detectability. We show finding the smallest number of sensors to remove is NPhard. Lastly through simulations, we analyze two greedy approaches for approximating the strong detectability sensor selection problem.

7 
Inapproximability of the EdgeContraction ProblemHIRATA, Tomio, OTSUKI, Hideaki 01 May 2006 (has links)
No description available.

8 
Some Problems in OneOperator SchedulingBaki, Mohammed Fazle January 1999 (has links)
A flexible workforce or a versatile machine is employed to perform various types of operations. Often these resources are associated with setups. Whenever a worker or machine switches from processing one type of operation to another a setup time may be required although several operations of a same type can be processed in succession after a single setup. The presence of setups gives rise to the problem of choosing batch sizes that are neither too large nor too small. In the last one and a half decade, many researchers have addressed the problem of scheduling with batching. A majority of articles assumes that there is only one type of scarce resource, which is typically machine. Often there can be two scarce resources such as a worker and a machine or a machine and a tool. We propose a resource constrained scheduling model with a single operator and two or more machines. Whenever the operator changes machine, a setup time is required that may be sequence dependent or sequence independent. We consider the two cases of an open shop and a flow shop. In the open shop case, the order in which a job visits the machines is unrestricted. In the flow shop case, every job must visit the machines in the same order. We consider various scheduling objectives. For variable number of machines, many cases are intractable. We discuss some dominance properties that narrow down the search for an optimal schedule. We present a dynamic programming approach which solves a large number of cases. The running time of the dynamic program is polynomial for a fixed number of machines. For the case of two machines, we show that the dominance properties have a nice interpretation. We develop some algorithms and justify their use by establishing running times, comparing the running times with those of the existing algorithms, and testing the performance of the algorithms.

9 
Randomized and Deterministic Parameterized Algorithms and Their Applications in BioinformaticsLu, Songjian 2009 December 1900 (has links)
Parameterized NPhard problems are NPhard problems that are associated with
special variables called parameters. One example of the problem is to find simple
paths of length k in a graph, where the integer k is the parameter. We call this
problem the ppath problem. The ppath problem is the parameterized version of
the wellknown NPcomplete problem  the longest simple path problem.
There are two main reasons why we study parameterized NPhard problems.
First, many application problems are naturally associated with certain parameters.
Hence we need to solve these parameterized NPhard problems. Second, if parameters
take only small values, we can take advantage of these parameters to design very
effective algorithms.
If a parameterized NPhard problem can be solved by an algorithm of running
time in form of f(k)nO(1), where k is the parameter, f(k) is independent of n, and
n is the input size of the problem instance, we say that this parameterized NPhard
problem is fixed parameter tractable (FPT). If a problem is FPT and the parameter
takes only small values, the problem can be solved efficiently (it can be solved almost
in polynomial time). In this dissertation, first, we introduce several techniques that can be used to
design efficient algorithms for parameterized NPhard problems. These techniques
include branch and bound, divide and conquer, color coding and dynamic programming,
iterative compression, iterative expansion and kernelization. Then we present
our results about how to use these techniques to solve parameterized NPhard problems,
such as the ppath problem and the pdfeedback vertex set problem.
Especially, we designed the first algorithm of running time in form of f(k)nO(1) for
the pdfeedback vertex set problem. Thus solved an outstanding open problem,
i.e. if the pdfeedback vertex set problem is FPT. Finally, we will introduce how
to use parameterized algorithm techniques to solve the signaling pathway problem and
the motif finding problem from bioinformatics.

10 
Optimization of CodeConstellation for Mary CDMA SystemsChen, YangWen 02 September 2006 (has links)
In this thesis, we propose and evaluate quasioptimal algorithms for solving the codeconstellation optimization problem in Mary CDMA system. The Mary CDMA system is a new CDMA architecture. The more spreading codes used in each user, and the higher bandwidth efficiency can achieve with more bits packed in each symbol. We use a code, which we refer to as ¡§mapping code¡¨, to help form a multidimensional spherical codeconstellation. The M codewords of the mapping code correspond onetoone to the M points on the codeconstellation. Thus, the codeconstellation optimization problem is a combinatorial optimization problem. We present that an exhaustive search (ES) algorithm would have compute and check all possible subset, and then this problem becomes a NPhard. Based on the exhaustive search algorithm, we propose symmetric points search (SPS) algorithm to reduce computation
complexity, but it is not optimal algorithm. In addition, we propose a quasioptimal algorithm, namely Manhattan distance search (MDS) algorithm. Numerical results and comparisons are provided to illustrate that the computation complexity of the Manhattan distance search algorithm increases linearly with dimension of codeconstellation and its performance is better than others.

Page generated in 0.137 seconds