共查询到20条相似文献,搜索用时 31 毫秒
1.
M. Y. Chan Danny Z. Chen Francis Y. L. Chin Cao An Wang 《Journal of Combinatorial Optimization》2006,11(4):435-443
This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given point
set V of size n in the k-dimensional space (k-D) for k = 2,3. The NNE-graph provides another way of connecting points in a communication network, which has lower expected degree
at each point and shorter total length of connections with respect to those using Delaunay triangulation. In fact, the NNE-graph
can also be used as a tool to test whether a point set is randomly generated or has some particular properties.
We show that in 2-D the NNE-graph can be constructed in optimal
time in the worst case. We also present an
time algorithm, where d is the
-th largest degree in the utput NNE-graph. The algorithm is optimal when
. The algorithm is also sensitive to the structure of the NNE-graph, for instance when
, the number of edges in NNE-graph is bounded by
for any value g with
. We finally propose an
time algorithm for the problem in 3-D, where d and
are the
-th largest vertex degree and the largest vertex degree in the NNE-graph, respectively. The algorithm is optimal when the
largest vertex degree of the NNE-graph
is
. 相似文献
2.
For a Boolean function f given by its truth table (of length
) and a parameter s the problem considered is whether there is a Boolean function g
-equivalent to f, i.e.,
, and computed by a circuit of size at most s. In this paper we investigate the complexity of this problem and show that for specific values of
it is unlikely to be in P/poly. Under the same assumptions we also consider the optimization variant of the problem and prove its inapproximability. 相似文献
3.
Yigal Bejerano Joseph Naor Alexander Sprintson 《Journal of Combinatorial Optimization》2006,12(1-2):17-34
We study efficient algorithms for establishing reliable connections with bandwidth guarantees in communication networks. In
the normal mode of operation, each connection uses a primary path to deliver packets from the source to the destination. To ensure continuous operation in the event of an edge failure,
each connection uses a set of backup bridges, each bridge protecting a portion of the primary path. To meet the bandwidth requirement of the connection, a certain amount
of bandwidth must be allocated the edges of the primary path, as well as on the backup edges. In this paper, we focus on minimizing
the amount of required backup allocation by sharing backup bandwidth among different connections. We consider efficient sharing schemes that require only partial information about the current state of the network. Specifically, the only information available for each edge is the total
amount of primary allocation and the cost of allocating backup bandwidth on this edge. We consider the problem of finding
a minimum cost backup allocation together with a set of bridges for a given primary path. We prove that this problem is
NP-hard and present an approximation algorithm whose performance is within
of the optimum, where n is the number of edges in the primary path. We also consider the problem of finding both a primary path and backup allocation
of minimal total cost.
A preliminary version of this paper appears in the Proceedings of 13th Annual European Symposium on Algorithms - ESA 2005,
Mallorca, Spain.
J. (Seffi) Naor: This research is supported in part by a foundational and strategical research grant from the Israeli Ministry
of Science, and by a US-Israel BSF Grant 2002276. 相似文献
4.
It is known that
(Cai, 2001). The reverse direction of whether ZPPNP is contained in
remains open. We show that if the zero-error algorithm is allowed to ask only one query to the NP oracle (for any input and
random string), then it can be simulated in
. That is, we prove that
. Next we consider whether the above result can be improved as
and point out a difficulty in doing so. Via a simple proof, we observe that BPP ⊆ ZPPNP[1] (a result implicitly proven in some prior work). Thus, achieving the above improvement would imply BPP ⊆ PNP, settling a long standing open problem.
We then argue that the above mentioned improvement can be obtained for the next level of the polynomial time hierarchy. Namely,
we prove that
. On the other hand, by adapting our proof of our main result it can be shown that
. For the purpose of comparing these two results, we prove that
. We conclude by observing that the above claims extend to the higher levels of the hierarchy: for k ≥ 2,
and
.
Research supported in part by NSF grant CCR-0208013. A preliminary version of the paper was presented at COCOON′05 Cai and
Chakaravarthy (2005).
Part of the research was conducted while the author was at the University of Wisconsin, Madison. 相似文献
5.
Yoshiyuki Kusakari Daisuke Masubuchi Takao Nishizeki 《Journal of Combinatorial Optimization》2001,5(2):249-266
Let G = (V,E) be a plane graph with nonnegative edge weights, and let
be a family of k vertex sets
, called nets. Then a noncrossing Steiner forest for
in G is a set
of k trees
in G such that each tree
connects all vertices, called terminals, in net N
i, any two trees in
do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time
if G has n vertices and each net contains a bounded number of terminals. 相似文献
6.
We show several hardness results for the Minimum Hacking problem, which roughly can be described as the problem of finding the best way to compromise a target node given a few initial compromised nodes in a network. We give several reductions to show that Minimum Hacking is not approximable to within
where δ = 1−
c n, for any c < 1/2. We also analyze some heuristics on this problem. 相似文献
7.
We present an O(n3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically
, where n is the number of vertices in the input (undirected) graph. This improves the previous best.Part of work done while visiting City University of Hong Kong. 相似文献
8.
Center and Distinguisher for Strings with Unbounded Alphabet 总被引:2,自引:0,他引:2
Consider two sets
and
of strings of length L with characters from an unbounded alphabet , i.e., the size of is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of
is a string that minimizes the maximum of Hamming1
distance(s, s*) over all string s : s
. In contrast, a farthest string t* from
maximizes the minimum of Hamming distance(t*,t) over all elements t: t
. A distinguisher of
from
is a string that is close to every string in
and far away from any string in
. We obtain polynomial time approximation schemes to settle the above problems. 相似文献
9.
Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present,
is the best known approximation ratio achievable in polynomial time for SBR. A very closely related problem, called Breakpoint Graph Decomposition (BGD), calls for a largest collection of edge disjoint cycles in a suitably-defined graph. It has been shown that for almost all instances SBR is equivalent to BGD, in the sense that any solution of the latter corresponds to a solution of the former having the same value. In this paper, we show how to improve the approximation ratio achievable in polynomial time for BGD, from the previously known
to
for any > 0. Combined with the results in (Caprara, Journal of Combinatorial Optimization, vol. 3, pp. 149–182, 1999b), this yields the same approximation guarantee for n! – O((n – 5)!) out of the n! instances of SBR on permutations with n elements. Our result uses the best known approximation algorithms for Stable Set on graphs with maximum degree 4 as well as for Set Packing where the maximum size of a set is 6. Any improvement in the ratio achieved by these approximation algorithms will yield an automatic improvement of our result. 相似文献
10.
Order Consolidation for Batch Processing 总被引:3,自引:0,他引:3
We consider the batch processing of orders where either whole or part of a single order or a specific pair of different orders may be grouped in a batch with a fixed capacity. The problem can be modelled by a graph G = (V,E), where each node v
V corresponds to an order, its weight w(v) corresponds to the amount of ordered quantity and a pair of orders, say u and v may be grouped in a batch if there exists the edge (u,v)
E. The objective is to maximize the number of batches filled up to its capacity
. In this paper, we prove that the problem is NP-hard and, moreover, that no PTAS exists unless P = NP. Then, an optimal algorithm is developed with running time O(|V|log |V|) for the special case when G is a tree. 相似文献
11.
Hiroshi Nagamochi Takashi Shiraki Toshihide Ibaraki 《Journal of Combinatorial Optimization》2001,5(2):175-212
Given a finite set V and a set function
, we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function
together has value at least 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in
time, where
is the time to compute the value of f(X) for a subset
. 相似文献
12.
We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems
in graphs, MINIMUM EDGE DOMINATING SET and MINIMUM MAXIMAL MATCHING. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than
. The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs.
An extended abstract of this paper was accepted at the 14th Annual International Symposium on Algorithms and Computation,
ISAAC 2003. 相似文献
13.
Given a graph G = (V,E), we define the locally optimal independent sets asfollows. Let S be an independent set and T be a subset of V such that S T = and (S)
T, where (S) is defined as the neighbor set of S. A minimum dominating set of S in T is defined as TD(S)
T such that every vertex of S is adjacent to a vertex inTD(S) and TD(S) has minimum cardinality. An independent setI is called r-locally optimal if it is maximal and there exists noindependent set S
V\I with |ID (S)| r such that|S| >|I (S)|.In this paper, we demonstrate that for k-claw free graphs ther-locally optimal independent sets is found in polynomial timeand the worst case is bounded by
, where I and I* are a locally optimal and an optimal independent set,respectively. This improves the best published bound by Hochbaum (1983) bynearly a factor of two. The bound is proved by LP duality and complementaryslackness. We provide an efficientO(|V|r+3) algorithm to find an independent set which is notnecessarily r-locally optimal but is guarantteed with the above bound. Wealso present an algorithm to find a r-locally optimal independent set inO(|V|r(k-1)+3) time. 相似文献
14.
For a Boolean function
given by a Boolean formula (or a binary circuit) S we discuss the problem of building a Boolean formula (binary circuit) of minimal size, which computes the function g equivalent to
, or -equivalent to
, i.e.,
. In this paper we prove that if P NP then this problem can not be approximated with a good approximation ratio by a polynomial time algorithm. 相似文献
15.
Let D = (V, A) be a directed graph, for each vertex v V, let +(v) and – (v) denote the sets of arcs leaving and entering v,
and
be intersecting families on +(v) and –(v), respectively, and
and
be submodular functions on intersecting pairs. A flow f : A R is feasible if
Given a cost function c on A, the minimum cost polymatroidal flow problem is to find a feasible flow f with minimum cost {c(e)f(e)ve A}, it is a significant generalization of many combinatorial optimization problems.Given a feasible flow f*, cost and restriction functions on A, the inverse polymatroidal flow problem is to modify c, optimally and with bounds, such that f* becomes a minimum cost polymatroidal flow under the modified cost.It is shown in this paper that the inverse 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 efficiently by strongly polynomial combinatorial algorithms. We also give a necessary and sufficient condition for the feasibility of the inverse problem. 相似文献
16.
Nanda Piersma 《Journal of Combinatorial Optimization》1999,3(1):31-50
The solution value
of a stochastic version of the capacitated facility location problem is studied. It is shown that, for large numbers of customers n, the value of
can be closely approximated by , where the constant is identified as a function of the parameters of the underlying stochastic model. Furthermore, an extensive probabilistic analysis is performed on the difference
that includes an exponential inequality on the tail distribution, a classification of the speed of convergence and a central limit theorem. 相似文献
17.
Cynthia A. Phillips Andreas S. Schulz David B. Shmoys Cliff Stein Joel Wein 《Journal of Combinatorial Optimization》1998,1(4):413-426
We consider the problem of scheduling n jobs withrelease dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion time of the optimal nonpreemptive schedule to that of the optimal preemptive schedule is at most 7/3, improving a bound of
Shmoys and Wein. 相似文献
18.
Approximation Algorithms in Batch Processing 总被引:23,自引:0,他引:23
Xiaotie Deng Chung Keung Poon Yuzhong Zhang 《Journal of Combinatorial Optimization》2003,7(3):247-257
A polynomial approximation scheme for minimizing makespan in a batch processing system under dynamic job arrivals is presented. A lower bound of
on the competitive ratio of any on-line algorithm is proved. This is matched by an on-line algorithm for the special case of unbounded machine capacity. 相似文献
19.
Hypergraph 2-colorability, also known as set splitting, is a widely studied problem in graph theory. In this paper we study the maximization version of the same. We recast the problem as a special type of satisfiability problem and give approximation algorithms for it. Our results are valid for hypergraph 2-colorability, set splitting and MAX-CUT (which is a special case of hypergraph 2-colorability) because the reductions are approximation preserving. Here we study the MAXNAESP problem, the optimal solution to which is a truth assignment of the literals that maximizes the number of clauses satisfied. As a main result of the paper, we show that any locally optimal solution (a solution is locally optimal if its value cannot be increased by complementing assignments to literals and pairs of literals) is guaranteed a performance ratio of
. This is an improvement over the ratio of
attributed to another local improvement heuristic for MAX-CUT (C. Papadimitriou, Computational Complexity, Addison Wesley, 1994). In fact we provide a bound of
for this problem, where k 3 is the minimum number of literals in a clause. Such locally optimal algorithms appear to subsume typical greedy algorithms that have been suggested for problems in the general domain of satisfiability. It should be noted that the NAESP problem where each clause has exactly two literals, is equivalent to MAX-CUT. However, obtaining good approximation ratios using semi-definite programming techniques (M. Goemans and D.P. Williamson, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994a, pp. 422–431) appears difficult. Also, the randomized rounding algorithm as well as the simple randomized algorithm both (M. Goemans and D.P. Williamson, SIAM J. Disc. Math, vol. 7, pp. 656–666, 1994b) yield a bound of
for the MAXNAESP problem. In contrast to this, the algorithm proposed in this paper obtains a bound of
for this problem. 相似文献
20.
Nguyen Bao Nguyen C. Thach Nguyen Wing-Kin Sung 《Journal of Combinatorial Optimization》2007,13(3):223-242
Consider two phylogenetic networks and ’ of size n. The tripartition-based distance finds the proportion of tripartitions which are not shared by and ’. This distance is proposed by Moret et al. (2004) and is a generalization of Robinson-Foulds distance, which is orginally
used to compare two phylogenetic trees. This paper gives an -time algorithm to compute this distance, where h is the number of hybrid nodes in and ’ while k is the maximum number of hybrid nodes among all biconnected components in and ’. Note that $k \ll h \ll n$ in a phylogenetic network. In addition, we propose algorithms for comparing galled-trees, which
are an important, biological meaningful special case of phylogenetic network. We give an $O(n)$-time algorithm for comparing
two galled-trees. We also give an -time algorithm for comparing a galled-tree with another general network, where h and k are the number of hybrid nodes in the latter network and its biggest biconnected component respectively. 相似文献