BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Donglei Du

Donglei Du appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputer Science and Game TheoryArtificial IntelligenceDiscrete MathematicsMachine Learningmath.OC

Catalog footprint

What is connected

6works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2022arXiv

An improved approximation algorithm for maximizing a DR-submodular function over a convex set

Maximizing a DR-submodular function subject to a general convex set is an NP-hard problem arising from many applications in combinatorial optimization and machine learning. While it is highly desirable to design efficient approximation algorithms under this general setting where neither the objective function is monotonic nor the feasible set is down-closed, our main contribution is to present a 0.25-approximation Frank-Wolfe type of algorithm with a sub-exponential time-complexity under the value oracle model.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization

We propose a two-phase systematical framework for approximation algorithm design and analysis via Lyapunov function. The first phase consists of using Lyapunov function as an input and outputs a continuous-time approximation algorithm with a provable approximation ratio. The second phase then converts this continuous-time algorithm to a discrete-time algorithm with almost the same approximation ratio along with provable time complexity. One distinctive feature of our framework is that we only need to know the parametric form of the Lyapunov function whose complete specification will not be decided until the end of the first phase by maximizing the approximation ratio of the continuous-time algorithm. Some immediate benefits of the Lyapunov function approach include: (i) unifying many existing algorithms; (ii) providing a guideline to design and analyze new algorithms; and (iii) offering new perspectives to potentially improve existing algorithms. We use various submodular maximization problems as running examples to illustrate our framework.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Population Monotonicity of Independent Set Games

An independent set game is a cooperative game defined on graphs and dealing with profit-sharing in maximum independent set problems. A population monotonic allocation scheme is a rule specifying how to share the profit of each coalition among its participants such that every participant is better off when the coalition expands. In this paper, we provide a necessary and sufficient characterization for population monotonic allocation schemes in independent set games. Moreover, our characterization can be verified efficiently.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximation algorithms for general cluster routing problem

Graph routing problems have been investigated extensively in operations research, computer science and engineering due to their ubiquity and vast applications. In this paper, we study constant approximation algorithms for some variations of the general cluster routing problem. In this problem, we are given an edge-weighted complete undirected graph $G=(V,E,c),$ whose vertex set is partitioned into clusters $C_{1},\dots ,C_{k}.$ We are also given a subset $V'$ of $V$ and a subset $E'$ of $E.$ The weight function $c$ satisfies the triangle inequality. The goal is to find a minimum cost walk $T$ that visits each vertex in $V'$ only once, traverses every edge in $E'$ at least once and for every $i\in [k]$ all vertices of $C_i$ are traversed consecutively.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An improved approximation algorithm for k-median problem using a new factor-revealing LP

The k-median problem is a well-known strongly NP-hard combinatorial optimization problem of both theoretical and practical significance. The previous best approximation ratio for this problem is 2.611+ε(Bryka et al. 2014) based on an (1, 1.95238219) bi-factor approximation algorithm for the classical facility location problem (FLP). This work offers an improved algorithm with an approximation ratio 2.592 +εbased on a new (1, 1.93910094) bi-factor approximation algorithm for the FLP.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Copula-based Randomized Mechanisms for Truthful Scheduling on Two Unrelated Machines

We design a Copula-based generic randomized truthful mechanism for scheduling on two unrelated machines with approximation ratio within $[1.5852, 1.58606]$, offering an improved upper bound for the two-machine case. Moreover, we provide an upper bound 1.5067711 for the two-machine two-task case, which is almost tight in view of the lower bound of 1.506 for the scale-free truthful mechanisms [4]. Of independent interest is the explicit incorporation of the concept of Copula in the design and analysis of the proposed approximation algorithm. We hope that techniques like this one will also prove useful in solving other problems in the future.

0 citations0 reviewsNo code linkedOpen access