共查询到20条相似文献,搜索用时 46 毫秒
1.
Mohammad Khairul Hasan Hyunwoo Jung Kyung-Yong Chwa 《Journal of Combinatorial Optimization》2008,16(2):155-172
We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c
e
for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d
j
and a set of facilities F⊆V each has nonnegative opening cost f
i
and capacity to serve all client demands. The objective is to open a subset of facilities, say
, to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost
is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in
Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm. 相似文献
2.
Jinjiang Yuan Shisheng Li Ji Tian Ruyan Fu 《Journal of Combinatorial Optimization》2009,17(2):206-213
We consider a single batch machine on-line scheduling problem with delivery times. In this paper on-line means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing
of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been
delivered. For each job J
j
, its processing time and delivery time are denoted by p
j
and q
j
, respectively. We consider two restricted models: (1) the jobs have small delivery times, i.e., for each job J
j
, q
j
≤p
j
; (2) the jobs have agreeable processing and delivery times, i.e., for any two jobs J
i
and J
j
, p
i
>p
j
implies q
i
≥q
j
. We provide an on-line algorithm with competitive ratio
for both problems, and the results are the best possible.
Project supported by NSFC (10671183). 相似文献
3.
Onur Seref O. Erhun Kundakcioglu Oleg A. Prokopyev Panos M. Pardalos 《Journal of Combinatorial Optimization》2009,17(1):3-20
In this study we introduce a generalized support vector classification problem: Let X i , i=1,…,n be mutually exclusive sets of pattern vectors such that all pattern vectors x i,k , k=1,…,|X i | have the same class label y i . Select only one pattern vector $x_{i,k^{*}}In this study we introduce a generalized support vector classification problem: Let X
i
, i=1,…,n be mutually exclusive sets of pattern vectors such that all pattern vectors x
i,k
, k=1,…,|X
i
| have the same class label y
i
. Select only one pattern vector
from each set X
i
such that the margin between the set of selected positive and negative pattern vectors are maximized. This problem is formulated
as a quadratic mixed 0-1 programming problem, which is a generalization of the standard support vector classifiers. The quadratic
mixed 0-1 formulation is shown to be
-hard. An alternative approach is proposed with the free slack concept. Primal and dual formulations are introduced for linear
and nonlinear classification. These formulations provide flexibility to the separating hyperplane to identify the pattern
vectors with large margin. Iterative elimination and direct selection methods are developed to select such pattern vectors
using the alternative formulations. These methods are compared with a na?ve method on simulated data. The iterative elimination
method is also applied to neural data from a visuomotor categorical discrimination task to classify highly cognitive brain
activities. 相似文献
4.
Wil Michiels Jan Korst Emile Aarts Jan van Leeuwen 《Journal of Combinatorial Optimization》2007,13(1):19-32
We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this well-studied problem the Largest Differencing Method of Karmarkar and Karp outperforms other existing polynomial-time approximation algorithms from an average-case perspective. For m ≥ 3 the worst-case performance of the Largest Differencing Method has remained a challenging open problem. In this paper we show that the worst-case performance ratio is bounded between . For fixed m we establish further refined bounds in terms of n. 相似文献
5.
Cai Mao-Cheng 《Journal of Combinatorial Optimization》1999,3(4):465-474
In this paper we study the inverse problem of matroid intersection: Two matroids M
1 = (E,
1) and M
2 = (E,
2), their intersection B, and a weight function w on E are given. We try to modify weight w, optimally and with bounds, such that B becomes a maximum weight intersection under the modified weight. It is shown in this paper that the problem can be formulated as a combinatorial linear program and can be further transformed into a minimum cost circulation problem. Hence it can be solved by strongly polynomial time algorithms. We also give a necessary and sufficient condition for the feasibility of the problem. Finally we extend the discussion to the version of the problem with Multiple Intersections. 相似文献
6.
Hung Q. Ngo 《Journal of Combinatorial Optimization》2008,15(1):61-76
In this paper, we formulate and investigate the following problem: given integers d,k and r where k>r≥1,d≥2, and a prime power q, arrange d hyperplanes on
to maximize the number of r-dimensional subspaces of
each of which belongs to at least one of the hyperplanes. The problem is motivated by the need to give tighter bounds for
an error-tolerant pooling design based on finite vector spaces.
This work is partially supported by NSF CAREER Award CCF-0347565. 相似文献
7.
Given d>2 and a set of n grid points Q in ℜ
d
, we design a randomized algorithm that finds a w-wide separator, which is determined by a hyper-plane, in
sublinear time such that Q has at most
points on either side of the hyper-plane, and at most
points within
distance to the hyper-plane, where c
d
is a constant for fixed d. In particular, c
3=1.209. To our best knowledge, this is the first sublinear time algorithm for finding geometric separators. Our 3D separator
is applied to derive an algorithm for the protein side-chain packing problem, which improves and simplifies the previous algorithm
of Xu (Research in computational molecular biology, 9th annual international conference, pp. 408–422, 2005).
This research is supported by Louisiana Board of Regents fund under contract number LEQSF(2004-07)-RD-A-35.
The part of this research was done while Bin Fu was associated with the Department of Computer Science, University of New
Orleans, LA 70148, USA and the Research Institute for Children, 200 Henry Clay Avenue, New Orleans, LA 70118, USA. 相似文献
8.
Teresa W. Haynes Michael A. Henning Lucas C. van der Merwe 《Journal of Combinatorial Optimization》2009,18(1):23-37
Let G be a graph and
be the complement of G. The complementary prism
of G is the graph formed from the disjoint union of G and
by adding the edges of a perfect matching between the corresponding vertices of G and
. For example, if G is a 5-cycle, then
is the Petersen graph. In this paper we consider domination and total domination numbers of complementary prisms. For any
graph G,
and
, where γ(G) and γ
t
(G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds.
Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
9.
In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine
whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time
unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved
to
when the underlying graph G is an interval graph. 相似文献
10.
For plane triangulations, it has been proved that there exists a plane triangulation G with n vertices such that for any st-orientation of G, the length of the longest directed paths of G in the st-orientation is
(Zhang and He in Lecture Notes in Computer Science, vol. 3383, pp. 425–430, 2005). In this paper, we prove the bound
is optimal by showing that every plane triangulation G with n-vertices admits an st-orientation with the length of its longest directed paths bounded by
. In addition, this st-orientation is constructible in linear time. A by-product of this result is that every plane graph G with n vertices admits a visibility representation with height
, constructible in linear time, which is also optimal.
A preliminary version of this paper was presented at AAIM 2007. 相似文献
11.
On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time 总被引:4,自引:1,他引:3
Scheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times C
j is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time w
j
C
j. We provide a linear time on-line algorithm for the unrestrictive model (i.e., b n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + )-competitive on-line algorithm for any > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees. 相似文献
12.
Hyunwoo Jung Mohammad Khairul Hasan Kyung-Yong Chwa 《Journal of Combinatorial Optimization》2009,18(3):258-271
In the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c e on the edges, a set of facilities ??V, a set of demands (i.e., clients) $\mathcal{D}\subseteq VIn the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c
e
on the edges, a set of facilities ℱ⊆V, a set of demands (i.e., clients)
D í V\mathcal{D}\subseteq V
, and a parameter M≥1. Each facility i has a nonnegative opening cost f
i
and each client j has d
j
units of demand. Our objective is to open some facilities, say F⊆ℱ, assign each demand j to some open facility i(j)∈F and connect all open facilities using a Steiner tree T such that the total cost, which is
?i ? Ffi+?j ? Ddjci(j)j+M?e ? Tce\sum_{i\in F}f_{i}+\sum_{j\in \mathcal{D}}d_{j}c_{i(j)j}+M\sum_{e\in T}c_{e}
, is minimized.
We present a primal-dual 6.55-approximation algorithm for the ConFL problem which improves the previous primal-dual 8.55-approximation
algorithm given by Swamy and Kumar (Algorithmica 40:245–269, 2004). 相似文献
13.
In the binary single constraint Knapsack Problem, denoted KP, we are given a knapsack of fixed capacity c and a set of n items. Each item j, j = 1,...,n, has an associated size or weight wj and a profit pj. The goal is to determine whether or not item j, j = 1,...,n, should be included in the knapsack. The objective is to maximize the total profit without exceeding the capacity c of the knapsack. In this paper, we study the sensitivity of the optimum of the KP to perturbations of either the profit or the weight of an item. We give approximate and exact interval limits for both cases
(profit and weight) and propose several polynomial time algorithms able to reach these interval limits. The performance of
the proposed algorithms are evaluated on a large number of problem instances. 相似文献
14.
We study minimum-cost sensor placement on a bounded 3D sensing field, R, which comprises a number of discrete points that may or may not be grid points. Suppose we have ℓ types of sensors available
with different sensing ranges and different costs. We want to find, given an integer σ ≥ 1, a selection of sensors and a subset
of points to place these sensors such that every point in R is covered by at least σ sensors and the total cost of the sensors is minimum. This problem is known to be NP-hard. Let ki denote the maximum number of points that can be covered by a sensor of the ith type. We present in this paper a polynomial-time approximation algorithm for this problem with a proven approximation ratio
. In applications where the distance of any two points has a fixed positive lower bound, each ki is a constant, and so we have a polynomial-time approximation algorithms with a constant guarantee. While γ may be large,
we note that it is only a worst-case upper bound. In practice the actual approximation ratio is small, even on randomly generated
points that do not have a fixed positive minimum distance between them. We provide a number of numerical results for comparing
approximation solutions and optimal solutions, and show that the actual approximation ratios in these examples are all less
than 3, even though γ is substantially larger.
This research was supported in part by NSF under grant CCF-04080261 and by NSF of China under grant 60273062. 相似文献
15.
Given a directed graph D=(V,A) with a set of d specified vertices S={s 1,…,s d }?V and a function f : S→? where ? denotes the set of positive integers, we consider the problem which asks whether there exist ∑ i=1 d f(s i ) in-trees denoted by \(T_{i,1},T_{i,2},\ldots,T_{i,f(s_{i})}\) for every i=1,…,d such that \(T_{i,1},\ldots,T_{i,f(s_{i})}\) are rooted at s i , each T i,j spans vertices from which s i is reachable and the union of all arc sets of T i,j for i=1,…,d and j=1,…,f(s i ) covers A. In this paper, we prove that such set of in-trees covering A can be found by using an algorithm for the weighted matroid intersection problem in time bounded by a polynomial in ∑ i=1 d f(s i ) and the size of D. Furthermore, for the case where D is acyclic, we present another characterization of the existence of in-trees covering A, and then we prove that in-trees covering A can be computed more efficiently than the general case by finding maximum matchings in a series of bipartite graphs. 相似文献
16.
In this paper, we study the Radiation hybrid map construction ( $\mathsf{{RHMC} }$ ) problem which is about reconstructing a genome from a set of gene clusters. The problem is known to be $\mathsf{{NP} }$ -complete even when all gene clusters are of size two and the corresponding problem ( $\mathsf{{RHMC}_2 }$ ) admits efficient constant-factor approximation algorithms. In this paper, for the first time, we consider the more general case when the gene clusters can have size either two or three ( $\mathsf{{RHMC}_3 }$ ). Let ${p\text{- }\mathsf {RHMC} }$ be a parameterized version of $\mathsf{{RHMC} }$ where the parameter is the size of solution. We present a linear kernel for ${p\text{- }\mathsf {RHMC}_3 }$ of size $22k$ that when combined with a bounded search-tree algorithm, gives an FPT algorithm running in $O(6^kk+n)$ time. For ${p\text{- }\mathsf {RHMC}_3 }$ we present a bounded search tree algorithm which runs in $O^*(2.45^k)$ time, greatly improving the previous bound using weak kernels. 相似文献
17.
Let γ
t
{k}(G) denote the total {k}-domination number of graph G, and let
denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices,
. As a corollary of this result, we have
for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005).
The work was supported by NNSF of China (No. 10701068 and No. 10671191). 相似文献
18.
We introduce an exponential neighborhood for the Vehicle Routing Problem (vrp) with unit customers’ demands, and we show that it can be explored efficiently in polynomial time by reducing its exploration to a particular
case of the Restricted Complete Matching (rcm) problem that we prove to be polynomial time solvable using flow techniques. Furthermore, we show that in the general case
with non-unit customers’ demands the exploration of the neighborhood becomes an
-hard problem. 相似文献
19.
In the partial degree bounded edge packing problem (PDBEP), the input is an undirected graph \(G=(V,E)\) with capacity \(c_v\in {\mathbb {N}}\) on each vertex v. The objective is to find a feasible subgraph \(G'=(V,E')\) maximizing \(|E'|\), where \(G'\) is said to be feasible if for each \(e=\{u,v\}\in E'\), \(\deg _{G'}(u)\le c_u\) or \(\deg _{G'}(v)\le c_v\). In the weighted version of the problem, additionally each edge \(e\in E\) has a weight w(e) and we want to find a feasible subgraph \(G'=(V,E')\) maximizing \(\sum _{e\in E'} w(e)\). The problem is already NP-hard if \(c_v = 1\) for all \(v\in V\) (Zhang in: Proceedings of the joint international conference on frontiers in algorithmics and algorithmic aspects in information and management, FAW-AAIM 2012, Beijing, China, May 14–16, pp 359–367, 2012). In this paper, we introduce a generalization of the PDBEP problem. We let the edges have weights as well as demands, and we present the first constant-factor approximation algorithms for this problem. Our results imply the first constant-factor approximation algorithm for the weighted PDBEP problem, improving the result of Aurora et al. (FAW-AAIM 2013) who presented an \(O(\log n)\)-approximation for the weighted case. We also study the weighted PDBEP problem on hypergraphs and present a constant factor approximation if the maximum degree of the hypergraph is bounded above by a constant. We study a generalization of the weighted PDBEP problem with demands where each edge additionally specifies whether it requires at least one, or both its end-points to not exceed the capacity. The objective is to pick a maximum weight subset of edges. We give a constant factor approximation for this problem. We also present a PTAS for the weighted PDBEP problem with demands on H-minor free graphs, if the demands on the edges are bounded by polynomial. We show that the PDBEP problem is APX-hard even for bipartite graphs with \(c_v = 1, \; \forall v\in V\) and having degree at most 3. 相似文献
20.
Let G=(V,E) be an undirected graph in which every vertex v∈V is assigned a nonnegative integer w(v). A w-packing is a collection of cycles (repetition allowed) in G such that every v∈V is contained at most w(v) times by the members of . Let 〈w〉=2|V|+∑
v∈V
⌈log (w(v)+1)⌉ denote the binary encoding length (input size) of the vector (w(v): v∈V)
T
. We present an efficient algorithm which finds in O(|V|8〈w〉2+|V|14) time a w-packing of maximum cardinality in G provided packing and covering cycles in G satisfy the ℤ+-max-flow min-cut property. 相似文献