BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Chenchen Wu

Chenchen Wu contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsBiomoleculesDiscrete MathematicsMachine Learningmath.COmath.OCNetworking and Internet Architecturephysics.chem-ph

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Maximizing Modular plus Non-monotone Submodular Functions

The research problem in this work is the relaxation of maximizing non-negative submodular plus modular with the entire real number domain as its value range over a family of down-closed sets. We seek a feasible point $\mathbf{x}^*$ in the polytope of the given constraint such that $\mathbf{x}^*\in\arg\max_{\mathbf{x}\in\mathcal{P}\subseteq[0,1]^n}F(\mathbf{x})+L(\mathbf{x})$, where $F$, $L$ denote the extensions of the underlying submodular function $f$ and modular function $\ell$. We provide an approximation algorithm named \textsc{Measured Continuous Greedy with Adaptive Weights}, which yields a guarantee $F(\mathbf{x})+L(\mathbf{x})\geq \left(1/e-\mathcal{O}(ε)\right)\cdot f(OPT)+\left(\frac{β-e}{e(β-1)}-\mathcal{O}(ε)\right)\cdot\ell(OPT)$ under the assumption that the ratio of non-negative part within $\ell(OPT)$ to the absolute value of its negative part is demonstrated by a parameter $β\in[0, \infty]$, where $OPT$ is the optimal integral solution for the discrete problem. It is obvious that the factor of $\ell(OPT)$ is $1$ when $β=0$, which means the negative part is completely dominant at this time; otherwise the factor is closed to $1/e$ whe $β\rightarrow\infty$. Our work first breaks the restriction on the specific value range of the modular function without assuming non-positivity or non-negativity as previous results and quantifies the relative variation of the approximation guarantee for optimal solutions with arbitrary structure. Moreover, we also give an analysis for the inapproximability of the problem we consider. We show a hardness result that there exists no polynomial algorithm whose output $S$ satisfies $f(S)+\ell(S)\geq0.478\cdot f(OPT)+\ell(OPT)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Molcontroller: a VMD Graphical User Interface for Manipulating Molecules

Visual Molecular Dynamics (VMD) is one of the most widely used molecular graphics software in the community of theoretical simulations. So far, however, it still lacks a graphical user interface (GUI) for molecular manipulations when doing some modeling tasks. For instance, translation or rotation of a selected molecule(s) or part(s) of a molecule, which are currently only can be achieved using tcl scripts. Here, we use tcl script develop a user-friendly GUI for VMD, named Molcontroller, which is featured by allowing users to quickly and conveniently perform various molecular manipulations. This GUI might be helpful for improving the modeling efficiency of VMD users.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Online Joint Placement and Allocation of Virtual Network Functions with Heterogeneous Servers

Network Function Virtualization (NFV) is a promising virtualization technology that has the potential to significantly reduce the expenses and improve the service agility. NFV makes it possible for Internet Service Providers (ISPs) to employ various Virtual Network Functions (VNFs) without installing new equipments. One of the most attractive approaches in NFV technology is a so-called Joint Placement and Allocation of Virtual Network Functions (JPA-VNF) which considers the balance between VNF investment with Quality of Services (QoS). We introduce a novel capability function to measure the potential of locating VNF instances for each server in the proposed OJPA-HS model. This model allows the servers in the network to be heterogeneous, at the same time combines and generalizes many classical JPA-VNF models. Despite its NP-hardness, we present a provable best-possible deterministic online algorithm based on dynamic programming (DP). To conquer the high complexity of DP, we propose two additional randomized heuristics, the Las Vegas (LV) and Monte Carlo (MC) randomized algorithms, which performs even as good as DP with much smaller complexity. Besides, MC is a promising heuristic in practice as it has the advantage to deal with big data environment. Extensive numerical experiments are constructed for the proposed algorithms in the paper.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Outliers Detection Is Not So Hard: Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques

In this paper, we consider two types of robust models of the $k$-median/$k$-means problems: the outlier-version ($k$-MedO/$k$-MeaO) and the penalty-version ($k$-MedP/$k$-MeaP), in which we can mark some points as outliers and discard them. In $k$-MedO/$k$-MeaO, the number of outliers is bounded by a given integer. In $k$-MedP/$k$-MeaP, we do not bound the number of outliers, but each outlier will incur a penalty cost. We develop a new technique to analyze the approximation ratio of local search algorithms for these two problems by introducing an adapted cluster that can capture useful information about outliers in the local and the global optimal solution. For $k$-MeaP, we improve the best known approximation ratio based on local search from $25+\varepsilon$ to $9+\varepsilon$. For $k$-MedP, we obtain the best known approximation ratio. For $k$-MedO/$k$-MeaO, there exists only two bi-criteria approximation algorithms based on local search. One violates the outlier constraint (the constraint on the number of outliers), while the other violates the cardinality constraint (the constraint on the number of clusters). We consider the former algorithm and improve its approximation ratios from $17+\varepsilon$ to $3+\varepsilon$ for $k$-MedO, and from $274+\varepsilon$ to $9+\varepsilon$ for $k$-MeaO.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Too Much Information Kills Information: A Clustering Perspective

Clustering is one of the most fundamental tools in the artificial intelligence area, particularly in the pattern recognition and learning theory. In this paper, we propose a simple, but novel approach for variance-based k-clustering tasks, included in which is the widely known k-means clustering. The proposed approach picks a sampling subset from the given dataset and makes decisions based on the data information in the subset only. With certain assumptions, the resulting clustering is provably good to estimate the optimum of the variance-based objective with high probability. Extensive experiments on synthetic datasets and real-world datasets show that to obtain competitive results compared with k-means method (Llyod 1982) and k-means++ method (Arthur and Vassilvitskii 2007), we only need 7% information of the dataset. If we have up to 15% information of the dataset, then our algorithm outperforms both the k-means method and k-means++ method in at least 80% of the clustering tasks, in terms of the quality of clustering. Also, an extended algorithm based on the same idea guarantees a balanced k-clustering result.

0 citations0 reviewsNo code linkedOpen access