10045838
Algorithms for finding distance-edge-colorings of graphs
For a bounded integer @?, we wish to color all edges of a graph G so that any two edges within distance @? have different colors. Such a coloring is called a distance-edge-coloring or an @?-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.
32325022
Algorithms for Finding Distance-Edge-Colorings of Graphs
For a bounded integer l, we wish to color all edges of a graph G so that any two edges within distance l have different colors. Such a coloring is called a distance-edge-coloring or an l-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.
2226240
Partitioning Trees of Supply and Demand
Assume that a tree T has a number ns of "supply vertices" and all the other vertices are "demand vertices." Each supply vertex is assigned a positive number called a supply, while each demand vertex is assigned a positive number called a demand. One wish to partition T into exactly ns subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in the subtree. The "partition problem" is a decision problem to ask whether T has such a partition. The "maximum partition problem" is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. First is a linear-time algorithm for the partition problem. Second is a pseudo-polynomial-time algorithm for the maximum partition problem. Third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem.
40274616
On the spectra of certain distance-regular graphs
Let r be an undirected graph whose vertex-set V(F) is the set (ZJ~ , u2 ,..., v,>. The adjacency matrix of I’ is the n x n matrix A = A(r), over the complex number field, whose entries aij are given by a,j = 1 if vi and vi are adjacent, = 0 otherwise. DEFINITION 1. The spectrum of r is the set of distinct eigenvalues 4l , 4 ,**-> Od of A(F), together with their multiplicities, written m(&), m(4),..., m(0,). Since r is undirected, A is symmetric, and so the Bi are all real numbers. We arrange the Bi in increasing order, namely, 0, < O1 < *.. < e dMany studies have been done on the spectra of graphs by many mathematicians. Some of them may be found, for instance, in Biggs [2].
15889327
Towards Better Approximation of Winner Determination for Combinatorial Auctions with Large Number of Bids
We propose new approximate algorithms for combinatorial auctions with massively large number of (more than 100,000) bids. In this paper, we focus on a more practical approximated algorithm in the context of revenue maximization. We propose a hill-climbing greedy algorithm, a SA-like random search algorithm, and their enhancement for searching multiple key parameter values. The experimental results demonstrate that our algorithms perform approximately 0.997 optimality compared with the optimal solutions and better than previously presented approximated algorithms. We also demonstrate that our algorithms are a kind of anytime algorithm that bring better results in shorter computational time that can be applied to large and dynamic electronic markets.
8383423
A Support Method for Qualitative Simulation-Based Learning System
In this paper, we mainly present a support method of our proposed e-learning system. We employ qualitative simulations because this lets the learners understand the conceptual principles in economic dynamics. First, we define some qualitative values employed on simulation graph model that consists of nodes and arcs. Then, we show the support method using our learning system based on qualitative simulation.
7078795
Multi-issue Negotiation Protocol for Agents: Exploring Nonlinear Utility Spaces
Multi-issue negotiation protocols have been studied widely and represent a promising field since most negotiation problems in the real world involve interdependent multiple issues. The vast majority of this work has assumed that negotiation issues are independent, so agents can aggregate the utilities of the issue values by simple summation, producing linear utility functions. In the real world, however, such aggregations are often unrealistic. We cannot, for example, just add up the value of car's carburetor and the value of car's engine when engineers negotiate over the design a car. These value of these choices are interdependent, resulting in nonlinear utility functions. In this paper, we address this important gap in current negotiation techniques. We propose a negotiation protocol where agents employ adjusted sampling to generate proposals, and a bidding-based mechanism is used to find social-welfare maximizing deals. Our experimental results show that our method substantially outperforms existing methods in large non-linear utility spaces like those found in real world contexts.
20000085
Toward a Large Scale E-Market: A Greedy and Local Search Based Winner Determination
Combinatorial auction is one of the most popular market mechanisms and it has a huge effect on electronic markets and political strategies. On large scale e-markets, we need a good approximation algorithm for winner determination that is robust for changing the distribution and the number of bids in an auction. We proposed approximate algorithms for combinatorial auctions with massively large number of (more than 100,000) bids. In this paper, we show the robustness of our winner determination algorithms for combinatorial auctions with large number of bids. Experimental results demonstrate that our proposed algorithms are robust on changing the distribution and the number of bids in an auction. Finally, we shortly describe a theoretical limitation about our algorithms that concerns with giving truthfulness of the auction mechanism.